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
h710511504e7024a6
Venue
SIGMOD
Year
1998
Pagerank
0.0001325914
Overall Rank
886 | 94.05%
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
342 The Onion Technique: Indexing for Linear Optimization Queries 2000 SIGMOD 0.00020530255
650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015149775
1,077 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012154948
1,774 ArrayStore: A Storage Manager for Complex Parallel Array Processing 2011 SIGMOD 9.6688719e-05
1,878 Effectively Learning Spatial Indices 2020 VLDB 9.4451309e-05
2,730 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 8.0861221e-05
2,911 Indexing Large Trajectory Data Sets With SETI* 2003 CIDR 7.8720638e-05
3,016 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.7483267e-05
3,182 General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows 2002 SIGMOD 7.561954e-05
3,230 Similarity Query Processing for High-Dimensional Data 2020 VLDB 7.5056037e-05
3,333 FTW: Fast Similarity Search under the Time Warping Distance 2005 PODS 7.4153527e-05
4,714 Towards Effective Indexing for Very Large Video Sequence Database 2005 SIGMOD 6.4555106e-05
5,444 Pigeonring: A Principle for Faster Thresholded Similarity Search 2019 VLDB 6.1268526e-05
5,722 Ranked Subsequence Matching in Time-Series Databases 2007 VLDB 6.0183253e-05
6,943 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 5.6380615e-05
7,023 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 5.6186604e-05
8,818 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 5.2700772e-05
9,186 Indexing Images in Oracle8i 2000 SIGMOD 5.2114454e-05
9,544 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 5.1611019e-05
10,206 Continuous Query Processing in Data Streams Using Duality of Data and Queries 2006 SIGMOD 5.059736e-05
12,579 QuEval: Beyond high-dimensional indexing à la carte 2013 VLDB 4.9793485e-05
13,201 GHOST: Fine Granularity Buffering of Index Pages 1999 VLDB 4.9793485e-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.0011405675
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.0008122792
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034860244
279 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022308048
358 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00020019939
1,157 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00011774968
1,813 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.5801503e-05
3,137 Data Warehousing and OLAP for Decision Support 1997 SIGMOD 7.6077413e-05
3,887 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9458013e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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