High Dimensional Similarity Search with Bundled Query Processing on Hilbert R-Tree

Yohei Nasu, Naoki Kishikawa, Kei Tashima, Shin Kodama, Yasunobu Imamura, Takeshi Shinohara, Koichi Hirata, Tetsuji Kuboyama

2015

Abstract

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.

Paper Citation

in Harvard Style

Nasu Y., Kishikawa N., Tashima K., Kodama S., Imamura Y., Shinohara T., Hirata K. and Kuboyama T. (2015). High Dimensional Similarity Search with Bundled Query Processing on Hilbert R-Tree . In Proceedings of the International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM, ISBN 978-989-758-076-5, pages 354-359. DOI: 10.5220/0005279503540359

in Bibtex Style

@conference{icpram15,
author={Yohei Nasu and Naoki Kishikawa and Kei Tashima and Shin Kodama and Yasunobu Imamura and Takeshi Shinohara and Koichi Hirata and Tetsuji Kuboyama},
title={High Dimensional Similarity Search with Bundled Query Processing on Hilbert R-Tree},
booktitle={Proceedings of the International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM,},
year={2015},
pages={354-359},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005279503540359},
isbn={978-989-758-076-5},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM,
TI - High Dimensional Similarity Search with Bundled Query Processing on Hilbert R-Tree
SN - 978-989-758-076-5
AU - Nasu Y.
AU - Kishikawa N.
AU - Tashima K.
AU - Kodama S.
AU - Imamura Y.
AU - Shinohara T.
AU - Hirata K.
AU - Kuboyama T.
PY - 2015
SP - 354
EP - 359
DO - 10.5220/0005279503540359