DBScholar

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
h751cabf5bc18a722
Venue
SIGMOD
Year
1998
Pagerank
0.00013588099
Overall Rank
828 | 94.46%
DOI
10.1145/276304.276319

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{seidl_sigmod98,
        title = {{Optimal Multi-Step k-Nearest Neighbor Search}},
        author = {Seidl, Thomas and Kriegel, Hans-Peter},
        series = {{SIGMOD} '98},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/276304.276319},
        url = {https://dl.acm.org/doi/10.1145/276304.276319},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank Citing Paper Year Venue Pagerank
198 Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases 2001 SIGMOD 0.00025558119
463 Query Processing in Spatial Network Databases 2003 VLDB 0.00017806376
616 Exact Indexing of Dynamic Time Warping 2002 VLDB 0.00015512487
647 Evaluating Top-k Selection Queries 1999 VLDB 0.00015165562
681 Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases 2004 VLDB 0.00014792999
1,075 Warping Indexes with Envelope Transforms for Query by Humming 2003 SIGMOD 0.00012129172
1,311 Continuous Nearest Neighbor Search 2002 VLDB 0.00011063629
2,416 S4: Top-k Spreadsheet-Style Search for Query Discovery 2015 SIGMOD 8.4837888e-05
3,118 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.6114853e-05
3,330 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 7.406702e-05
3,424 Efficient EMD-based Similarity Search in Multimedia Databases via Flexible Dimensionality Reduction 2008 SIGMOD 7.2974683e-05
3,666 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 7.0975312e-05
4,216 Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance 2010 VLDB 6.717297e-05
4,921 An Efficient Index Structure for String Databases 2001 VLDB 6.3441964e-05
5,737 Ranked Subsequence Matching in Time-Series Databases 2007 VLDB 5.9955855e-05
5,970 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.9116326e-05
6,552 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.7306642e-05
6,913 On Efficiently Searching Trajectories and Archival Data for Historical Similarities 2008 VLDB 5.6331177e-05
7,045 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 5.5975731e-05
8,308 Anticipatory DTW for Efficient Similarity Search in Time Series Databases 2009 VLDB 5.3417975e-05
8,844 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 5.2501688e-05
9,466 Using Sets of Feature Vectors for Similarity Search on Voxelized CAD Objects 2003 SIGMOD 5.1590473e-05
12,762 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 4.9605343e-05
13,152 A Shrinking-Based Approach for Multi-Dimensional Data Analysis 2003 VLDB 4.9605343e-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
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051134355
42 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00045609336
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.0004024707
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034749222
361 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00019948113
386 Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases 1995 VLDB 0.00019396455
490 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017397036
843 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013501136
1,161 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00011733128
1,825 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.5443954e-05
3,893 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9232481e-05
8,593 S3: Similarity Search in CAD Database Systems 1997 SIGMOD 5.2936565e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,129 What is the nearest neighbor in high dimensional spaces? 2000 VLDB
2 20 Similarity Search in High Dimensions via Hashing 1999 VLDB
3 1,165 Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases 2023 SIGMOD
4 10,332 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB
5 1,641 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB
6 674 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD
7 6,623 Similarity Search: A Matching Based Approach 2006 VLDB
8 3,784 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD
9 5,970 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB
10 3,330 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD