Please use this identifier to cite or link to this item:
Title: LDC: Enabling search by partial distance in a hyper-dimensional space
Authors: Koudas, N.
Ooi, B.C. 
Shen, H.T. 
Tung, A.K.H. 
Issue Date: 2004
Citation: Koudas, N., Ooi, B.C., Shen, H.T., Tung, A.K.H. (2004). LDC: Enabling search by partial distance in a hyper-dimensional space. Proceedings - International Conference on Data Engineering 20 : 6-17. ScholarBank@NUS Repository.
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.
Source Title: Proceedings - International Conference on Data Engineering
DOI: 10.1109/ICDE.2004.1319980
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Oct 17, 2018


checked on Oct 17, 2018

Page view(s)

checked on Sep 22, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.