Search

We perform an experimental study to evaluate the performance of a matheuristic for the production routing problem (PRP). First, we develop a basic matheuristic that prescribes starting from a partial initial solution, completing it using a sequence of constructive heuristics, and improving it using a general-purpose mixed-integer programming heuristic. Next, we investigate the effect of three state-of-the-art mathematical formulations on the proposed matheuristic convergence. The formulations are implemented and tested with and without the use of valid inequalities. In addition, by suggesting different techniques to generate a feasible starting solution for our matheuristic, we assess the contribution of an initial solution to the matheuristic’s overall performance. We conduct extensive computational experiments on benchmark data instances for the PRP. The results show that a proper choice of an embedded mathematical formulation depends on the data instances’ features, such as the number of customers and the length of the planning horizon. The comparisons undertaken in this study indicate that having a better initial solution does not necessarily lead to finding a better final solution. published

Data in the form of graphs are prevalent, ranging from biological and social networks to citation graphs and the Web. In particular, most real-world graphs are heterogeneous, containing objects of multiple types, which present new opportunities for many problems on graphs. Consider a typical proximity search problem on graphs, which boils down to measuring the proximity between two given nodes. Most earlier studies on homogeneous or bipartite graphs only measure a generic form of proximity, without accounting for different “semantic classes”—for instance, on a social network two users can be close for different reasons, such as being classmates or family members, which represent two distinct semantic classes. Learning these semantic classes are made possible on heterogeneous graphs through the concept of metagraphs . In this study, we identify metagraphs as a novel and effective means to characterize the common structures for a desired class of proximity. Subsequently, we propose a family of metagraph-based proximity, and employ a learning-to-rank technique that automatically learns the right parameters to suit the desired semantic class. In terms of efficiency, we develop a symmetry-based matching algorithm to speed up the computation of metagraph instances. Empirically, extensive experiments reveal that our metagraph-based proximity substantially outperforms the best competitor by more than 10 percent, and our matching algorithm can reduce matching time by more than half. As a further generalization, we aim to derive a general node and edge representation for heterogeneous graphs, in order to support arbitrary machine learning tasks beyond proximity search. In particular, we propose the finer-grained anchored metagraph , which is capable of discriminating the roles of nodes within the same metagraph. Finally, further experiments on the general representation show that we can outperform the state of the art significantly and consistently across various machine learning tasks.

The direction of arrival (DOA) estimation for off-grid targets in the coprime array, which can extend degrees of freedom, is studied. Among existing research results, joint orthogonal matching pursuit (JOMP) has obvious advantages in complexity, but drawbacks in accuracy. Therefore, a bi-level iterative algorithm is proposed to improve estimation performance of JOMP in this study. First, JOMP is executed to obtain the initial estimations of DOAs and mismatch parameters. Then, an iterative proximity searching is implemented to update target vectors to decline the residual further. After that, on the strength of results of the secondary iteration, the signal spectrum and mismatch parameters can be obtained through exploiting LS algorithm. Simulation results verify effectiveness of the proposed algorithm.

Query reformulation, including query recommendation and query auto-completion, is a popular add-on feature of search engines, which provide related and helpful reformulations of a keyword query. Due to the dropping prices of smartphones and the increasing coverage and bandwidth of mobile networks, a large percentage of search engine queries are issued from mobile devices. This makes it possible to improve the quality of query recommendation and auto-completion by considering the physical locations of the query issuers. However, limited research has been done on location-aware query reformulation for search engines. In this paper, we propose an effective spatial proximity measure between a query issuer and a query with a location distribution obtained from its clicked URLs in the query history. Based on this, we extend popular query recommendation and auto-completion approaches to our location-aware setting, which suggest query reformulations that are semantically relevant to the original query and give results that are spatially close to the query issuer. In addition, we extend the bookmark coloring algorithm for graph proximity search to support our proposed query recommendation approaches online, and we adapt an A* search algorithm to support our query auto-completion approach. We also propose a spatial partitioning based approximation that accelerates the computation of our proposed spatial proximity. We conduct experiments using a real query log, which show that our proposed approaches significantly outperform previous work in terms of quality, and they can be efficiently applied online.

