Please use this identifier to cite or link to this item:
|Title:||LDC: Enabling search by partial distance in a hyper-dimensional space|
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 14, 2017
WEB OF SCIENCETM
checked on Nov 18, 2017
checked on Dec 10, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.