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: hfa11f42c57dfbbd0
Venue: VLDB
Year: 1995
Pagerank: 0.00013847746
Overall Rank: 802 | 94.61%
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.00040370171
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.0003305531
597	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00015766567
2,079	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS	9.0775779e-05
2,683	Identifying Similarities, Periodicities and Bursts for Online Search Queries	2004	SIGMOD	8.1393112e-05
4,304	Data Series Progressive Similarity Search with Probabilistic Quality Guarantees	2020	SIGMOD	6.6771697e-05
4,639	Pivot-based Metric Indexing	2017	VLDB	6.4903275e-05
4,728	Finding Near Neighbors Through Cluster Pruning	2007	PODS	6.4473669e-05
5,411	GTS: GPU-based Tree Index for Fast Similarity Search	2024	SIGMOD	6.1408042e-05
7,395	LiteHST: A Tree Embedding based Method for Similarity Search	2023	SIGMOD	5.5370691e-05
8,629	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	5.2994494e-05
8,786	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	5.2768554e-05
10,405	Adaptive Outlier Detection over Data Stream	2026	SIGMOD	4.9793485e-05
10,656	LM-Tree: A Hybrid Learned Index for Similarity Search in Metric Spaces	2026	SIGMOD	4.9793485e-05
11,882	DESIRE: An Efficient Dynamic Cluster-based Forest Indexing for Similarity Search in Multi-Metric Spaces	2022	VLDB	4.9793485e-05
13,108	The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces	2003	VLDB	4.9793485e-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,611	Efficient Geometry-based Similarity Search of 3D Spatial Databases	1999	SIGMOD
2	28	Nearest Neighbor Queries	1995	SIGMOD
3	3,320	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB
4	3,774	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
5	6,919	GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces	2025	VLDB
6	2,113	What is the nearest neighbor in high dimensional spaces?	2000	VLDB
7	597	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD
8	20	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,325	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD