Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Berkmann, N., Krigel, H.-P., Schneider, R., Seeger, B.: The R*-tree: an Efficient and Robust Access Method for Points and Rectangles. In: ACM SIGMOD 1990, pp. 322–331 (1990)
Katayama, N., Satoh, S.: The SR-tree: an Index Structure for High-dimensional Nearest Neighbor Queries. In: ACM SIGMOD 1997, pp. 369–380 (1997)
White, D.A., Jain, R.: Similarity Indexing with the SS-tree. In: ICDE 1996, pp. 516–523 (1996)
Lin, K.-I., Jagadish, H.V., Faloutsos, C.: The TV-tree: An Index Structure for High-Dimensional Data. VLDB Journal 3(4), 517–542 (1994)
Uhlmann, J.K.: Satisfying General Proximity/ Similarity Queries with Metric Trees. Information Processing Letters 40, 175–179 (1991)
Zezula, P., Ciaccia, P., Rabitti, F.: M-tree: A Dynamic Index for Similarity Queries in Multimedia Databases. TR 7, HERMES ESPRIT LTR Project (1996)
Bozkaya, T., Ozsoyoglu, M.: Distance-based Indexing for High-dimensional Metric Spaces. In: ACM SIGMOD 1997, pp. 357–368 (1997)
Ciaccia, P., Patella, M., Zezula, P.: M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. In: VLDB 1997, Greece (1997)
Ishikawa, M., Chen, H., Furuse, K., Yu, J.X., Ohbo, N.: MB + tree: a Dynamically Updatable Metric Index for Similarity Search. In: Lu, H., Zhou, A. (eds.) WAIM 2000. LNCS, vol. 1846, pp. 356–366. Springer, Heidelberg (2000)
Traina Jr., C., Traina, A., Seeger, B., Faloutsos, C.: Slim-trees: High Performance Metric Trees Minimizing Overlap Between Nodes. In: Zaniolo, C., Grust, T., Scholl, M.H., Lockemann, P.C. (eds.) EDBT 2000. LNCS, vol. 1777, pp. 51–65. Springer, Heidelberg (2000)
Zhou, X., Wang, G., Yu, J.X., Yu, G.: M + -tree: A New Dynamical Multidimensional Index for Metric Spaces. In: Proc. of 14th Australasian Database Conference (ADC 2003), pp. 161–168 (2003)
Wang, G., Lu, H., Yu, G., Bao, Y.: Managing Very Large Document Collections Using Semantics. Journal of Computer Science and Technology 18(3), 403–406 (2003)
Böhm, C., Berchtold, S., Keim, D.A.: High-dimensional Spaces - Index Structures for Improving the Performance of Multimedia Databases. ACM Computing Surveys (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhou, X., Wang, G., Zhou, X., Yu, G. (2005). BM + -Tree: A Hyperplane-Based Index Method for High-Dimensional Metric Spaces. In: Zhou, L., Ooi, B.C., Meng, X. (eds) Database Systems for Advanced Applications. DASFAA 2005. Lecture Notes in Computer Science, vol 3453. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11408079_36
Download citation
DOI: https://doi.org/10.1007/11408079_36
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25334-1
Online ISBN: 978-3-540-32005-0
eBook Packages: Computer ScienceComputer Science (R0)