DBScholar

Back to papers

A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space

Summary: New cost model for nearest-neighbor search that incorporates boundary effects, enabling accurate expected query-time estimates across arbitrary high dimensions, data distributions, and index structures. Generalizes a quadtree-derived NN algorithm (proves optimal) and empirically validates superior estimation accuracy for Hilbert and X-tree on synthetic and real data. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1104
Venue
PODS
Year
1997
Pagerank
0.00012027131
Overall Rank
1,137 | 92.21%
DOI
10.1145/263661.263671

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{berchtold_pods97,
        address = {New York, NY, USA},
        series = {{PODS} '97},
        title = {{A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space}},
        url = {https://dl.acm.org/doi/10.1145/263661.263671},
        doi = {10.1145/263661.263671},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Berchtold, Stefan and Böhm, Christian and Keim, Daniel A. and Kriegel, Hans-Peter},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank Citing Paper Year Venue Pagerank
304 Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications 1998 SIGMOD 0.00021917388
796 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.00013932561
864 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00013522522
1,281 Continuous Nearest Neighbor Search 2002 VLDB 0.00011349245
1,486 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.00010625076
1,561 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010361147
1,646 Fast Algorithms for Projected Clustering 1999 SIGMOD 0.00010128564
1,776 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.7853414e-05
1,778 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.7769047e-05
1,993 Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data 2001 SIGMOD 9.3421788e-05
2,101 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 9.1657486e-05
2,426 Active Storage For Large-Scale Data Mining and Multimedia 1998 VLDB 8.5987569e-05
2,734 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 8.190416e-05
3,562 Location-based Spatial Queries 2003 SIGMOD 7.3080612e-05
3,581 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 7.2873782e-05
3,866 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 7.061829e-05
5,838 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 6.0702428e-05
5,857 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 6.0644613e-05
7,681 Efficient Concurrency Control in Multidimensional Access Methods 1999 SIGMOD 5.5683442e-05
9,115 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 5.3215443e-05
9,417 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.2740525e-05
11,199 Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results 2024 SIGMOD 5.093636e-05
11,408 Closest Pairs Search Over Data Stream 2023 SIGMOD 5.093636e-05
11,751 On the I/O Complexity of the k-Nearest Neighbors Problem 2020 PODS 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank Cited Paper Year Venue Pagerank
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.001157935
28 Nearest Neighbor Queries 1995 SIGMOD 0.00052102434
85 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00035405879
350 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00020425134
1,202 Fractals for Secondary Key Retrieval 1989 PODS 0.00011672157
4,070 Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension 1996 VLDB 6.9272604e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 6,133 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB
2 1,934 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB
3 3,282 Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches 2000 VLDB
4 21 Similarity Search in High Dimensions via Hashing 1999 VLDB
5 1,605 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB
6 1,281 Continuous Nearest Neighbor Search 2002 VLDB
7 705 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB
8 581 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD
9 2,101 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS
10 2,158 What is the nearest neighbor in high dimensional spaces? 2000 VLDB