Search

Nearest neighbor search is a fundamental and essential operation in applications from many domains, such as databases, machine learning, multimedia, and computer vision. Because exact searching results are not efficient for a high-dimensional space, a lot of efforts have turned to approximate nearest neighbor search. Although many algorithms have been continuously proposed in the literature each year, there is no comprehensive evaluation and analysis of their performance. In this paper, we conduct a comprehensive experimental evaluation of many state-of-the-art methods for approximate nearest neighbor search. Our study (1) is cross-disciplinary (i.e., including 19 algorithms in different domains, and from practitioners) and (2) has evaluated a diverse range of settings, including 20 datasets, several evaluation metrics, and different query workloads. The experimental results are carefully reported and analyzed to understand the performance results. Furthermore, we propose a new method that achieves both high query efficiency and high recall empirically on majority of the datasets under a wide range of settings. [ABSTRACT FROM AUTHOR]

Given two object sets Q and O, a metric similarity join finds similar object pairs according to a certain criterion. This operation has a wide variety of applications in data cleaning and data mining, to name but a few. However, the rapidly growing volume of data nowadays challenges traditional metric similarity join methods, and thus, a distributed method is required. In this paper, we adopt a popular distributed framework, namely, MapReduce, to support scalable metric similarity joins. To ensure the load balancing, we present two sampling based partition methods. One utilizes the pivot and the space-filling curve mappings to cluster the data into one-dimensional space, and then selects high quality centroids to enable equal-sized partitions. The other uses the KD-tree partitioning technique to equally divide the data after the pivot mapping. To avoid unnecessary object pair evaluation, we propose a framework that maps the two involved object sets in order, where the range-object filtering, the double-pivot filtering, the pivot filtering, and the plane sweeping techniques are utilized for pruning. Extensive experiments with both real and synthetic data sets demonstrate that our solutions outperform significantly existing state-of-the-art competitors. [ABSTRACT FROM AUTHOR]

Spatial queries including similarity search and similarity joins are useful in many areas, such as multimedia retrieval, data integration, and so on. However, they are not supported well by commercial DBMSs. This may be due to the complex data types involved and the needs for flexible similarity criteria seen in real applications. In this paper, we propose a versatile and efficient disk-based index for metric data, the S pace-filling curve and Pivot-based B ^+ -tree (SPB-tree). This index leverages the B $^+$ -tree, and uses space-filling curve to cluster data into compact regions, thus achieving storage efficiency. It utilizes a small set of so-called pivots to reduce significantly the number of distance computations when using the index. Further, it makes use of a separate random access file to support a broad range of data. By design, it is easy to integrate the SPB-tree into an existing DBMS. We present efficient algorithms for processing similarity search and similarity joins, as well as corresponding cost models based on SPB-trees. Extensive experiments using both real and synthetic data show that, compared with state-of-the-art competitors, the SPB-tree has much lower construction cost, smaller storage size, and supports more efficient similarity search and similarity joins with high accuracy cost models. [ABSTRACT FROM PUBLISHER]

An all-k-nearest-neighbor (AkNN) query finds from a given object set O , k nearest neighbors for each object in a specified query set Q. This operation is common in many applications such as GIS, data mining, and image analysis. Although it has received much attention in the Euclidean space, there is little prior work on the metric space. In this paper, we study the problem of AkNN retrieval in metric spaces, termed metric AkNN (MAkNN) search, and propose efficient algorithms for supporting MAk NN queries with arbitrary k value. Our methods utilize dynamic disk-based metric indexes (e.g., M-tree), employ a series of pruning rules, take advantage of grouping, reuse, pre-processing, and progressive pruning techniques, require no detailed representations of objects, and can be applied as long as the distance metric satisfies the triangle inequality. In addition, we extend our approaches to tackle metric self-AkNN (MSAkNN) search, a natural variation of MAkNN queries, where the query set Q is identical to the object set O. Extensive experiments using both real and synthetic data sets demonstrate, compared with state-of-the-art euclidean Ak NN, MAkNN, and MSAkNN algorithms, the performance of our proposed algorithms and the effectiveness of our presented techniques. [ABSTRACT FROM PUBLISHER]

Skyline query is of great importance in many applications, such as multicriteria decision making and business planning. In particular, a skyline point is a data object in the database whose attribute vector is not dominated by that of any other objects. Previous methods to retrieve skyline points usually assume static data objects in the database (that is, their attribute vectors are fixed), whereas several recent works focus on skyline queries with dynamic attributes. In this paper, we propose a novel variant of skyline queries, namely metric skyline, whose dynamic attributes are defined in the metric space (that is, not limited to the euclidean space). We illustrate an efficient and effective pruning mechanism to answer metric skyline queries (MSQs) through a metric index. Most importantly, we formalize the query performance of the MSQ in terms of the pruning power (PP), by a cost model, in light of which we construct an optimized metric index aiming to maximize PP of MSQs. Extensive experiments have demonstrated the efficiency and effectiveness of our proposed pruning techniques as well as the constructed index in answering MSQs. [ABSTRACT FROM AUTHOR]

This paper first proposes three improved gossip mechanisms by mapping links into metric space and dynamically adapting the number of selected neighbors to disseminate messages. Experiments and comparisons show that these mechanisms can improve the performance of gossip in peer-to-peer (P2P) networks. This is the effect of mapping a network into a metric space that differentiates nodes and links according to linking characteristics and controlling local information flow with knowing such differences. A further study about query routing on P2P semantic link network shows that mapping a network into a semantic space can also improve the performance. An intrinsic rule is found by experimental comparisons and analysis: The performance of a P2P network can be improved by designing an appropriate mapping from the network into metric space or semantic space. A general framework for networking with metric space and semantic space is suggested. [ABSTRACT FROM AUTHOR]

Given a set D of objects, a reverse nearest neighbor (RNN) query returns the objects q in D such that o is closer to a query object q than to any other object in D, according to a certain similarity metric. The existing ANN solutions are not sufficient because they either 1) rely on precomputed information that is expensive to maintain in the presence of updates or 2) are applicable only when the data consists of ‘Euclidean objects’ and similarity is measured using the L2 norm. In this paper, we present the first algorithms for efficient RNN search in generic metric spaces. Our techniques require no detailed representations of objects, and can be applied as long as their mutual distances can be computed and the distance metric satisfies the triangle inequality. We confirm the effectiveness of the proposed methods with extensive experiments. [ABSTRACT FROM AUTHOR]

In this paper, we present an embedding technique, called MetricMap, which is capable of estimating distances in a pseudometric space. Given a database of objects and a distance function for the objects, which is a pseudometric, we map the objects to vectors in a pseudo-Euclidean space with a reasonably low dimension while preserving the distance between two objects approximately. Such an embedding technique can be used as an approximate oracle to process a broad class of distance-based queries. It is also adaptable to data mining applications such as data clustering and classification. We present the theory underlying MetricMap and conduct experiments to compare MetricMap with other methods including MVP-tree and M-tree in processing the distance-based queries. Experimental results on both protein and RNA data show the good performance and the superiority of MetricMap over the other methods. [ABSTRACT FROM AUTHOR]