Near Neighbor Search in Large Metric Spaces

Summary: Introduces GNAT, a Geometric Near-neighbor Access Tree for approximate near-neighbor search in high-dimensional metric spaces with costly distance evaluations. It emphasizes geometry over simple partitions and empirically beats prior structures. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8300
Venue: VLDB
Year: 1995
Pagerank: 0.00017772684
Overall Rank: 708 | 95.08%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Sergey Brin

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.0005181666
125	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00044847972
575	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00019882723
1,811	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS	0.00010467197
2,477	Identifying Similarities, Periodicities and Bursts for Online Search Queries	2004	SIGMOD	8.6941234e-05
4,090	Finding Near Neighbors Through Cluster Pruning	2007	PODS	6.4577834e-05
4,536	Data Series Progressive Similarity Search with Probabilistic Quality Guarantees	2020	SIGMOD	6.104642e-05
4,985	Pivot-based Metric Indexing	2017	VLDB	5.7856648e-05
7,654	LiteHST: A Tree Embedding based Method for Similarity Search	2023	SIGMOD	4.687476e-05
8,171	GTS: GPU-based Tree Index for Fast Similarity Search	2024	SIGMOD	4.5688498e-05
8,693	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	4.466142e-05
10,180	LM-Tree: A Hybrid Learned Index for Similarity Search in Metric Spaces	2026	SIGMOD	4.1945683e-05
10,957	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	4.1945683e-05
11,375	DESIRE: An Efficient Dynamic Cluster-based Forest Indexing for Similarity Search in Multi-Metric Spaces	2022	VLDB	4.1945683e-05
12,625	The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces	2003	VLDB	4.1945683e-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	Pagerank
8,201	Efficient Geometry-based Similarity Search of 3D Spatial Databases	1999	SIGMOD	4.5599694e-05
47	Nearest Neighbor Queries	1995	SIGMOD	0.0007015885
3,061	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB	7.6382127e-05
4,070	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.4784181e-05
7,837	GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces	2025	VLDB	4.6379694e-05
2,107	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.5330494e-05
575	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00019882723
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.0005181666
3,579	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	6.9502303e-05