The Pyramid-Technique: Towards Breaking the Curse of Dimensionality.
Stefan Berchtold, Christian Böhm, Hans-Peter Kriegel:
The Pyramid-Technique: Towards Breaking the Curse of Dimensionality.
SIGMOD Conference 1998: 142-153@inproceedings{DBLP:conf/sigmod/BerchtoldBK98,
author = {Stefan Berchtold and
Christian B{\"o}hm and
Hans-Peter Kriegel},
editor = {Laura M. Haas and
Ashutosh Tiwary},
title = {The Pyramid-Technique: Towards Breaking the Curse of Dimensionality},
booktitle = {SIGMOD 1998, Proceedings ACM SIGMOD International Conference
on Management of Data, June 2-4, 1998, Seattle, Washington, USA},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-995-5},
pages = {142-153},
ee = {http://doi.acm.org/10.1145/276304.276318, db/conf/sigmod/BerchtoldBK98.html},
crossref = {DBLP:conf/sigmod/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
In this paper, we propose the Pyramid-Technique,
a new indexing method for high-dimensional data spaces.
The Pyramid-Technique is highly adapted to range query processing using the maximum metric Lmax.
In contrast to all other index structures,
the performance of the Pyramid-Technique does not deteriorate when processing range queries on data of higher dimensionality.
The Pyramid-Technique is based on a special partitioning strategy which is optimized for high-dimensional data.
The basic idea is to divide the data space first into 2d
pyramids sharing the center point of the space as a top.
In a second step, the single pyramids are cut into slices parallel to the basis of the pyramid.
These slices form the data pages.
Furthermore, we show that this partition provides a mapping from the given d-dimensional space to a 1-dimensional space.
Therefore, we are able to use a B+-tree to manage the transformed data.
As an analytical evaluation of our technique for hypercube range queries and uniform data distribution shows,
the Pyramid-Technique clearly outperforms index structures using other partitioning strategies.
To demonstrate the practical relevance of our technique,
we experimentally compared the Pyramid-Technique with the X-tree,
the Hilbert R-tree,
and the Linear Scan.
The results of our experiments using both,
synthetic and real data,
demonstrate that the Pyramid-Technique outperforms the X-tree and the Hilbert R-tree by a factor of up to 14 (number of page accesses) and up to 2500 (total elapsed time) for range queries.
Copyright © 1998 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" and ...
Online Version (ACM WWW Account required): Full Text in PDF Format
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
Printed Edition
Laura M. Haas, Ashutosh Tiwary (Eds.):
SIGMOD 1998, Proceedings ACM SIGMOD International Conference on Management of Data, June 2-4, 1998, Seattle, Washington, USA.
ACM Press 1998, ISBN 0-89791-995-5 BibTeX
,
SIGMOD Record 27(2),
June 1998
Contents
[Abstract]
[Full Text (Postscript)]
References
- [1]
- Rudolf Bayer, Edward M. McCreight:
Organization and Maintenance of Large Ordered Indices.
Acta Inf. 1: 173-189(1972) BibTeX
- [2]
- Stefan Berchtold, Christian Böhm, Bernhard Braunmüller, Daniel A. Keim, Hans-Peter Kriegel:
Fast Parallel Similarity Search in Multimedia Databases.
SIGMOD Conference 1997: 1-12 BibTeX
- [3]
- Stefan Berchtold, Christian Böhm, Hans-Peter Kriegel:
Improving the Query Performance of High-Dimensional Index Structures by Bulk-Load Operations.
EDBT 1998: 216-230 BibTeX
- [4]
- ...
- [5]
- Stefan Berchtold, Christian Böhm, Daniel A. Keim, Hans-Peter Kriegel:
A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space.
PODS 1997: 78-86 BibTeX
- [6]
- Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel:
The X-tree : An Index Structure for High-Dimensional Data.
VLDB 1996: 28-39 BibTeX
- [7]
- Stefan Berchtold, Bernhard Ertl, Daniel A. Keim, Hans-Peter Kriegel, Thomas Seidl:
Fast Nearest Neighbor Search in High-Dimensional Space.
ICDE 1998: 209-218 BibTeX
- [8]
- ...
- [9]
- Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.
SIGMOD Conference 1990: 322-331 BibTeX
- [10]
- Douglas Comer:
The Ubiquitous B-Tree.
ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
- [11]
- Surajit Chaudhuri, Umeshwar Dayal:
Data Warehousing and OLAP for Decision Support (Tutorial).
SIGMOD Conference 1997: 507-508 BibTeX
- [12]
- Christos Faloutsos, Ron Barber, Myron Flickner, Jim Hafner, Wayne Niblack, Dragutin Petkovic, William Equitz:
Efficient and Effective Querying by Image Content.
J. Intell. Inf. Syst. 3(3/4): 231-262(1994) BibTeX
- [13]
- Christos Faloutsos, Pravin Bhagwat:
Declustering Using Fractals.
PDIS 1993: 18-25 BibTeX
- [14]
- Jerome H. Friedman, Jon Louis Bentley, Raphael A. Finkel:
An Algorithm for Finding Best Matches in Logarithmic Expected Time.
ACM Trans. Math. Softw. 3(3): 209-226(1977) BibTeX
- [15]
- Gísli R. Hjaltason, Hanan Samet:
Ranking in Spatial Databases.
SSD 1995: 83-95 BibTeX
- [16]
- H. V. Jagadish:
A Retrieval Technique for Similar Shapes.
SIGMOD Conference 1991: 208-217 BibTeX
- [17]
- David A. White, Ramesh Jain:
Similarity Indexing: Algorithms and Performance.
Storage and Retrieval for Image and Video Databases (SPIE) 1996: 62-73 BibTeX
- [18]
- Norio Katayama, Shin'ichi Satoh:
The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries.
SIGMOD Conference 1997: 369-380 BibTeX
- [19]
- King-Ip Lin, H. V. Jagadish, Christos Faloutsos:
The TV-Tree: An Index Structure for High-Dimensional Data.
VLDB J. 3(4): 517-542(1994) BibTeX
- [20]
- Rajiv Mehrotra, James E. Gary:
Feature-Based Retrieval of Similar Shapes.
ICDE 1993: 108-115 BibTeX
- [21]
- John T. Robinson:
The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes.
SIGMOD Conference 1981: 10-18 BibTeX
- [22]
- Thomas Seidl, Hans-Peter Kriegel:
Efficient User-Adaptable Similarity Search in Large Multimedia Databases.
VLDB 1997: 506-515 BibTeX
- [23]
- David A. White, Ramesh Jain:
Similarity Indexing with the SS-tree.
ICDE 1996: 516-523 BibTeX
Referenced by
- Charu C. Aggarwal, Alexander Hinneburg, Daniel A. Keim:
On the Surprising Behavior of Distance Metrics in High Dimensional Spaces.
ICDT 2001: 420-434
- Yuan-Chi Chang, Lawrence D. Bergman, Vittorio Castelli, Chung-Sheng Li, Ming-Ling Lo, John R. Smith:
The Onion Technique: Indexing for Linear Optimization Queries.
SIGMOD Conference 2000: 391-402
- Melliyal Annamalai, Rajiv Chopra, Samuel DeFazio:
Indexing Images in Oracle8i.
SIGMOD Conference 2000: 539-547
- Beng Chin Ooi, Kian-Lee Tan, Cui Yu, Stéphane Bressan:
Indexing the Edges - A Simple and Yet Efficient Approach to High-Dimensional Indexing.
PODS 2000: 166-174
- Christian Böhm, Hans-Peter Kriegel:
Dynamically Optimizing High-Dimensional Index Structures.
EDBT 2000: 36-50
- Cheng Hian Goh, Beng Chin Ooi, D. Sim, Kian-Lee Tan:
GHOST: Fine Granularity Buffering of Indexes.
VLDB 1999: 339-350
- Weidong Chen, Jyh-Herng Chow, You-Chin Fuh, Jean Grandbois, Michelle Jou, Nelson Mendonça Mattos, Brian T. Tran, Yun Wang:
High Level Indexing of User-Defined Types.
VLDB 1999: 554-564
- Ju-Hong Lee, Deok-Hwan Kim, Chin-Wan Chung:
Multi-dimensional Selectivity Estimation Using Compressed Histogram Information.
SIGMOD Conference 1999: 205-214
- Charu C. Aggarwal, Joel L. Wolf, Philip S. Yu:
A New Method for Similarity Indexing of Market Basket Data.
SIGMOD Conference 1999: 407-418
- Vijayshankar Raman:
Locality Preserving Dictionaries: Theory and Application to Clustering in Databases.
PODS 1999: 337-345
- Hakan Ferhatosmanoglu, Divyakant Agrawal, Amr El Abbadi:
Concentric Hyperspaces and Disk Allocation for Fast Parallel Range Searching.
ICDE 1999: 608-615
- Kaushik Chakrabarti, Sharad Mehrotra:
The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces.
ICDE 1999: 440-447
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:42 2009