We address an integrated airline scheduling problem that combines three airline planning processes: fleet assignment, aircraft routing, and crew pairing. For a given daily flight schedule, the problem requires simultaneously assigning aircraft and crews to each scheduled flight, taking into account aircraft maintenance restrictions and crew work rules. We propose to solve this complex problem of integrated flight planning while taking into account robustness considerations. In this regard, robustness is achieved by restricting tight connections in the schedule and increasing the number of connections where crews follow the aircraft. We formulate the problem using a very large-scale, yet compact, mixed-integer programming model, and we propose a matheuristic consisting of a decomposition approach and a proximity search algorithm. Computational experiments carried out on real instances from a major airline and having up to 14,014 itineraries, 646 flights, and 202 aircraft provide evidence of the proposed approach's efficacy. In particular, we find that the average deviation from a conservative bound is at most equal to 0.6%. 2021 This research was carried out with financial support from the AXIOM project, partly funded by the Research Council of Norway . We thank the Editor and the two reviewers for their valuable comments on our manuscript, which have helped us to improve it. Scopus

Similarity searching is a very useful task in several disciplines such as pattern recognition, machine learning, and decision theory. To solve this task we can use an index to speed up the searching. Among the current indices, the permutant based searching approach has proved its efficiency for high-dimensional data before, however up to now this approach had not been adapted to work with low-dimensional data where the approach seemed useless. We propose several ways to adapt the permutant searching approach for low-dimensional data, using zones varying the distribution of the radii, trying different distance measures, and using partial distance computation as well. After many experiments, we arrived to conclusions about the optimal values of the parameters using a synthetic database of vectors, and then use these learned values on real databases obtaining excellent results for k -nearest neighbor queries, both in high and low dimensional data.

This paper presents an efficient online approach for complete coverage path planning of mobile robots in an unknown workspace based on online boustrophedon motion and an optimized backtracking mechanism. The presented approach first performs a single continuous boustrophedon motion until a critical point is reached. In order to completely cover the environment, next starting point is decided by using the accumulated knowledge of the environment map. An efficient backtracking technique based on proposed Two-way Proximity Search algorithm is used to plan a path from the critical point to the new starting point. Simulation results show the efficiency of proposed backtracking approach with improved total coverage time, coverage path length and memory requirements.

Searching by proximity has been a source of puzzling behaviors and counter-intuitive findings for well established algorithmic design rules. One example is a linked list; it is the worst data structure for exact searching, and one of the most competitive for proximity searching. Common sense also dictates that an online data structure is less competitive than the full-knowledge, static version. A counter example in proximity searching is the static Spatial Approximation Tree (SAT), which is slower than its dynamic version (DSAT). In this paper we show that changing only the insertion policy of the SAT, leaving every other aspect of the data structure untouched, can produce a systematically faster index. We call the index Distal Spatial Approximation Tree (DiSAT). We found that even a random insertion policy produce a faster version of the SAT, which explains why the DSAT is faster than SAT. In brief, the SAT is improved by selecting distal, instead of proximal, nodes. This is the exact opposite of the insertion policy proposed in the original paper, and can be used in main or secondary memory versions of the index. We tested our approach with representatives of the state of the art in exact proximity searching. As it happens often in experimental setups, there are no absolute winners in all the aspects tested. Our data structure has no parameters to tune-up and a small memory footprint. In addition it can be constructed quickly. Our approach is among the most competitive, those outperforming DiSAT achieve this at the expense of larger memory usage or an impractical construction time.

Recent years have witnessed the emergence of new types of semantic search engines which attempt to overcome the defects of the traditional search engines by providing different search patterns. A big question here is that in order to achieve the semantic search engines SSEs, what types of search patterns should SSEs support? To help seek one of the many possible answers, in this paper we start with classifying and comparing current search engines, particularly from the perspective of search patterns which consist of index structure, user profiles, and interaction mechanism. We then present a novel search pattern named ExNa by defining its model and basic operations in detail. To validate the ExNa search pattern, we develop a prototype search engine named KNOWLE, and the experimental results show that KNOWLE equipped with ExNa can improve both the efficiency of the entire system when compared with search engines of other search patterns. Copyright © 2016 John Wiley & Sons, Ltd.

Search engine is a computer program that searches documents on the internet containing terms being searched by a user. This study discusses the search engines, an effective tool for library professionals. The study determines the various aspects of Search engine including background of search engines, and how search engines work. Further, it analyses the internet search techniques, i.e., basic, advanced and refine search. The paper highlights the effective use in searching information on internet on the basis of Boolean operators AND, OR, NOT and proximity searching, etc. Finally, it highlights the categories of search engines. http://dx.doi.org/10.14429/djlit.35.6.8804

