An Efficient Split Algorithm to Minimize the Overlap between Node Index Spaces in a Multi-dimensional Indexing Scheme M-tree


The KIPS Transactions:PartD, Vol. 12, No. 2, pp. 233-246, Apr. 2005
10.3745/KIPSTD.2005.12.2.233,   PDF Download:

Abstract

To enhance the user response time of content-based retrieval service for multimedia information, several multi-dimensional index schemes have been proposed. M-tree, a well known multidimensional index scheme is of metric space access method, and is based on the distance between objects in the metric space. However, since the overlap between index spaces of nodes might enlarge the number of nodes of M-tree accessed for query processing, the user response time for content-based multimedia information retrieval grows longer. In this paper, we propose a node split algorithm which is able to reduce the size of overlap between index spaces of nodes in M-tree. In the proposed scheme, we choose a virtual center point as the routing object and entry redistribution as the postprocessing after node split in order to reduce the radius of index space of a node, and finally in order to reduce the overlap between the index spaces of routing nodes. Form the experimental results, we can see the proposed split algorithm reduce the overlap between index space of nodes and finally enhance the user response time for similarity-based query processing.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
S. H. Im, K. I. Ku, K. C. Kim, Y. S. Kim, "An Efficient Split Algorithm to Minimize the Overlap between Node Index Spaces in a Multi-dimensional Indexing Scheme M-tree," The KIPS Transactions:PartD, vol. 12, no. 2, pp. 233-246, 2005. DOI: 10.3745/KIPSTD.2005.12.2.233.

[ACM Style]
Sang Hyuk Im, Kyong I Ku, Ki Chang Kim, and Yoo Sung Kim. 2005. An Efficient Split Algorithm to Minimize the Overlap between Node Index Spaces in a Multi-dimensional Indexing Scheme M-tree. The KIPS Transactions:PartD, 12, 2, (2005), 233-246. DOI: 10.3745/KIPSTD.2005.12.2.233.