Search

This paper examines the balancing of assembly lines with multi-manned stations and a heterogeneous workforce. Both topics received considerable attention in the literature, but not in an integrated fashion. Combining these two characteristics gives rise to a highly combinatorial Multi-manned Assembly Line Worker Integration and Balancing Problem. When considering multi-manned stations, the already coupled decisions on assigning tasks to heterogeneous workers and workers to stations must be further linked with task scheduling assessments. We propose a Mixed-Integer Linear Programming model and develop two heuristic solution procedures, which tackle the problem with a hierarchical decomposition approach. Computational tests on a large dataset indicate that the proposed method can obtain good primal bounds in short computational times. We demonstrate that these results can be applied to the monolithic model either as a warm start or in a proximity search procedure to obtain synergistic gains with statistically significant differences. From a managerial perspective, we show that multi-manned stations can reduce the assembly line's length even in the presence of a heterogeneous workforce, which is crucial for many industries manufacturing large-size products. [ABSTRACT FROM AUTHOR]

Proximity search is extensively used in modern machine learning algorithms across various applications. Proximity search aims at finding data points which are close to the data point of interest. Extant algorithms depend on distance-based metrics to find the closest data points. However, these metrics are limited by their dependency on the distribution of data along different dimensions, making them sensitive to scaling and translation. The performance also suffers as the number of dimensions increase. Furthermore, proximity estimation between any two data points in extant metrics does not factor in the relative position of the rest of the data. In this paper, we aim to provide an alternative to these metrics by proposing Rank Adjacency Measure (RAM) which is agnostic to the distribution of the data. RAM estimates the probability of proximity between points by extending the concept of ordering in one dimension. We provide a detailed mathematical construction of RAM. We illustrate the effectiveness of the proposed methodology using five datasets in three application areas - Outlier Detection, Nearest Neighbor Search, and Text Similarity. While our proposed methodology outperforms existing algorithms in outlier detection by 50%, it performs at par with existing metrics for other two applications. We conclude the paper with discussion on its limitations and research directions for improving RAM.

In this paper, we are interested in algorithms that take in input an arbitrary graph G , and that enumerate in output all the (inclusion-wise) maximal "subgraphs" of G which fulfil a given property Π. All over this paper, we study several different properties Π , and the notion of subgraph under consideration (induced or not) will vary from a result to another. More precisely, we present efficient algorithms to list all maximal split subgraphs, maximal induced cographs and maximal threshold graphs of a given input graph. All the algorithms presented here run in polynomial delay, and moreover for split graphs it only requires polynomial space. In order to develop an algorithm for maximal split (edge-)subgraphs, we establish a bijection between the maximal split subgraphs and the maximal stable sets of an auxiliary graph. For cographs and threshold graphs, the algorithms rely on a framework recently introduced by Conte & Uno (2019) called Proximity Search. Finally we consider the extension problem, which consists in deciding if there exists a maximal induced subgraph satisfying a property Π that contains a set of prescribed vertices and that avoids another set of vertices. We show that this problem is NP-complete for every non-trivial hereditary property Π. We extend the hardness result to some specific edge version of the extension problem. [ABSTRACT FROM AUTHOR]

This paper studies a problem of determining the state of a system through costly tests of its components, where components can be tested simultaneously in batches to exploit economies of scale. This problem is a generalization of the classical sequential testing problem and it has applications in various settings, including machine maintenance, disease diagnosis, and new product development. We prove that the problem is strongly NP-hard, model it as a mixed-integer programming formulation, and we also propose a dynamic program for it. Additionally, we design a tabu search and a hybrid solution method that combines a tabu search metaheuristic and a proximity search matheuristic. Based on extensive computational experiments, we find that the dynamic program can solve instances with up to 25 components within a 15-minute time limit and 16 GB of RAM. With respect to larger instances, the proposed metaheuristic and hybrid method are better than a greedy heuristic. • We study sequential testing in batches with resource constraints. • We consider a fixed cost per batch, variable testing costs, and independent prior probabilities for each component. • We propose a mixed-integer programming formulation and a dynamic program. • We develop a tabu search and a hybrid method that combines tabu search with proximity search. [ABSTRACT FROM AUTHOR]

