XM-tree: data driven computational model by using metric extended nodes with non-overlapping in high-dimensional metric spaces

Zineddine Kouahla (), Adeel Anjum (), Sheeraz Akram (), Tanzila Saba and José Martinez ()
Additional contact information
Zineddine Kouahla: University of GUELMA
Adeel Anjum: COMSATS Institute of Information Technology
Sheeraz Akram: Foundation University
Tanzila Saba: Prince Sultan University
José Martinez: LINA Laboratory UMR 6241, University of Nantes

Computational and Mathematical Organization Theory, 2019, vol. 25, issue 2, No 7, 196-223

Abstract: Abstract Finding similar objects based on a query and a distance, remains a fundamental problem for many applications. The general problem of many similarity measures is to focus the search on as few elements as possible to find the answer. The index structures divides the target dataset into subsets. With large amounts of data, the volumes of the subspaces grow exponentially, that will affect the search algorithms. This problem is caused by inherent deficiencies of space partitioning, and also, the overlap factor between regions. This methods have proven to be unreliable, it becomes hard to store, manage, and analyze these quantities. The research tends to degenerate into a complete analysis of the data set. In this paper, we propose a new indexing technique called XM-tree, that partitions the space using spheres. The idea is to combine two structures, arborescent and sequential, in order to limit the volume of the outer regions of the spheres, by creating extended regions and inserting them into linked lists named extended regions, and also by excluding of the empty sets—separable partitions—that do not contain objects. The goal is to eliminate some objects without the need to compute their relative distances to a query object. Therefore, we proposed a parallel version of the structure on a set of real machine. We also discuss the efficiency of the construction and querying phases, and the quality of our index by comparing it with recent techniques.

Keywords: Metric space; Indexing; Tree; Extended nodes; Multimedia databases; Nearest neighbor; Complex data (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10588-018-9272-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:comaot:v:25:y:2019:i:2:d:10.1007_s10588-018-9272-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10588

DOI: 10.1007/s10588-018-9272-x

Access Statistics for this article

Computational and Mathematical Organization Theory is currently edited by Terrill Frantz and Kathleen Carley

More articles in Computational and Mathematical Organization Theory from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().