In this paper, we propose a new method for 2D/3D object indexing and retrieval. The principle consists of an automatic selection of optimal views by using an incremental algorithm based on pivot selection techniques for proximity searching in metric spaces. The selected views are afterward described by four well-established descriptors from the MPEG-7 standard, namely: the color structure descriptor (CSD), the scalable color descriptor (SCD), the edge histogram descriptor (EHD) and the color layout descriptor (CLD). We present our results on two databases: The Amsterdam Library of Images (ALOI-1000), consisting of 72,000 color images of views, and the Columbia Object Image Library (COIL-100), consisting of 7200 color images of views. The results prove the performance of the developed method and its superiority over the k-means algorithm and the automatic selection of optimal views proposed by Mokhtarian et al.

In this paper we investigate the effects of replacing the objective function of a 0-1 mixed-integer convex program (MIP) with a "proximity" one, with the aim of using a black-box solver as a refinement heuristic. Our starting observation is that enumerative MIP methods naturally tend to explore a neighborhood around the solution of a relaxation. A better heuristic performance can however be expected by searching a neighborhood of an integer solution--a result that we obtain by just modifying the objective function of the problem at hand. The relationship of this approach with primal integer methods is also addressed. Promising computational results on different proof-of-concept implementations are presented, suggesting that proximity search can be quite effective in quickly refining a given feasible solution. This is particularly true when a sequence of similar MIPs has to be solved as, e.g., in a column-generation setting.

In the information retrieval process, functions that rank documents according to their estimated relevance to a query typically regard query terms as being independent. However, it is often the joint presence of query terms that is of interest to the user, which is overlooked when matching independent terms. One feature that can be used to express the relatedness of co-occurring terms is their proximity in text. In past research, models that are trained on the proximity information in a collection have performed better than models that are not estimated on data. We analyzed how co-occurring query terms can be used to estimate the relevance of documents based on their distance in text, which is used to extend a unigram ranking function with a proximity model that accumulates the scores of all occurring term combinations. This proximity model is more practical than existing models, since it does not require any co-occurrence statistics, it obviates the need to tune additional parameters, and has a retrieval speed close to competing models. We show that this approach is more robust than existing models, on both Web and newswire corpora, and on average performs equal or better than existing proximity models across collections.

Ranked result lists with query-dependent snippets have become state of the art in text search. They are typically implemented by searching, at query time, for occurrences of the query words in the top-ranked documents. This document-based approach has three inherent problems: (i) when a document is indexed by terms which it does not contain literally (e.g., related words or spelling variants), localization of the corresponding snippets becomes problematic; (ii) each query operator (e.g., phrase or proximity search) has to be implemented twice, on the index side in order to compute the correct result set, and on the snippet-generation side to generate the appropriate snippets; and (iii) in a worst case, the whole document needs to be scanned for occurrences of the query words, which could be problematic for very long documents. We present a new index-based method that localizes snippets by information solely computed from the index and that overcomes all three problems. Unlike previous index-based methods, we show how to achieve this at essentially no extra cost in query processing time, by a technique we call operator inversion . We also show how our index-based method allows the caching of individual segments instead of complete documents, which enables a significantly larger cache hit-ratio as compared to the document-based approach. We have fully integrated our implementation with the CompleteSearch engine.

Current Google image search adopt a hybrid search approach in which a text-based query (e.g., “Paris landmarks”) is used to retrieve a set of relevant images, which are then refined by the user (e.g., by re-ranking the retrieved images based on similarity to a selected example). We conjecture that given such hybrid image search engines, learning per-query distance functions over image features can improve the estimation of image similarity. We propose scalable solutions to learning query-specific distance functions by 1) adopting a simple large-margin learning framework, 2) using the query-logs of text-based image search engine to train distance functions used in content-based systems. We evaluate the feasibility and efficacy of our proposed system through comprehensive human evaluation, and compare the results with the state-of-the-art image distance function used by Google image search.

Systems that produce ranked lists of results are abundant. For instance, Web search engines return ranked lists of Web pages. There has been work on distance measure for list permutations, like Kendall tau and Spearman's footrule, as well as extensions to handle top-k lists, which are more common in practice. In addition to ranking whole objects (e.g., Web pages), there is an increasing number of systems that provide keyword search on XML or other semistructured data, and produce ranked lists of XML sub-trees. Unfortunately, previous distance measures are not suitable for ranked lists of sub-trees since they do not account for the possible overlap between the returned sub-trees. That is, two sub-trees differing by a single node would be considered separate objects. In this paper, we present the first distance measures for ranked lists of sub-trees, and show under what conditions these measures are metrics. Furthermore, we present algorithms to efficiently compute these distance measures. Finally, we evaluate and compare the proposed measures on real data using three popular XML keyword proximity search systems.

