Indexing high-dimensional data for efficient in-memory similarity search
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 Delta-tree, to speed up the high-dimensional query in main memory environment. The Delta-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 Delta(+)-tree, that globally clusters the data space and then partitions clusters into small regions. The Delta(+)-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 Delta(+)-tree is superior in most cases.
main memory high-dimensional index similarity query