Welcome to D
SIGMOD'00
PODS'00
= PODS'00 Webs
= Plenary Talk
<<< = PODS'00 Pape>>>
SIGMOD Recor
CIKM 2000/CI
COMAD 2000
Data Enginee
DL 2000
DPDJ
EDBT 2000
Hypertext 20
ICDE 2000
KDD 2000
KDD Explorat
KRDB 2000
SBBD 2000
SIGIR 2000
SIGIR Forum
SSDBM 2000
TODS
VLDB'00
VLDBJ

Indexing the Edges - A Simple and Yet Efficient Approach to High-Dimensional Indexing


Beng Chin Ooi, Kian-Lee Tan, Cui Yu, and Stéphane Bressan

  View Paper (PDF)  

Return to Indexing / Transactions


Abstract

In this paper, we propose a new tunable index scheme, called iMinMax(), that maps points in high dimensional spaces to single dimension values determined by their maximum or minimum values among all dimensions. By varying the tuning "knob" , we can obtain different family of iMinMax structures that are optimized for different distributions of data sets. For a d-dimensional space, a range query need to be transformed into d subqueries. However, some of these subqueries can be pruned away without evaluation, further enhancing the efficiency of the scheme. Experimental results show that iMinMax() can outperform the more complex Pyramid technique by a wide margin.


References


Note: References link to DBLP on the Web.

[1]
Elisa Bertino , Beng Chin Ooi , Ron Sacks-Davis , Kian-Lee Tan , Justin Zobel , Boris Shidlovsky , Barbara Catania : Indexing Techniques for Advanced Database Systems. Kluwer 1997, ISBN 0-7923-9985-4
[2]
Antonin Guttman : R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984 : 47-57
[3]
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
[4]
Roger Weber , Hans-Jörg Schek , Stephen Blott : A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. VLDB 1998 : 194-205
[5]
Stefan Berchtold , Christian Böhm , Hans-Peter Kriegel : The Pyramid-Tree: Breaking the Curse of Dimensionality. SIGMOD Conference 1998 : 142-153
[6]
Douglas Comer : The Ubiquitous B-Tree. Computing Surveys 11(2) : 121-137(1979)

Referenced by

  1. Mong-Li Lee , Masaru Kitsuregawa , Beng Chin Ooi , Kian-Lee Tan , Anirban Mondal : Towards Self-Tuning Data Placement in Parallel Database Systems. SIGMOD Conference 2000 : 225-236

BIBTEX


@inproceedings{DBLP:conf/pods/YuOB00,
  author    = {Beng Chin Ooi and
                Kian-Lee Tan and
                Cui Yu and
                St{\'e}phane Bressan},
   title     = {Indexing the Edges - A Simple and Yet Efficient Approach to High-Dimensional
                Indexing},
   booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium
                on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,
                USA},
   publisher = {ACM},
   year      = {2000},
   isbn      = {1-58113-214-X},
   pages     = {166-174},
   crossref  = {DBLP:conf/pods/00},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


DiSC'01 Copyright ©2002 ACM Inc.