DBScholar

Back to papers

The Pyramid-Technique: Towards Breaking the Curse of Dimensionality

Summary: Pyramid-Technique: a high-dim index for L_max range queries, using 2^d pyramids with slices-as-pages. Maps to 1D for B+-tree indexing; experiments show up to 14x fewer page accesses and 2500x faster time vs X-tree/Hilbert R-tree. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
3071
Venue
SIGMOD
Year
1998
Pagerank
0.00013522522
Overall Rank
864 | 94.08%
DOI
10.1145/276304.276318

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{berchtold_sigmod98,
        title = {{The Pyramid-Technique: Towards Breaking the Curse of Dimensionality}},
        author = {Berchtold, Stefan and Böhm, Christian 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.276318},
        url = {https://dl.acm.org/doi/10.1145/276304.276318},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank Citing Paper Year Venue Pagerank
333 The Onion Technique: Indexing for Linear Optimization Queries 2000 SIGMOD 0.0002089582
705 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014829964
1,053 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012401532
1,742 ArrayStore: A Storage Manager for Complex Parallel Array Processing 2011 SIGMOD 9.8748669e-05
1,840 Effectively Learning Spatial Indices 2020 VLDB 9.6404567e-05
2,734 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 8.190416e-05
2,853 Indexing Large Trajectory Data Sets With SETI* 2003 CIDR 8.0383547e-05
2,979 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.8984588e-05
3,125 General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows 2002 SIGMOD 7.7344198e-05
3,267 FTW: Fast Similarity Search under the Time Warping Distance 2005 PODS 7.5816553e-05
3,310 Similarity Query Processing for High-Dimensional Data 2020 VLDB 7.5363562e-05
4,618 Towards Effective Indexing for Very Large Video Sequence Database 2005 SIGMOD 6.6036373e-05
5,592 Ranked Subsequence Matching in Time-Series Databases 2007 VLDB 6.1552372e-05
5,726 Pigeonring: A Principle for Faster Thresholded Similarity Search 2019 VLDB 6.1079184e-05
6,887 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 5.7457967e-05
6,894 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 5.744549e-05
8,655 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 5.3910353e-05
9,035 Indexing Images in Oracle8i 2000 SIGMOD 5.327414e-05
9,365 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 5.279561e-05
10,017 Continuous Query Processing in Data Streams Using Duality of Data and Queries 2006 SIGMOD 5.1758281e-05
12,288 QuEval: Beyond high-dimensional indexing à la carte 2013 VLDB 5.093636e-05
12,911 GHOST: Fine Granularity Buffering of Index Pages 1999 VLDB 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.00082404462
85 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00035405879
277 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022537944
350 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00020425134
1,137 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00012027131
1,776 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.7853414e-05
3,079 Data Warehousing and OLAP for Decision Support 1997 SIGMOD 7.7762802e-05
3,866 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 7.061829e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 4,730 A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries 1998 PODS
2 8,765 Contorting High Dimensional Data for Efficient Main Memory KNN Processing 2003 SIGMOD
3 8,570 Modeling High-Dimensional Index Structures using Sampling 2001 SIGMOD
4 12,940 Fast High-Dimensional Data Search in Incomplete Databases 1998 VLDB
5 8,680 The PH-Tree – A Space-Efficient Storage Structure and Multi-Dimensional Index 2014 SIGMOD
6 8,655 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD
7 1,529 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS
8 12,489 Worst-Case Efficient Range Search Indexing 2009 PODS
9 9,365 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR
10 6,894 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS