Published Articles >> Table of Contents >> Abstract

20th International Conference on Data Engineering (ICDE'04)   p. 6
LDC: Enabling Search By Partial Distance In A Hyper-Dimensional Space
Nick Koudas, AT&T Labs Research, Shannon Laboratory Florham Park, USA
Beng Chin Ooi, National University of Singapore
Heng Tao Shen, National University of Singapore
Anthony K. H. Tung, National University of Singapore

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDE.2004.1319980
Send link to a friend

Abstract
Recent advances in research fields like multimedia and bioinformatics have brought about a new generation of hyper-dimensional databases which can contain hundreds or even thousands of dimensions. Such hyper-dimensional databases pose significant problems to existing high-dimensional indexing techniques which have been developed for indexing databases with (commonly) less than a hundred dimensions. To support efficient querying and retrieval on hyper-dimensional databases, we propose a methodology called Local Digital Coding (LDC) which can support k-nearest neighbors (KNN) queries on hyper-dimensional databases and yet co-exist with ubiquitous indices, such as B+-trees. LDC extracts a simple bitmap representation called Digital Code(DC) for each point in the database.Pruning during KNN search is performed by dynamically selecting only a subset of the bits from the DC based on which subsequent comparisons are performed. In doing so, expensive operations involved in computing L-norm distance functions between hyper-dimensional data can be avoided. Extensive experiments are conducted to show that our methodology offers significant performance advantages over other existing indexing methods on both real life and synthetic hyper-dimensional datasets.
Back to Top Additional Information
Citation:  Nick Koudas, Beng Chin Ooi, Heng Tao Shen, Anthony K. H. Tung, "LDC: Enabling Search By Partial Distance In A Hyper-Dimensional Space," icde, p. 6,  20th International Conference on Data Engineering (ICDE'04),  2004