DBScholar

Back to papers

Indexing the Distance: An Efficient Method to KNN Processing

Summary: iDistance transforms high-dimensional KNN search into 1D range queries by partitioning data around reference points and indexing distance keys with a B+-tree. Flexible partition/reference selection adapts the index to data distribution, outperforming fixed metric indexes. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
hc2214f9a4c108c80
Venue
VLDB
Year
2001
Pagerank
7.7483267e-05
Overall Rank
3,016 | 79.73%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{yu_vldb01,
        title = {{Indexing the Distance: An Efficient Method to KNN Processing}},
        author = {Yu, Cui and Ooi, Beng Chin and Tan, Kian-Lee and Jagadish, H. V.},
        journal = {PVLDB},
        series = {{VLDB} '01},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank Citing Paper Year Venue Pagerank
650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015149775
1,304 Continuous Nearest Neighbor Search 2002 VLDB 0.00011104243
2,064 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB 9.0942902e-05
2,176 Efficient Processing of k Nearest Neighbor Joins using MapReduce 2012 VLDB 8.9159001e-05
2,505 DSH: Data Sensitive Hashing for High-Dimensional k-NN Search 2014 SIGMOD 8.3779738e-05
2,939 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.8340314e-05
3,253 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.4900624e-05
3,650 TASTI: Semantic Indexes for Machine Learning-based Queries over Unstructured Data 2022 SIGMOD 7.1341771e-05
3,658 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 7.1243855e-05
4,714 Towards Effective Indexing for Very Large Video Sequence Database 2005 SIGMOD 6.4555106e-05
4,856 Neighbor-Sensitive Hashing 2016 VLDB 6.3798143e-05
5,270 Online Event-driven Subsequence Matching over Financial Data Streams 2004 SIGMOD 6.2013771e-05
5,532 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 6.0932822e-05
8,192 TI: An Efficient Indexing Mechanism for Real-Time Search on Tweets 2011 SIGMOD 5.3804626e-05
8,927 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD 5.2559789e-05
12,713 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 4.9793485e-05
12,967 Peer-to-Peer Similarity Search in Metric Spaces 2007 VLDB 4.9793485e-05
12,994 Using High Dimensional Indexes to Support Relevance Feedback Based Interactive Images Retrieval 2006 VLDB 4.9793485e-05
13,046 Database-Inspired Search 2005 VLDB 4.9793485e-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.001992968
32 BIRCH: An Efficient Data Clustering Method for Very Large Databases 1996 SIGMOD 0.00049737458
45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.0004503446
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040370171
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034860244
279 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022308048
363 CURE: An Efficient Clustering Algorithm for Large Databases 1998 SIGMOD 0.00019987463
597 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00015766567
886 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.0001325914
1,634 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 0.0001001862
1,793 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.6235776e-05
3,320 Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches 2000 VLDB 7.4302233e-05
6,943 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 5.6380615e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,157 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS
2 597 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD
3 3,774 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD
4 1,571 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB
5 7,856 Similarity Search on Bregman Divergence: Towards Non-Metric Indexing 2009 VLDB
6 12,054 On the I/O Complexity of the k-Nearest Neighbors Problem 2020 PODS
7 6,239 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB
8 3,325 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD
9 650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB
10 8,927 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD