Please use this identifier to cite or link to this item: https://doi.org/10.1109/ICDE.2004.1319980
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
Source: 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. https://doi.org/10.1109/ICDE.2004.1319980
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
URI: http://scholarbank.nus.edu.sg/handle/10635/42018
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.

SCOPUSTM   
Citations

29
checked on Dec 14, 2017

WEB OF SCIENCETM
Citations

15
checked on Nov 18, 2017

Page view(s)

54
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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