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.00013455619
Overall Rank
1,180 | 91.81%
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.00029356968
798 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.00016484637
929 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.0001523035
1,272 Continuous Nearest Neighbor Search 2002 VLDB 0.00012871443
1,499 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00011643887
1,568 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.0001131667
1,596 Fast Algorithms for Projected Clustering 1999 SIGMOD 0.00011210688
1,755 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 0.00010661725
1,808 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 0.00010476269
1,923 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010079134
2,093 Active Storage For Large-Scale Data Mining and Multimedia 1998 VLDB 9.5570993e-05
2,285 Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data 2001 SIGMOD 9.1097273e-05
3,199 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 7.3999833e-05
3,549 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9792126e-05
3,802 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 6.7524078e-05
3,815 Location-based Spatial Queries 2003 SIGMOD 6.7314038e-05
5,889 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.2842168e-05
6,055 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 5.2297716e-05
7,653 Efficient Concurrency Control in Multidimensional Access Methods 1999 SIGMOD 4.6831774e-05
8,890 A General Framework for Modeling and Processing Optimization Queries 2007 VLDB 4.4235206e-05
9,173 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 4.3807204e-05
10,989 Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results 2024 SIGMOD 4.1905499e-05
11,209 Closest Pairs Search Over Data Stream 2023 SIGMOD 4.1905499e-05
11,558 On the I/O Complexity of the k-Nearest Neighbors Problem 2020 PODS 4.1905499e-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.0016113151
48 Nearest Neighbor Queries 1995 SIGMOD 0.0006954126
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00044255276
231 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00032141918
1,250 Fractals for Secondary Key Retrieval 1989 PODS 0.00013037936
3,528 Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension 1996 VLDB 7.0033241e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
7,235 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB 4.7882389e-05
2,969 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 7.7955562e-05
3,062 Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches 2000 VLDB 7.6348035e-05
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076824554
1,535 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 0.00011461371
1,272 Continuous Nearest Neighbor Search 2002 VLDB 0.00012871443
1,013 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014632051
675 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00018304179
1,808 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 0.00010476269
2,099 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 9.5429949e-05