Near Neighbor Search in Large Metric Spaces

Summary: Introduces GNAT, a geometric, hierarchical index for approximate nearest-neighbor search in high-dimensional metric spaces with costly distance evaluations. Unlike decomposition-based structures, it models intrinsic data geometry and outperforms prior methods experimentally. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 8491
Venue: VLDB
Year: 1995
Pagerank: 0.00014069958
Overall Rank: 784 | 94.63%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Sergey Brin (Stanford University)

BibTeX Citation

@article{brin_vldb95,
        title = {{Near Neighbor Search in Large Metric Spaces}},
        author = {Brin, Sergey},
        journal = {PVLDB},
        series = {{VLDB} '95},
        pages = {574},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040719947
107	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00033511706
592	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00016029789
2,101	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS	9.1657486e-05
2,659	Identifying Similarities, Periodicities and Bursts for Online Search Queries	2004	SIGMOD	8.286986e-05
4,212	Data Series Progressive Similarity Search with Probabilistic Quality Guarantees	2020	SIGMOD	6.8283344e-05
4,627	Pivot-based Metric Indexing	2017	VLDB	6.5963674e-05
4,657	Finding Near Neighbors Through Cluster Pruning	2007	PODS	6.5830079e-05
7,376	LiteHST: A Tree Embedding based Method for Similarity Search	2023	SIGMOD	5.6298131e-05
7,474	GTS: GPU-based Tree Index for Fast Similarity Search	2024	SIGMOD	5.6093517e-05
8,848	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	5.3577837e-05
8,911	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	5.3483178e-05
10,189	Adaptive Outlier Detection over Data Stream	2026	SIGMOD	5.093636e-05
10,469	LM-Tree: A Hybrid Learned Index for Similarity Search in Metric Spaces	2026	SIGMOD	5.093636e-05
11,573	DESIRE: An Efficient Dynamic Cluster-based Forest Indexing for Similarity Search in Multi-Metric Spaces	2022	VLDB	5.093636e-05
12,818	The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces	2003	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,442	Efficient Geometry-based Similarity Search of 3D Spatial Databases	1999	SIGMOD
2	28	Nearest Neighbor Queries	1995	SIGMOD
3	3,282	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB
4	3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
5	7,124	GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces	2025	VLDB
6	2,158	What is the nearest neighbor in high dimensional spaces?	2000	VLDB
7	592	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD
8	21	Similarity Search in High Dimensions via Hashing	1999	VLDB
9	56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB
10	3,363	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD