BM+-tree: A hyperplane-based index method for high-dimensional metric spaces

Zhou, X. M., Wang, G. R., Zhou, X. F. and Yu, G. (2005). BM+-tree: A hyperplane-based index method for high-dimensional metric spaces. In: Lizhu Zhou, Beng Chin Ooi and Xiaofeng Meng, Database Systems For Advanced Applications, Proceedings. The 10th International Conference on Database Systems for Advanced Applications (DASFAA 2005), Beijing, China, (398-409). 17-20 April, 2005. doi:10.1007/11408079_36


Author Zhou, X. M.
Wang, G. R.
Zhou, X. F.
Yu, G.
Title of paper BM+-tree: A hyperplane-based index method for high-dimensional metric spaces
Conference name The 10th International Conference on Database Systems for Advanced Applications (DASFAA 2005)
Conference location Beijing, China
Conference dates 17-20 April, 2005
Proceedings title Database Systems For Advanced Applications, Proceedings   Check publisher's open access policy
Journal name Database Systems for Advanced Applications, Proceedings   Check publisher's open access policy
Place of Publication Berlin
Publisher Springer-Verlag
Publication Year 2005
Sub-type Fully published paper
DOI 10.1007/11408079_36
Open Access Status Not yet assessed
ISBN 3-540-25334-3
ISSN 0302-9743
Editor Lizhu Zhou
Beng Chin Ooi
Xiaofeng Meng
Volume 3453
Start page 398
End page 409
Total pages 12
Language eng
Abstract/Summary In this paper, we propose a novel high-dimensional index method, the BM+-tree, to support efficient processing of similarity search queries in high-dimensional spaces. The main idea of the proposed index is to improve data partitioning efficiency in a high-dimensional space by using a rotary binary hyperplane, which further partitions a subspace and can also take advantage of the twin node concept used in the M+-tree. Compared with the key dimension concept in the M+-tree, the binary hyperplane is more effective in data filtering. High space utilization is achieved by dynamically performing data reallocation between twin nodes. In addition, a post processing step is used after index building to ensure effective filtration. Experimental results using two types of real data sets illustrate a significantly improved filtering efficiency.
Subjects E1
280108 Database Management
700103 Information processing services
Keyword similarity search
multidimensional index
binary hyperplane
range query
K-NN query
Q-Index Code E1

 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 7 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 4 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Fri, 24 Aug 2007, 06:35:05 EST