|
|
|
@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}
}
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.
