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: 8301
Venue: VLDB
Year: 1995
Pagerank: 0.00017770532
Overall Rank: 707 | 95.09%
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.00051785122
125	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00044946098
574	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.0001987713
1,808	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS	0.00010476269
2,478	Identifying Similarities, Periodicities and Bursts for Online Search Queries	2004	SIGMOD	8.6866662e-05
4,096	Finding Near Neighbors Through Cluster Pruning	2007	PODS	6.4506806e-05
4,524	Data Series Progressive Similarity Search with Probabilistic Quality Guarantees	2020	SIGMOD	6.1091797e-05
5,086	Pivot-based Metric Indexing	2017	VLDB	5.7036022e-05
7,654	LiteHST: A Tree Embedding based Method for Similarity Search	2023	SIGMOD	4.6831082e-05
8,167	GTS: GPU-based Tree Index for Fast Similarity Search	2024	SIGMOD	4.567569e-05
8,687	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	4.4621895e-05
10,180	LM-Tree: A Hybrid Learned Index for Similarity Search in Metric Spaces	2026	SIGMOD	4.1905499e-05
10,960	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	4.1905499e-05
11,377	DESIRE: An Efficient Dynamic Cluster-based Forest Indexing for Similarity Search in Multi-Metric Spaces	2022	VLDB	4.1905499e-05
12,634	The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces	2003	VLDB	4.1905499e-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,200	Efficient Geometry-based Similarity Search of 3D Spatial Databases	1999	SIGMOD	4.5556029e-05
48	Nearest Neighbor Queries	1995	SIGMOD	0.0006954126
3,062	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB	7.6348035e-05
4,035	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	6.5111577e-05
7,843	GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces	2025	VLDB	4.6335219e-05
2,099	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.5429949e-05
574	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.0001987713
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076824554
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00051785122
3,574	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD	6.9520978e-05