Stanford InfoLab Publication Server

Near Neighbor Search in Large Metric Spaces

Brin, S. (1995) Near Neighbor Search in Large Metric Spaces. In: 21th International Conference on Very Large Data Bases (VLDB 1995), September 11-15, 1995, Zurich, Switzerland.




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

Item Type:Conference or Workshop Item (Paper)
Subjects:Computer Science > Databases and the Web
Projects:Digital Libraries
Related URLs:Project Homepage
ID Code:113
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:14 Jan 2009 14:05

Download statistics

Repository Staff Only: item control page