A search engine user with a well-defined information need is not interested in getting thousands of hits, but a few hits that are all highly relevant to their search. Often search words need to be refined and augmented to narrow results to more relevant pages. However, an overly specific query may lead to no hits at all, while most typical queries lead to thousands or even millions of them, both undesirable outcomes. This paper suggests a query rewriting method for generating alternative query strings and proposes a hit count prediction model for predicting the number of search engine hits for each alternative query string, based on the English language frequencies of the words in the search terms. Using the hit count prediction model, different types of search strategies, such as a lowest hit count query preference, can be utilized to improve users’ search experience. We present an evaluation experiment of the hit count prediction model for three major search engines. We also discuss and quantify how far the Google, Yahoo! and Bing search engines diverge from monotonic behaviour, considering negative and positive search terms separately.

Authority flow and proximity search have been used extensively in measuring the association between entities in data graphs, ranging from the web to relational and XML databases. These two ranking factors have been used and studied separately in the past. In addition to their semantic differences, a key advantage of proximity search is the existence of efficient execution algorithms. In contrast, due to the complexity of calculating the authority flow, current systems only use precomputed authority flows in runtime. This limitation prohibits authority flow to be used more effectively as a ranking factor. In this paper, we present a comparative analysis of the two ranking factors. We present an efficient approximation of authority flow based on proximity search. We analytically estimate the approximation error and how this affects the ranking of the results of a query.

This paper presents a fully decentralised, efficient and highly scalable resource-discovery approach that is applicable to large heterogeneous and highly dynamic distributed systems. The approach is based on a hybrid overlay network, named TRIPOD, which enables an efficient search for resources in the aforementioned highly distributed, dynamic and largely heterogeneous systems. The key advantages of our solution are its efficient proximity searching, an ability to search over highly dynamic resource properties, the in-built fault tolerance and robustness and, finally, its very low and manageable network overhead.

In this paper, we study the problem of keyword proximity search in XML documents. We take the disjunctive semantics among the keywords into consideration and find top-k relevant compact connected trees (CCTrees) as the answers of keyword proximity queries. We first introduce the notions of compact lowest common ancestor (CLCA) and maximal CLCA (MCLCA), and then propose compact connected trees and maximal CCTrees (MCCTrees) to efficiently and effectively answer keyword proximity queries. We give the theoretical upper bounds of the numbers of CLCAs, MCLCAs, CCTrees and MCCTrees, respectively. We devise an efficient algorithm to generate all MCCTrees, and propose a ranking mechanism to rank MCCTrees. Our extensive experimental study shows that our method achieves both high efficiency and effectiveness, and outperforms existing state-of-the-art approaches significantly.

Metric space searching is an emerging technique to address the problem of efficient similarity searching in many applications, including multimedia databases and other repositories handling complex objects. Although promising, the metric space approach is still immature in several aspects that are well established in traditional databases. In particular, most indexing schemes are static, that is, few of them tolerate insertion or deletion of elements at reasonable cost over an existing index. The spatial approximation tree ( sa--tree ) has been experimentally shown to provide a good tradeoff between construction cost, search cost, and space requirement. However, the sa--tree is static, which renders it unsuitable for many database applications. In this paper, we study different methods to handle insertions and deletions on the sa--tree at low cost. In many cases, the dynamic construction (by successive insertions) is even faster than the previous static construction, and both are similar elsewhere. In addition, the dynamic version significantly improves the search performance of sa--trees in virtually all cases. The result is a much more practical data structure that can be useful in a wide range of database applications.

We give efficient algorithms and index data structures for range search in general metric spaces. We give a simple methods to make almost any existing algorithm memory adaptive, improving the search the more memory is available. For vector spaces and metric space of strings we show how several distances can be computed in bit-parallelly, in sequential computer, and use the result to improve the search performance. This method works especially well with approximate range queries. The experimental results show that we can obtain order of magnitude improvements over the existing methods.

We have developed simple algorithms that allow adjacency and proximity searching in Google and the Science Citation Index (SCI). The SCI algorithm exploits the fact that SCI stopwords in a search phrase function as a placeholder. Such a phrase serves effectively as a fixed adjacency condition determined by the number n of adjacent stopwords (i.e. retrieve all records where word A and word B are separated by n words in at least one location). The algorithm integrates over search phrases with different numbers of adjacent stopwords to provide a flexible adjacency or proximity capability (i.e. retrieve all records where word A and word B are separated by n or fewer words in at least one location, where n is the maximum separation desired between A and B in at least one location). The Google algorithm exploits the fact that asterisks (in Google) separating words in a phrase function like word wildcards. The difference between two such phrases (the first phrase containing one fewer asterisk than the second phrase) serves effectively as a fixed adjacency or proximity condition, with the number of separating words equal to the number of asterisks in the first phrase. The algorithm integrates over these phrase differentials to provide a flexible adjacency or proximity capability (i.e. retrieve all records where word A and word B are separated by n or fewer words in at least one location, where n is the maximum separation desired between A and B in at least one location).

Similarity searching has a vast number of applications in numerous fields, such as audio and image databases, image quantization and compression, text or document databases, computational biology, and data mining, to name a few. A common aspect of all the applications is that we have a universe U of objects, and a non-negative distance function d : U× U→ R. The distance function is metric, if it satisfies for all x, y, z ∈ U

The metric space model abstracts many proximity search problems, from nearest-neighbor classifiers to textual and multimedia information retrieval. In this context, an index is a data structure that speeds up proximity queries. However, indexes lose their efficiency as the intrinsic data dimensionality increases. In this paper we present a simple index called list of clusters (LC), which is based on a compact partitioning of the data set. The LC is shown to require little space, to be suitable both for main and secondary memory implementations, and most importantly, to be very resistant to the intrinsic dimensionality of the data set. In this aspect our structure is unbeaten. We finish with a discussion of the role of unbalancing in metric space searching, and how it permits trading memory space for construction time.

When searching for information on the Web, it is often necessary to use one of the available search engines. Because the number of results are quite large for most queries, we need some measure of relevance with respect to the query. One of the most important relevance factors is the proximity score, i.e., how close the keywords appear together in a given document. A basic proximity score is given by the size of the smallest range containing all the keywords in the query. We generalize the proximity score to include many practically important cases and present an O(n log k)-time algorithm for the generalized problem, where k is the number of keywords and n is the number of occurrences of the keywords in a document.

Traditional online information services have been offering proximity and positional operators for many years to narrow or broaden a search by specifying how far and in what order the words of the query should appear in the documents or in their surrogates to qualify for retrieval. The proximity and positional operators which define the distance and the order of the words required are not exactly intuitive and vary greatly from one online system to the other. Still, they are used by the savviest searchers intensively. This paper examines and evaluates various search engines in terms of word proximity and position.

The main bottleneck of the research in metric space searching is the so-called curse of dimensionality, which makes the task of searching some metric spaces intrinsically difficult, whatever algorithm is used. A recent trend to break this bottleneck resorts to probabilistic algorithms, where it has been shown that one can find 99% of the relevant objects at a fraction of the cost of the exact algorithm. These algorithms are welcome in most applications because resorting to metric space searching already involves a fuzziness in the retrieval requirements. In this paper, we push further in this direction by developing probabilistic algorithms on data structures whose exact versions are the best for high dimensions. As a result, we obtain probabilistic algorithms that are better than the previous ones. We give new insights on the problem and propose a novel view based on time-bounded searching. We also propose an experimental framework for probabilistic algorithms that permits comparing them in offline mode.

MyMED is a database system that mirrors MEDLINETM data and that provides access to the data locally, without the restrictions involved in accessing the National Library of Medicine Web site. The implementation of MyMED is based on the IBM DB2 Universal DatabaseTM, the DB2® XML Extender and the DB2 Text Information Extender. The resulting system supports advanced queries, including wildcard searching abilities, proximity searching, scoring functions, and capabilities to build a thesaurus, and constitutes an important research tool for text mining of biomedical-citation data. The paper describes the challenges encountered in the use of DB2 ExtendersTM products, the methods used to overcome these challenges, and the implementation of MyMED. The benefits of MyMED are illustrated through some use cases, and directions for future work are outlined.

With few exceptions, proximity search algorithms in metric spaces based on the use of pivots select them at random among the objects of the metric space. However, it is well known that the way in which the pivots are selected can drastically affect the performance of the algorithm. Between two sets of pivots of the same size, better chosen pivots can largely reduce the search time. Alternatively, a better chosen small set of pivots (requiring much less space) can yield the same efficiency as a larger, randomly chosen, set. We propose an efficiency measure to compare two pivot sets, combined with an optimization technique that allows us to select good sets of pivots. We obtain abundant empirical evidence showing that our technique is effective, and it is the first that we are aware of in producing consistently good results in a wide variety of cases and in being based on a formal theory. We also show that good pivots are outliers, but that selecting outliers does not ensure that good pivots are selected.