This paper proposes a new general technique for maximal subgraph enumeration which we call proximity search, whose aim is to design efficient enumeration algorithms for problems that could not be solved by existing frameworks. To support this claim and illustrate the technique we include output-polynomial algorithms for several problems for which output-polynomial algorithms were not known, including the enumeration of maximal bipartite subgraphs, maximal k-degenerate subgraphs (for bounded k), maximal induced chordal subgraphs, and maximal induced trees. Using known techniques, such as reverse search, the space of all maximal solutions induces an implicit directed graph called "solution graph" or \supergraph," and solutions are enumerated by traversing it; however, nodes in this graph can have exponential out-degree, thus requiring exponential time to be spent on each solution. The novelty of proximity search is a formalization that allows us to define a better solution graph, and a technique, which we call canonical reconstruction, by which we can exploit the properties of given problems to build such graphs. This results in solution graphs whose nodes have significantly smaller (i.e., polynomial) out-degree with respect to existing approaches, but that remain strongly connected, so that all solutions can be enumerated in polynomial delay by a traversal. A drawback of this approach is the space required to keep track of visited solutions, which can be exponential; we further propose a technique to induce a parent-child relationship among solutions and achieve polynomial space when suitable conditions are met. [ABSTRACT FROM AUTHOR]

Given a collection of n objects equipped with a distance function d(·, ·), the Nearest Neighbor Graph (NNG) consists in finding the nearest neighbor of each object in the collection. Without an index the total cost of NNG is quadratic. Using an index the cost would be sub-quadratic if the search for individual items is sublinear. Unfortunately, due to the so called curse of dimensionality the indexed and the brute force methods are almost equally inefficient. In this paper we present an efficient algorithm to build the Near Neighbor Graph (nNG), that is an approximation of NNG, using only the index construction, without actually searching for objects.

Given a collection of n objects equipped with a distance function d(·, ·), the Nearest Neighbor Graph (NNG) consists in finding the nearest neighbor of each object in the collection. Without an index the total cost of NNG is quadratic. Using an index the cost would be sub-quadratic if the search for individual items is sublinear. Unfortunately, due to the so called curse of dimensionality the indexed and the brute force methods are almost equally inefficient. In this paper we present an efficient algorithm to build the Near Neighbor Graph (nNG), that is an approximation of NNG, using only the index construction, without actually searching for objects. [ABSTRACT FROM AUTHOR]

Given a set of n disjoint balls $$b_1, \dots , b_n$$ in $$\mathrm{I\! R}^d$$ , we provide a data structure of near linear size that can answer $$(1\pm {\varepsilon })$$ -approximate kth-nearest neighbor queries on the balls in $$O(\log n + 1/{\varepsilon }^d)$$ time, where k and $${\varepsilon }$$ may be provided at query time. If k and $${\varepsilon }$$ are provided in advance, we provide a data structure to answer such queries requiring O( n / k) space; that is, the data structure requires sublinear space if k is sufficiently large. [ABSTRACT FROM AUTHOR]

Let $$\mathcal {D} = \{\mathsf {T}_1,\mathsf {T}_2, \ldots ,\mathsf {T}_D\}$$ be a collection of D string documents of n characters in total, that are drawn from an alphabet set $$\varSigma =[\sigma ]$$ . The top-k document retrieval problem is to preprocess $$\mathcal{D}$$ into a data structure that, given a query $$(P[1\ldots p],k)$$ , can return the k documents of $$\mathcal{D}$$ most relevant to the pattern P. The relevance is captured using a predefined ranking function, which depends on the set of occurrences of P in $$\mathsf {T}_d$$ . For example, it can be the term frequency (i.e., the number of occurrences of P in $$\mathsf {T}_d$$ ), or it can be the term proximity (i.e., the distance between the closest pair of occurrences of P in $$\mathsf {T}_d$$ ), or a pattern-independent importance score of $$\mathsf {T}_d$$ such as PageRank. Linear space and optimal query time solutions already exist for the general top- k document retrieval problem. Compressed and compact space solutions are also known, but only for a few ranking functions such as term frequency and importance. However, space efficient data structures for term proximity based retrieval have been evasive. In this paper we present the first sub-linear space data structure for this relevance function, which uses only o( n) bits on top of any compressed suffix array of $$\mathcal{D}$$ and solves queries in $$O((p+k) {{\mathrm{polylog}}}\,\,n)$$ time. We also show that scores that consist of a weighted combination of term proximity, term frequency, and document importance, can be handled using twice the space required to represent the text collection. [ABSTRACT FROM AUTHOR]

Biometric databases collect people's information and perform proximity search (finding records within bounded distance of the query) with few cryptographic protections. This work studies proximity searchable encryption applied to the iris biometric. Prior work proposed to build proximity search from inner product functional encryption (Kim et al., SCN 2018). This work identifies and closes two gaps in this approach: 1. Biometrics use long vectors, often with thousands of bits. Many inner product encryption schemes have to invert a matrix whose dimension scales with this size. Setup is then not feasible on commodity hardware. We introduce a technique that improves setup efficiency without harming accuracy. 2. Prior approaches leak distance between queries and all stored records. We propose a construction from function hiding, predicate, inner product encryption (Shen et al., TCC 2009) that avoids this leakage. Finally, we show that our scheme can be instantiated using symmetric pairing groups, which improves search efficiency. [ABSTRACT FROM AUTHOR]

