Storing data once in M-trees and PM-trees: Revisiting the building principles of metric access methods

Humberto Razente, Maria Camila N. Barioni, Yasin N. Silva

Research output: Contribution to journalArticlepeer-review


Since the introduction of the M-tree, a fundamental tree-based data structure for indexing multi-dimensional 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.

Original languageEnglish (US)
Article number101896
JournalInformation Systems
StatePublished - Feb 2022


  • Ball-partitioning indexing
  • M-tree
  • Metric access methods
  • PM-tree
  • Range query
  • k-nearest neighbor query

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'Storing data once in M-trees and PM-trees: Revisiting the building principles of metric access methods'. Together they form a unique fingerprint.

Cite this