Database Paper Browser

Back to papers

Optimal Multi-Step k-Nearest Neighbor Search

Summary: Two-stage kNN search for high-dimensional, adaptable similarity functions. Novel multi-step algorithm guarantees the minimum candidate set, outperforming Korn et al. 1996 with up to 120× fewer candidates and 48× faster runtime. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
3010
Venue
SIGMOD
Year
1998
Pagerank
0.00016502317
Overall Rank
802 | 94.43%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank Citing Paper Year Venue Pagerank
243 Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases 2001 SIGMOD 0.00031074984
389 Query Processing in Spatial Network Databases 2003 VLDB 0.00024620268
598 Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases 2004 VLDB 0.00019474545
699 Exact Indexing of Dynamic Time Warping 2002 VLDB 0.00018015254
805 Evaluating Top-k Selection Queries 1999 VLDB 0.00016437265
1,061 Warping Indexes with Envelope Transforms for Query by Humming 2003 SIGMOD 0.00014368716
1,275 Continuous Nearest Neighbor Search 2002 VLDB 0.00012883899
2,576 S4: Top-k Spreadsheet-Style Search for Query Discovery 2015 SIGMOD 8.5112408e-05
3,199 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.3927291e-05
3,425 Efficient EMD-based Similarity Search in Multimedia Databases via Flexible Dimensionality Reduction 2008 SIGMOD 7.1077107e-05
3,579 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 6.9502303e-05
3,800 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 6.7585633e-05
4,333 An Efficient Index Structure for String Databases 2001 VLDB 6.2805237e-05
4,373 Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance 2010 VLDB 6.2443809e-05
5,878 Ranked Subsequence Matching in Time-Series Databases 2007 VLDB 5.2916009e-05
5,882 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.2892937e-05
6,500 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.0381573e-05
6,577 On Efficiently Searching Trajectories and Archival Data for Historical Similarities 2008 VLDB 5.0042166e-05
6,778 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 4.9284526e-05
8,139 Anticipatory DTW for Efficient Similarity Search in Time Series Databases 2009 VLDB 4.5770301e-05
8,647 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 4.4768766e-05
9,122 Using Sets of Feature Vectors for Similarity Search on Voxelized CAD Objects 2003 SIGMOD 4.3922853e-05
12,227 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 4.1945683e-05
12,622 A Shrinking-Based Approach for Multi-Dimensional Data Analysis 2003 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank Cited Paper Year Venue Pagerank
47 Nearest Neighbor Queries 1995 SIGMOD 0.0007015885
65 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00062029383
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
231 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00032163466
362 Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases 1995 VLDB 0.00025770385
471 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00022364776
665 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00018451109
1,183 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00013455596
1,755 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 0.00010669106
3,555 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9772546e-05
8,124 S3: Similarity Search in CAD Database Systems 1997 SIGMOD 4.5801104e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,107 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 9.5330494e-05
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076637636
2,023 Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases 2023 SIGMOD 9.7544991e-05
9,933 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB 4.2500258e-05
1,542 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 0.00011456321
709 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD 0.00017768547
6,164 Similarity Search: A Matching Based Approach 2006 VLDB 5.1733919e-05
4,070 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 6.4784181e-05
5,882 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.2892937e-05
3,579 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 6.9502303e-05