Conventional abstraction queries, like range search and nearest neighbour retrieval, involve only conditions on objects' geometric properties. Today, several modern applications involve novel varieties of queries that aim to seek out objects satisfying each abstraction predicate, and a predicate on their associated texts. As an example, rather than considering all the restaurants, a nearest neighbour question would instead extract the eating house that's the highest among those whose menus contain "steak, spaghetti, brandy" all at an equivalent time. Presently the most suitable resolution to such queries is predicated on the IR2-tree, which, as shown during this paper, features a few deficiencies that seriously impact its potency. Motivated by this, a replacement access methodology has been developed which is known as the abstraction inverted index that extends the standard inverted index to address flat knowledge, and comes with algorithms that may answer nearest neighbour queries with keywords in real time. As scrutinised by experiments, the projected approaches outgo the IR2-tree in question latent period considerably, typically by an element of orders of magnitude. [ABSTRACT FROM AUTHOR]

Proximity searching is the problem of retrieving, from a given database, those objects closest to a query. To avoid exhaustive searching, data structures called indexes are built on the database prior to serving queries. The curse of dimensionality is a well-known problem for indexes: in spaces with sufficiently concentrated distance histograms, no index outperforms an exhaustive scan of the database. In recent years, a number of indexes for approximate proximity searching have been proposed. These are able to cope with the curse of dimensionality in exchange for returning an answer that might be slightly different from the correct one. In this paper we show that many of those recent indexes can be understood as variants of a simple general model based on K-nearest reference signatures. A set of references is chosen from the database, and the signature of each object consists of the K references nearest to the object. At query time, the signature of the query is computed and the search examines only the objects whose signature is close enough to that of the query. Many known and novel indexes are obtained by considering different ways to determine how much detail the signature records (e.g., just the set of nearest references, or also their proximity order to the object, or also their distances to the object, and so on), how the similarity between signatures is defined, and how the parameters are tuned. In addition, we introduce a space-efficient representation for those families of indexes, making it possible to search very large databases in main memory. Small indexes are cache friendly, inducing faster queries. We perform exhaustive experiments comparing several known and new indexes that derive from our framework, evaluating their time performance, memory usage, and quality of approximation. The best indexes outperform the state of the art, offering an attractive balance between all these aspects, and turn out to be excellent choices in many scenarios. Our framework gives high flexibility to design new indexes. [ABSTRACT FROM AUTHOR]

We investigate the classes of functions whose minimization diagrams can be approximated efficiently in Rd. We present a general framework and a data-structure that can be used to approximate the minimization diagram of such functions. The resulting data-structure has near linear size and can answer queries in logarithmic time. Applications include approximating the Voronoi diagram of multiplicatively weighted points, but the new technique also works for more general distance functions. For example, we get such data-structures for metrics induced by convex bodies, and the nearest furthest-neighbor distance to a set of point sets. Interestingly, our framework also works for distance functions that do not obey the triangle inequality. For many of these functions no near linear size approximation was known before. [ABSTRACT FROM AUTHOR]

For a set of n points in ℝd, and parameters κ and ε, we present a data structure that answers (1 + ε, κ) approximate nearest neighbor queries in logarithmic time. Surprisingly, the space used by the data structure is Õ (n/κ), where the Õ (·) notation here hides terms that are exponential in d, roughly varying as 1/εd,; as such, the space used is sublinear in the input size if k is sufficiently large. Our approach provides a novel way to summarize geometric data, such that meaningful proximity queries on the data can be carried out using this sketch. Using this, we provide a sublinear space data structure that can estimate the density of a point set under various measures, including (i) sum of distances of κ closest points to the query point and (ii) sum of squared distances of κ closest points to the query point. Our approach generalizes to other distance-based estimations of densities of similar flavor. We also study the problem of approximating some of these quantities when using sampling. In particular, we show that a sample of size Õ(n/κ) is sufficient, in some restricted cases, to estimate the above quantities. Remarkably, the sample size has only linear dependency on the dimension. [ABSTRACT FROM AUTHOR]

