Document Type

Article

Publication Date

2-2022

Publication Title

Information Systems

Volume

104

Pages

1-13

Publisher Name

Elsevier

Abstract

Since the introduction of the M-tree, a fundamental tree-based data structure for indexing multidimensional information, several structural enhancements have been proposed. One of the most effective ones is the use of additional global pivots that resulted in the PM-tree. These two indexing structures, however, can store the same data element in multiple nodes. In this article, we revisit both the M-tree and the PM-tree to propose a new construction algorithm that stores data elements only once in the tree hierarchies. The main challenge to accomplish this, is to properly select data elements when an inner node split is needed. To address it, we propose an approach based on the use of aggregate nearest neighbor queries. The new algorithms enable building the search result set as data elements are evaluated for pruning during traversal, allowing faster retrieval of k-nearest neighbors and range searches. We conducted an extensive set of experiments with different real datasets. The results show that our proposed algorithms have considerably superior performance when compared with the standard M-tree and PM-tree.

Comments

Author Posting © Elsevier, Ltd., 2021. This is the author's version of the work. It is posted here by permission of Elsevier for personal use, not for redistribution. The definitive version was published in Information Systems, Volume 104, February 2022. https://doi.org/10.1016/j.is.2021.101896

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.

Download

Share

COinS