Existing methods for retrieving k-nearest neighbours suffer from the curse of dimensionality. We argue this is caused in part by inherent deficiencies of space partitioning, which is the underlying strategy used by most existing methods. We devise a new strategy that avoids partitioning the vector space and present a novel randomized algorithm that runs in time linear in dimensionality of the space and sub-linear in the intrinsic dimensionality and the size of the dataset and takes space constant in dimensionality of the space and linear in the size of the dataset. The proposed algorithm allows fine-grained control over accuracy and speed on a per-query basis, automatically adapts to variations in data density, supports dynamic updates to the dataset and is easy-to-implement. We show appealing theoretical properties and demonstrate empirically that the proposed algorithm outperforms locality-sensitivity hashing (LSH) in terms of approximation quality, speed and space efficiency.
Extensive work over the past several decades has produced a rich collection of algorithms for fast retrieval of @math -nearest neighbours. Space partitioning forms the basis of the majority of these algorithms. Early approaches store points in deterministic tree-based data structures, such as @math -d trees @cite_7 , R-trees @cite_11 and X-trees @cite_6 @cite_8 , which effectively partition the vector space into a hierarchy of half-spaces, hyper-rectangles or Voronoi polygons. These methods achieve query times that are logarithmic in the number of data points and work very well for low-dimensional data. Unfortunately, their query times grow exponentially in ambient dimensionality because the number of leaves in the tree that need to be searched increases exponentially in ambient dimensionality; as a result, for high-dimensional data, these algorithms become slower than exhaustive search. More recent methods like spill trees @cite_18 , RP trees @cite_9 and virtual spill trees @cite_15 extend these approaches by randomizing the dividing hyperplane at each node. Unfortunately, the number of points in the leaves increases exponentially in the intrinsic dimensionality of the dataset.
@cite_18 @cite_7 @cite_8 @cite_9 @cite_6 @cite_15 @cite_11
2170605888 2165558283 2109424811 2118123209 2115854352 2118269922
The quest for processing data in high-dimensional space has resulted in a number of innovative indexing mechanisms. Choosing an appropriate indexing method for a given set of data requires careful consideration of data properties, data construction methods, and query types. We present a new indexing method to support efficient point queries, range queries, and k-nearest neighbor queries. Our method indexes objects dynamically using algebraic techniques, and it can substantially reduce the negative impacts of the "curse of dimensionality". In particular, our method partitions the data space recursively into hypercubes of certain capacity and labels each hypercube using the Cantor pairing function, so that all objects in the same hypercube have the same label. The bijective property and the computational efficiency of the Cantor pairing function make it possible to efficiently map between high-dimensional vectors and scalar labels. The partitioning and labeling process splits a subspace if the data items contained in it exceed its capacity. From the data structure point of view, our method constructs a tree where each parent node contains a number of labels and child pointers, and we call it a PL-tree . We compare our method with popular indexing algorithms including R*-tree, X-tree, quad-tree, and iDistance. Our numerical results show that the dynamic PL-tree indexing significantly outperforms the existing indexing mechanisms. For some multimedia applications, it has been found that domain objects cannot be represented as feature vectors in a multidimensional space. Instead, pair-wise distances between data objects are the only input. To support content-based retrieval, one approach maps each object to a k-dimensional (k-d) point and tries to preserve the distances among the points. Then, existing spatial access index methods such as the R-trees and KD-trees can support fast searching on the resulting k-d points. However, information loss is inevitable with such an approach since the distances between data objects can only be preserved to a certain extent. Here we investigate the use of a distance-based indexing method. In particular, we apply the vantage point tree (vp-tree) method. There are two important problems for the vp-tree method that warrant further investigation, the n-nearest neighbors search and the updating mechanisms. We study an n-nearest neighbors search algorithm for the vp-tree, which is shown by experiments to scale up well with the size of the dataset and the desired number of nearest neighbors, n. Experiments also show that the searching in the vp-tree is more efficient than that for the @math -tree and the M-tree. Next, we propose solutions for the update problem for the vp-tree, and show by experiments that the algorithms are efficient and effective. Finally, we investigate the problem of selecting vantage-point, propose a few alternative methods, and study their impact on the number of distance computation. XP-trees (external priority search trees) are simple, practical and versatile structures supporting searches on points, intervals and higher dimensional spatial objects in secondary memory. Our approach to developing external structures is to consider worst-case efficient (internal) data structures from computational geometry, here the priority search tree. With the XP-tree we succeeded in transferring the underlying principle in an appropriate way to organize secondary storage, arriving at a practically useful structure. Together with external counterparts of other structures from computational geometry, such as segment tree, interval tree, and range tree, XP-trees can be used as building blocks to construct nested tree structures directly representing sets of spatial objects in higher dimensions. Like the internal counterpart, the XP-tree supports "halfrange" queries on points in two dimensions. Although XP-trees are not fully dynamic we believe them to be useful in many applications. Regarding balanced XP-trees, O(logdn + t) external accesses in halfrange queries are guaranteed, where n is the number of points, d the degree of the XP-tree, and t the number of points within a halfrange. Mapping intervals, as one-dimensional spatial objects, into two-dimensional points in the standard way, the structure supports all interesting kinds of queries on intervals. An XP-tree also supports queries on spatial objects in more dimensions by projecting them to an interval in one dimension. Hence the XP-tree can be used as an index structure in temporal or geometric databese systems. Experimentalperformance evaluations show that halfrange queries on two-dimensional point sets as well as all types of interval and point queries on sets of intervals are supported efficiently by the structure. Searching is quite fast, when no or few objects are retrieved. Although the shape of an XP-tree degenerates when a point set representation of a set of intervals is stored, the searching behaviour is practically the same as for a corresponding balanced structure. Searching is either very fast or has a large "retrieval ratio". Similarity search in multimedia databases requires an efficient support of nearest neighbor search on a large set of high dimensional points as a basic operation for query processing. As recent theoretical results show, state of the art approaches to nearest neighbor search are not efficient in higher dimensions. In our new approach, we therefore precompute the result of any nearest neighbor search which corresponds to a computation of the voronoi cell of each data point. In a second step, we store the voronoi cells in an index structure efficient for high dimensional data spaces. As a result, nearest neighbor search corresponds to a simple point query on the index structure. Although our technique is based on a precomputation of the solution space, it is dynamic, i.e. it supports insertions of new data points. An extensive experimental evaluation of our technique demonstrates the high efficiency for uniformly distributed as well as real data. We obtained a significant reduction of the search time compared to nearest neighbor search in the X tree (up to a factor of 4).