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
8767
Venue
VLDB
Year
2001
Pagerank
7.2450912e-05
Overall Rank
3,301 | 77.06%
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,013 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014632051
1,272 Continuous Nearest Neighbor Search 2002 VLDB 0.00012871443
1,766 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB 0.00010611043
1,927 Efficient Processing of k Nearest Neighbor Joins using MapReduce 2012 VLDB 0.00010062395
3,018 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.6995792e-05
3,019 DSH: Data Sensitive Hashing for High-Dimensional k-NN Search 2014 SIGMOD 7.699097e-05
3,278 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.2858181e-05
3,802 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 6.7524078e-05
4,492 TASTI: Semantic Indexes for Machine Learning-based Queries over Unstructured Data 2022 SIGMOD 6.1374891e-05
4,663 Towards Effective Indexing for Very Large Video Sequence Database 2005 SIGMOD 6.0066508e-05
5,218 Neighbor-Sensitive Hashing 2016 VLDB 5.6204105e-05
5,314 Online Event-driven Subsequence Matching over Financial Data Streams 2004 SIGMOD 5.5702825e-05
5,646 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 5.3924438e-05
8,001 TI: An Efficient Indexing Mechanism for Real-Time Search on Tweets 2011 SIGMOD 4.6056189e-05
8,559 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 4.4893996e-05
12,235 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 4.1905499e-05
12,493 Peer-to-Peer Similarity Search in Metric Spaces 2007 VLDB 4.1905499e-05
12,520 Using High Dimensional Indexes to Support Relevance Feedback Based Interactive Images Retrieval 2006 VLDB 4.1905499e-05
12,572 Database-Inspired Search 2005 VLDB 4.1905499e-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.0032118946
33 BIRCH: An Efficient Data Clustering Method for Very Large Databases 1996 SIGMOD 0.00077399244
78 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00056385781
91 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00051785122
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00044255276
301 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00028396714
340 CURE: An Efficient Clustering Algorithm for Large Databases 1998 SIGMOD 0.00026854084
574 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.0001987713
929 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.0001523035
1,802 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 0.0001048177
1,923 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010079134
3,062 Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches 2000 VLDB 7.6348035e-05
7,006 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 4.8606861e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
8,645 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 4.4725847e-05
574 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.0001987713
4,035 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 6.5111577e-05
1,924 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010075677
7,790 Similarity Search on Bregman Divergence: Towards Non-Metric Indexing 2009 VLDB 4.6458343e-05
11,558 On the I/O Complexity of the k-Nearest Neighbors Problem 2020 PODS 4.1905499e-05
7,235 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB 4.7882389e-05
3,574 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 6.9520978e-05
1,013 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014632051
8,559 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 4.4893996e-05