An adaptive and efficient dimensionality reduction algorithm for high-dimensional indexing

Jin, Hui, Ooi, Beng Chin, Shen, Heng Tao, Yu, Cui and Zhou, Ao Ying (2003). An adaptive and efficient dimensionality reduction algorithm for high-dimensional indexing. In: Umeshwar Dayal, Krithi Ramamritham and T. M. Vijayaraman, Proceedings of the 19th International Conference on Data Engineering (ICDE 2003). 19th International Conference on Data Engineering (ICDE 2003), Bangalore, India, (87-87). March 5-8 2003.


Author Jin, Hui
Ooi, Beng Chin
Shen, Heng Tao
Yu, Cui
Zhou, Ao Ying
Title of paper An adaptive and efficient dimensionality reduction algorithm for high-dimensional indexing
Conference name 19th International Conference on Data Engineering (ICDE 2003)
Conference location Bangalore, India
Conference dates March 5-8 2003
Convener IEEE Computer Society
Proceedings title Proceedings of the 19th International Conference on Data Engineering (ICDE 2003)
Place of Publication Piscataway, NJ., U.S.A.
Publisher IEEE Computer Society
Publication Year 2003
Sub-type Fully published paper
DOI 10.1109/ICDE.2003.1260784
ISBN 0-7803-7665-X
Editor Umeshwar Dayal
Krithi Ramamritham
T. M. Vijayaraman
Start page 87
End page 87
Total pages 1
Language eng
Abstract/Summary The notorious iodimensionality curseln is a well-known phenomenon for any multi-dimensional indexes attempting to scale up to high dimensions. One well known approach to overcoming degradation in performance with respect to increasing dimensions is to reduce the dimensionality of the original dataset before constructing the index. However, identifying the correlation among the dimensions and effectively reducing them is a challenging task. In this paper, we present an adaptive Multi-level Mahalanobis-based Dimensionality Reduction (MMDR) technique for high-dimensional indexing. Our MMDR technique has three notable features compared to existing methods. First, it discovers elliptical clusters using only the low-dimensional subspaces. Second, data points in the different axis systems are indexed using a single B+-tree. Third, our technique is highly scalable in terms of data size and dimensionality. An extensive performance study using both real and synthetic datasets was conducted, and the results show that our technique not only achieves higher precision, but also enables queries to be processed efficiently.
Subjects 080604 Database Management
Q-Index Code E1
Q-Index Status Provisional Code
Institutional Status Unknown

 
Versions
Version Filter Type
Citation counts: Google Scholar Search Google Scholar
Access Statistics: 58 Abstract Views  -  Detailed Statistics
Created: Wed, 25 Feb 2009, 13:28:56 EST by Maryanne Watson on behalf of Faculty Of Engineering, Architecture & Info Tech