Abstract: An efficient computational capability for nonequilibrium radiation simulation via the ray tracing technique has been accomplished. The radiative rate equation is iteratively coupled with the aerodynamic conservation laws including nonequilibrium chemical and chemical–physical kinetic models. The spectral properties along tracing rays are determined by a space partition algorithm of the nearest neighbor search process, and the numerical accuracy is further enhanced by a local resolution refinement using the Gauss–Lobatto polynomial. The interdisciplinary governing equations are solved by an implicit delta formulation through the diminishing residual approach. The axisymmetric radiating flow fields over the reentry RAM-CII probe have been simulated and verified with flight data and previous solutions by traditional methods. A computational efficiency gain nearly forty times is realized over that of the existing simulation procedures. [Copyright &y& Elsevier]

Finding proximity information is crucial for massive database search. Locality Sensitive Hashing (LSH) is a method for finding nearest neighbors of a query point in a high-dimensional space. It classifies high-dimensional data according to data similarity. However, the 'curse of dimensionality' makes LSH insufficiently effective in finding similar data and insufficiently efficient in terms of memory resources and search delays. The contribution of this work is threefold. First, we study a Token List based information Search scheme (TLS) as an alternative to LSH. TLS builds a token list table containing all the unique tokens from the database, and clusters data records having the same token together in one group. Querying is conducted in a small number of groups of relevant data records instead of searching the entire database. Second, in order to decrease the searching time of the token list, we further propose the Optimized Token list based Search schemes (OTS) based on index-tree and hash table structures. An index-tree structure orders the tokens in the token list and constructs an index table based on the tokens. Searching the token list starts from the entry of the token list supplied by the index table. A hash table structure assigns a hash ID to each token. A query token can be directly located in the token list according to its hash ID. Third, since a single-token based method leads to high overhead in the results refinement given a required similarity, we further investigate how a Multi-Token List Search scheme (MTLS) improves the performance of database proximity search. We conducted experiments on the LSH-based searching scheme, TLS, OTS, and MTLS using a massive customer data integration database. The comparison experimental results show that TLS is more efficient than an LSH-based searching scheme, and OTS improves the search efficiency of TLS. Further, MTLS per forms better than TLS when the number of tokens is appropriately chosen, and a two-token adjacent token list achieves the shortest query delay in our testing dataset. [ABSTRACT FROM AUTHOR]

Abstract: An efficient and universal similarity search solution is a holy grail for multimedia information retrieval. Most similarity indexes work by mapping the original multimedia objects into simpler representations, which are then searched by proximity using a suitable distance function. In this paper we introduce a novel representation of the objects as sets of integers, with a distance that is computed using set operations. This allows us to use compressed inverted indexes, which have become a mature technology that excels in this type of search. Such indexes allow processing queries in main memory even for very large databases, so that the disk is accessed only to verify a few candidates and present the results. We show that our technique achieves very good speed/compression/recall tradeoffs. As an example, to reach 92% recall in 30-nearest neighbor searches, an index using 1 to 2.5bytes per object inspects less than 0.6% of the actual objects. Furthermore, the ratio between the distances to the actual nearest neighbors and those reported by our algorithm is very close to 1. [Copyright &y& Elsevier]

Abstract: This paper describes and evaluates a unified approach to phrasal query suggestions in the context of a high-precision search engine. The search engine performs ranked extended-Boolean searches with the proximity operator near being the default operation. Suggestions are offered to the searcher when the length of the result list falls outside predefined bounds. If the list is too long, the engine specializes the query through the use of super phrases; if the list is too short, the engine generalizes the query through the use of proximal subphrases. We describe methods for generating both types of suggestions and present algorithms for ranking the suggestions. Specifically, we present the problem of counting proximal subphrases for specialization and the problem of counting unordered super phrases for generalization. The uptake of our approach was evaluated by analyzing search log data from before and after the suggestion feature was added to a commercial version of the search engine. We looked at approximately 1.5 million queries and found that, after they were added, suggestions represented nearly 30% of the total queries. Efficacy was evaluated through a controlled study of 24 participants performing nine searches using three different search engines. We found that the engine with phrasal query suggestions had better high-precision recall than both the same search engine without suggestions and a search engine with a similar interface but using an Okapi BM25 ranking algorithm. [Copyright &y& Elsevier]

Current information retrieval methods either ignore the term positions or deal with exact term positions; the former can be seen as coarse document resolution, the latter as fine document resolution. We propose a new spectral-based information retrieval method that is able to utilize many different levels of document resolution by examining the term patterns that occur in the documents. To do this, we take advantage of the multiresolution analysis properties of the wavelet transform. We show that we are able to achieve higher precision when compared to vector space and proximity retrieval methods, while producing fast query times and using a compact index. [ABSTRACT FROM AUTHOR]