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.00013212387
Overall Rank
889 | 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
344 The Onion Technique: Indexing for Linear Optimization Queries 2000 SIGMOD 0.00020463118
650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015142453
1,080 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012114187
1,786 ArrayStore: A Storage Manager for Complex Parallel Array Processing 2011 SIGMOD 9.6344047e-05
1,884 Effectively Learning Spatial Indices 2020 VLDB 9.422145e-05
2,733 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 8.0653682e-05
2,923 Indexing Large Trajectory Data Sets With SETI* 2003 CIDR 7.8423791e-05
3,025 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.7214661e-05
3,192 General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows 2002 SIGMOD 7.5334132e-05
3,244 Similarity Query Processing for High-Dimensional Data 2020 VLDB 7.479122e-05
3,342 FTW: Fast Similarity Search under the Time Warping Distance 2005 PODS 7.3874144e-05
4,734 Towards Effective Indexing for Very Large Video Sequence Database 2005 SIGMOD 6.4311188e-05
5,467 Pigeonring: A Principle for Faster Thresholded Similarity Search 2019 VLDB 6.1037173e-05
5,737 Ranked Subsequence Matching in Time-Series Databases 2007 VLDB 5.9955855e-05
6,962 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 5.6181217e-05
7,045 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 5.5975731e-05
8,844 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 5.2501688e-05
9,216 Indexing Images in Oracle8i 2000 SIGMOD 5.1919937e-05
9,579 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 5.141601e-05
10,248 Continuous Query Processing in Data Streams Using Duality of Data and Queries 2006 SIGMOD 5.0412958e-05
12,628 QuEval: Beyond high-dimensional indexing à la carte 2013 VLDB 4.9605343e-05
13,248 GHOST: Fine Granularity Buffering of Index Pages 1999 VLDB 4.9605343e-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.0011386412
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.00081207565
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034749222
282 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022250557
361 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00019948113
1,161 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00011733128
1,825 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.5443954e-05
3,148 Data Warehousing and OLAP for Decision Support 1997 SIGMOD 7.5793138e-05
3,893 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9232481e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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