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
h1208163e77371bee
Venue
PODS
Year
1997
Pagerank
0.0001176973
Overall Rank
1,157 | 92.23%
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
308 Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications 1998 SIGMOD 0.00021463972
826 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.000136317
886 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00013253709
1,304 Continuous Nearest Neighbor Search 2002 VLDB 0.00011099525
1,518 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.0001039208
1,590 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010134811
1,679 Fast Algorithms for Projected Clustering 1999 SIGMOD 9.90334e-05
1,793 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.6212318e-05
1,814 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.5757565e-05
1,998 Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data 2001 SIGMOD 9.2123795e-05
2,077 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 9.0758123e-05
2,449 Active Storage For Large-Scale Data Mining and Multimedia 1998 VLDB 8.4460399e-05
2,730 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 8.0842027e-05
3,639 Location-based Spatial Queries 2003 SIGMOD 7.1412645e-05
3,659 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 7.1210394e-05
3,886 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9430152e-05
5,958 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.931243e-05
5,965 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 5.9302348e-05
7,841 Efficient Concurrency Control in Multidimensional Access Methods 1999 SIGMOD 5.4409195e-05
9,298 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 5.1997281e-05
9,605 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.1533056e-05
11,547 Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results 2024 SIGMOD 4.9769913e-05
11,728 Closest Pairs Search Over Data Stream 2023 SIGMOD 4.9769913e-05
12,060 On the I/O Complexity of the k-Nearest Neighbors Problem 2020 PODS 4.9769913e-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.0011402175
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051292389
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034847854
358 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00020011298
1,228 Fractals for Secondary Key Retrieval 1989 PODS 0.00011427053
4,154 Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension 1996 VLDB 6.7730465e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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