David R. Karger
Matthias Ruhl
ABSTRACT
Most research on nearest neighbor algorithms in the literature has been focused on the Euclidean case. In many practical search problems however, the underlying metric is non-Euclidean. Nearest neighbor algorithms for general metric spaces are quite weak, which motivates a search for other classes of metric spaces that can be tractably searched.In this paper, we develop an efficient dynamic data structure for nearest neighbor queries in growth-constrained metrics. These metrics satisfy the property that for any point q and number r the ratio between numbers of points in balls of radius 2r and r is bounded by a constant. Spaces of this kind may occur in networking applications, such as the Internet or Peer-to-peer networks, and vector quantization applications, where feature vectors fall into low-dimensional manifolds within high-dimensional vector spaces.
- J. Bentley, Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9):509--517, 1975. Google Scholar
Digital Library
- J. Bentley, B. Weide, and A. Yao. Optimal expected-time algorithms for closest point problems. ACM Transactions of (MATH)ematical Software, 6(4):563--580, 1980. Google ScholarDigital Library
- S. Brin. Near neighbor search in large metric spaces. In Proceedings VLDB, pages 574--584, 1995. Google ScholarDigital Library
- E. Chávez, G. Navarro, R. Baeza-Yates, and J. L. Marroquín. Searching in metric spaces. ACM Computing Surveys, 33(3):273--321, 2001. Google ScholarDigital Library
- K. Clarkson. Nearest neighbor queries in metric spaces. Discrete Computational Geometry, 22(1):63--93, 1999.Google ScholarCross Ref
- C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. Theory of Computing Systems, 32:241--280, 1999.Google ScholarCross Ref
- I. Stoica, R. Morris, D. Karger, F. Kasshoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings ACM SIGCOMM, 2001. Google ScholarDigital Library
- J. B. Tenenbaum. Mapping a manifold of perceptual observations. In Advances in Neural Information Processing Systems, volume 10. The MIT Press, 1998. Google ScholarDigital Library
- J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319--2323, December 2000. See also http://isomap.stanford.edu.Google ScholarCross Ref
- J. Uhlmann. Satisfying general proximity/similarity queries with metric trees. Information Processing Letters, 40:175--179, 1991.Google ScholarCross Ref
- P. Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. In Proceedings SODA, pages 311--321, 1993. Google ScholarDigital Library
Index Terms
- Finding nearest neighbors in growth-restricted metrics
Recommendations
Improving Locality Sensitive Hashing by Efficiently Finding Projected Nearest Neighbors
Similarity Search and ApplicationsAbstractSimilarity search in high-dimensional spaces is an important task for many multimedia applications. Due to the notorious curse of dimensionality, approximate nearest neighbor techniques are preferred over exact searching techniques since they can ...
K-Nearest Neighbor Finding Using MaxNearestDist
Similarity searching often reduces to finding the k nearest neighbors to a query object. Finding the k nearest neighbors is achieved by applying either a depth- first or a best-first algorithm to the search hierarchy containing the data. These ...
Extending LAESA Fast Nearest Neighbour Algorithm to Find the k Nearest Neighbours
Proceedings of the Joint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern RecognitionMany pattern recognition tasks make use of the k nearest neighbour (k-NN) technique. In this paper we are interested on fast k- NN search algorithms that can work in any metric space i.e. they are not restricted to Euclidean-like distance functions. ...
Comments