ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Near Neighbor Search in Large Metric Spaces.

Sergey Brin: Near Neighbor Search in Large Metric Spaces. VLDB 1995: 574-584
@inproceedings{DBLP:conf/vldb/Brin95,
  author    = {Sergey Brin},
  editor    = {Umeshwar Dayal and
               Peter M. D. Gray and
               Shojiro Nishio},
  title     = {Near Neighbor Search in Large Metric Spaces},
  booktitle = {VLDB'95, Proceedings of 21th International Conference on Very
               Large Data Bases, September 11-15, 1995, Zurich, Switzerland},
  publisher = {Morgan Kaufmann},
  year      = {1995},
  isbn      = {1-55860-379-4},
  pages     = {574-584},
  ee        = {db/conf/vldb/Brin95.html},
  crossref  = {DBLP:conf/vldb/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Given user data, one often wants to find approximate matches in a large database. A good example of such a task is finding images similar to a given image in a large collection of images. We focus on the important and technically difficult case where each data element is high dimensional, or more generally, is represented by a point in a large metric space- and distance calculations are computationally expensive.

In this paper we introduce a data structure to solve this problem called a GNAT - Geometric Near-neighbor Access Tree. It is based on the philosophy that the data structure should act as a hierarchical geometrical model of the data as opposed to a simple decomposition of the data that does not use its intrinsic geometry. In experiments, we find that GNAT's outperform previous data structures ina number of applications.

Copyright © 1995 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Umeshwar Dayal, Peter M. D. Gray, Shojiro Nishio (Eds.): VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. Morgan Kaufmann 1995, ISBN 1-55860-379-4
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[BFR+93]
...
[BK73]
Walter A. Burkhard, Robert M. Keller: Some Approaches to Best-Match File Searching. Commun. ACM 16(4): 230-236(1973) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FN75]
Keinosuke Fukunaga, Patrenahalli M. Narendra: A Branch and Bound Algorithms for Computing k-nearest Neighbors. IEEE Trans. Computers 24(7): 750-753(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FS82]
...
[HKR93]
...
[SW90]
Dennis Shasha, Jason Tsong-Li Wang: New Techniques for Best-Match Retrieval. ACM Trans. Inf. Syst. 8(2): 140-158(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Uhl91]
Jeffrey K. Uhlmann: Satisfying General Proximity/Similarity Queries with Metric Trees. Inf. Process. Lett. 40(4): 175-179(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ukk92]
Esko Ukkonen: Approximate String Matching with q-grams and Maximal Matches. Theor. Comput. Sci. 92(1): 191-211(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Yia93]
...

Copyright © Tue Mar 16 02:22:05 2010 by Michael Ley (ley@uni-trier.de)