LDC: Enabling search by partial distance in a hyper-dimensional space

Koudas, Nick, Ooi, Beng Chin, Shen, Heng Tao and Tung, Anthony K. H. (2004). LDC: Enabling search by partial distance in a hyper-dimensional space. In: Meral Ozsoyoglu and Stan Zdonik, Proceedings of the 20th International Conference on Data Engineering, ICDE 2004. 20th International Conference on Data Engineering (ICDE 2004), Boston USA, (6-17). 30 March - 2 April 2004. doi:10.1109/ICDE.2004.1319980


Author Koudas, Nick
Ooi, Beng Chin
Shen, Heng Tao
Tung, Anthony K. H.
Title of paper LDC: Enabling search by partial distance in a hyper-dimensional space
Conference name 20th International Conference on Data Engineering (ICDE 2004)
Conference location Boston USA
Conference dates 30 March - 2 April 2004
Convener IEEE Computer Society
Proceedings title Proceedings of the 20th International Conference on Data Engineering, ICDE 2004   Check publisher's open access policy
Journal name Proceedings - International Conference on Data Engineering   Check publisher's open access policy
Place of Publication Los Alamitos, California, U.S.A.
Publisher IEEE Computer Society
Publication Year 2004
Sub-type Fully published paper
DOI 10.1109/ICDE.2004.1319980
ISBN 0-7695-2065-0
ISSN 1063-6382
Editor Meral Ozsoyoglu
Stan Zdonik
Volume 20
Start page 6
End page 17
Total pages 12
Language eng
Abstract/Summary 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.
Subjects 080604 Database Management
Q-Index Code E1

 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 14 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 27 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Wed, 25 Feb 2009, 23:37:51 EST by Maryanne Watson on behalf of Library Corporate Services