Please use this identifier to cite or link to this item: https://doi.org/10.1109/TKDE.2005.46
Title: Indexing high-dimensional data for efficient in-memory similarity search
Authors: Cui, B. 
Ooi, B.C. 
Su, U.
Tan, K.-L. 
Keywords: High-dimensional index
Main memory
Similarity query
Issue Date: 2005
Source: Cui, B., Ooi, B.C., Su, U., Tan, K.-L. (2005). Indexing high-dimensional data for efficient in-memory similarity search. IEEE Transactions on Knowledge and Data Engineering 17 (3) : 339-352. ScholarBank@NUS Repository. https://doi.org/10.1109/TKDE.2005.46
Abstract: In main memory systems, the L2 cache typically employs cache line sizes of 32-128 bytes. These values are relatively small compared to high-dimensional data, e.g., > 32D. The consequence is that existing techniques (on low-dimensional data) that minimize cache misses are no longer effective. In this paper, we present a novel index structure, called A-tree, to speed up the high-dimensional query in main memory environment. The Δ-tree is a multilevel structure where each level represents the data space at different dimensionalities: the number of dimensions increases toward the leaf level. The remaining dimensions are obtained using Principal Component Analysis. Each level of the tree serves to prune the search space more efficiently as the lower dimensions can reduce the distance computation and better exploit the small cache line size. Additionally, the top-down clustering scheme can capture the feature of the data set and, hence, reduces the search space. We also propose an extension, called Δ 1-tree, that globally clusters the data space and then partitions clusters into small regions. The Δ +- tree can further reduce the computational cost and cache misses. We conducted extensive experiments to evaluate the proposed structures against existing techniques on different kinds of data sets. Our results show that the Δ +-tree is superior in most cases. © 2005 IEEE.
Source Title: IEEE Transactions on Knowledge and Data Engineering
URI: http://scholarbank.nus.edu.sg/handle/10635/39174
ISSN: 10414347
DOI: 10.1109/TKDE.2005.46
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

21
checked on Dec 13, 2017

WEB OF SCIENCETM
Citations

11
checked on Nov 16, 2017

Page view(s)

44
checked on Dec 16, 2017

Google ScholarTM

Check

Altmetric


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