Database Paper Browser

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
1105
Venue
PODS
Year
1997
Pagerank
0.00013455596
Overall Rank
1,183 | 91.78%
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
277 Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications 1998 SIGMOD 0.00029311426
802 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.00016502317
931 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00015238406
1,275 Continuous Nearest Neighbor Search 2002 VLDB 0.00012883899
1,502 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00011643406
1,586 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.00011250856
1,595 Fast Algorithms for Projected Clustering 1999 SIGMOD 0.00011222442
1,755 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 0.00010669106
1,811 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 0.00010467197
1,925 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010073407
2,089 Active Storage For Large-Scale Data Mining and Multimedia 1998 VLDB 9.5657612e-05
2,281 Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data 2001 SIGMOD 9.1077704e-05
3,183 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 7.4228241e-05
3,555 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9772546e-05
3,800 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 6.7585633e-05
3,814 Location-based Spatial Queries 2003 SIGMOD 6.7341058e-05
5,882 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.2892937e-05
6,051 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 5.2347385e-05
7,651 Efficient Concurrency Control in Multidimensional Access Methods 1999 SIGMOD 4.6876337e-05
8,889 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 4.4278238e-05
9,143 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 4.3850454e-05
10,986 Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results 2024 SIGMOD 4.1945683e-05
11,207 Closest Pairs Search Over Data Stream 2023 SIGMOD 4.1945683e-05
11,554 On the I/O Complexity of the k-Nearest Neighbors Problem 2020 PODS 4.1945683e-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
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016162015
47 Nearest Neighbor Queries 1995 SIGMOD 0.0007015885
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
1,249 Fractals for Secondary Key Retrieval 1989 PODS 0.00013044758
3,527 Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension 1996 VLDB 7.0073154e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,971 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 7.7970531e-05
7,239 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB 4.792836e-05
3,061 Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches 2000 VLDB 7.6382127e-05
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076637636
1,542 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 0.00011456321
1,275 Continuous Nearest Neighbor Search 2002 VLDB 0.00012883899
1,010 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014652858
682 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00018201541
1,811 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 0.00010467197
2,107 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 9.5330494e-05