Database Paper Browser

Back to papers

Indexing the Distance: An Efficient Method to KNN Processing

Summary: Proposes iDistance for high-D KNN: partition data, assign per-partition reference, project to 1D by distance to the reference, and index with a B+-tree. Partitioning and reference choice adapt the index to data; experiments confirm efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
8766
Venue
VLDB
Year
2001
Pagerank
7.2516103e-05
Overall Rank
3,300 | 77.05%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank Citing Paper Year Venue Pagerank
1,010 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014652858
1,275 Continuous Nearest Neighbor Search 2002 VLDB 0.00012883899
1,774 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB 0.00010604097
1,931 Efficient Processing of k Nearest Neighbor Joins using MapReduce 2012 VLDB 0.00010040427
3,018 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.7002798e-05
3,056 DSH: Data Sensitive Hashing for High-Dimensional k-NN Search 2014 SIGMOD 7.6432146e-05
3,275 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.2897998e-05
3,800 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 6.7585633e-05
4,501 TASTI: Semantic Indexes for Machine Learning-based Queries over Unstructured Data 2022 SIGMOD 6.137686e-05
4,666 Towards Effective Indexing for Very Large Video Sequence Database 2005 SIGMOD 6.0124339e-05
5,224 Neighbor-Sensitive Hashing 2016 VLDB 5.6197981e-05
5,310 Online Event-driven Subsequence Matching over Financial Data Streams 2004 SIGMOD 5.5753015e-05
5,636 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 5.3981191e-05
7,999 TI: An Efficient Indexing Mechanism for Real-Time Search on Tweets 2011 SIGMOD 4.6100392e-05
8,562 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 4.4937074e-05
12,227 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 4.1945683e-05
12,484 Peer-to-Peer Similarity Search in Metric Spaces 2007 VLDB 4.1945683e-05
12,511 Using High Dimensional Indexes to Support Relevance Feedback Based Interactive Images Retrieval 2006 VLDB 4.1945683e-05
12,563 Database-Inspired Search 2005 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank Cited Paper Year Venue Pagerank
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032169493
33 BIRCH: An Efficient Data Clustering Method for Very Large Databases 1996 SIGMOD 0.00077324389
79 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00056242144
91 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.0005181666
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.0004429571
284 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00028994728
341 CURE: An Efficient Clustering Algorithm for Large Databases 1998 SIGMOD 0.00026810548
575 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00019882723
931 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00015238406
1,806 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 0.00010490769
1,925 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010073407
3,061 Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches 2000 VLDB 7.6382127e-05
7,005 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 4.8654221e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,183 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00013455596
575 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00019882723
4,070 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 6.4784181e-05
1,933 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010038508
7,791 Similarity Search on Bregman Divergence: Towards Non-Metric Indexing 2009 VLDB 4.6502309e-05
11,554 On the I/O Complexity of the k-Nearest Neighbors Problem 2020 PODS 4.1945683e-05
7,239 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB 4.792836e-05
3,579 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 6.9502303e-05
1,010 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014652858
8,562 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 4.4937074e-05