Please use this identifier to cite or link to this item:
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
Citation: 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.
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
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.


checked on Aug 4, 2022


checked on Aug 4, 2022

Page view(s)

checked on Aug 4, 2022

Google ScholarTM



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