High Dimensional Similarity Search with Bundled Query Processing on Hilbert R-Tree
Yohei Nasu, 直樹 岸川, Kei Tashima, Shin Kodama, Yasunobu Imamura, Takeshi Shinohara, Kouichi Hirata, Tetsuji Kuboyama · 2015
Hilbert R-tree is an R-tree, which is a B-tree-like multiway balanced tree, such that data objects with high dimensions are sorted along the Hilbert curve. In this paper, we first point out that the compact Hilbert R-tree, which is a Hilbert R-tree without preserving Hilbert values, realizes the same performance as the standard Hilbert R-tree, by using the Hilbert sort and the Hilbert merge. Then, to improve search time for high dimensional objects in the compact Hilbert R-tree, we propose a bundled query processing. Furthermore, we introduce two methods, the pre-processing by the Hilbert merge and the control for the order of visiting nodes. From experimental results, we observe that, in the similarity search of sound and image data, the bundled query processing is about 30% faster than the combinations of individual query processing.