[ Pagewise preview ]
| Category | Value | ||
| Available via | http://dbpubs.stanford.edu/pub/1995-44 | ||
| Submitted on | 26th of February 2000 | ||
| Author | Brin, S. | ||
| Title | Near Neighbor Search in Large Metric Spaces | ||
| Date of publication | 1995 | ||
| Citation | S. Brin: Near Neighbor Search in Large Metric Spaces. Appeared in VLDB '95, 1995 | ||
| Language | English | ||
| Project | Digital Libraries | ||
| Type | Conference or Journal Paper | ||
| Subject group | Databases and the Web | ||
| 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 diffcult case where each data element is high dimensional, or more generally, is represented by a point in a large metric spaceand 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 in a number of applications. Keywords { near neighbor, metric space, approximate queries, data mining, Dirichlet domains, Voronoi regions | ||
| Fulltext source |
| Management of the document by | pubs@db.stanford.edu
| |
[ Pagewise preview ]