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.00013799572
Overall Rank: 803 | 94.62%
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.0004024707
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00032945275
598	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00015711108
2,080	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS	9.058838e-05
2,693	Identifying Similarities, Periodicities and Bursts for Online Search Queries	2004	SIGMOD	8.1107645e-05
4,321	Data Series Progressive Similarity Search with Probabilistic Quality Guarantees	2020	SIGMOD	6.6519404e-05
4,643	Pivot-based Metric Indexing	2017	VLDB	6.4734189e-05
4,749	Finding Near Neighbors Through Cluster Pruning	2007	PODS	6.423839e-05
5,432	GTS: GPU-based Tree Index for Fast Similarity Search	2024	SIGMOD	6.1176015e-05
7,414	LiteHST: A Tree Embedding based Method for Similarity Search	2023	SIGMOD	5.5161476e-05
8,655	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	5.2794257e-05
8,813	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	5.2570736e-05
10,483	Adaptive Outlier Detection over Data Stream	2026	SIGMOD	4.9605343e-05
10,728	LM-Tree: A Hybrid Learned Index for Similarity Search in Metric Spaces	2026	SIGMOD	4.9605343e-05
11,932	DESIRE: An Efficient Dynamic Cluster-based Forest Indexing for Similarity Search in Multi-Metric Spaces	2022	VLDB	4.9605343e-05
13,155	The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces	2003	VLDB	4.9605343e-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,637	Efficient Geometry-based Similarity Search of 3D Spatial Databases	1999	SIGMOD
2	28	Nearest Neighbor Queries	1995	SIGMOD
3	3,332	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB
4	3,784	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
5	6,941	GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces	2025	VLDB
6	2,129	What is the nearest neighbor in high dimensional spaces?	2000	VLDB
7	598	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,330	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD