Reducing the Distance Calculations when Searching an M-Tree

Beitrag in einer Fachzeitschrift

Details zur Publikation

Autorinnen und Autoren: Guhlemann S, Petersohn U, Meyer-Wegener K
Zeitschrift: Datenbank-Spektrum
Jahr der Veröffentlichung: 2017
Band: 17
Heftnummer: 2
Seitenbereich: 155-167
ISSN: 1618-2162
Sprache: Englisch


Recent years have brought rising interest in efficiently searching for similar entities in a broad range of domains. Such search can be used to facilitate working with unstructured data such as genome sequences, text corpora, complex production information, or multimedia content, where queries always contain an amount of noise. In such domains the only common structure is a distance function obeying the axioms of a metric. As mostly no other structure information is available, a lot of distances have to be computed during the course of a search. Contrary to classical database indexes, where the optimization focus is on reducing the number of disk accesses (or in case of in-memory databases the number of tree traversal operations), a major cost driver in such multimedia domains is this number of distance calculations which can be very computation intense.

There exists a range of index structures for supporting similarity search in metric spaces. A very promising one is the M-Tree, along with a number of compatible extensions (e. g. Slim-Tree, Bulk Loaded M-Tree, multi way insertion M-Tree, M2-Tree, etc.). The M-Tree family uses common algorithms for the k-nearest-neighbor and range search. These algorithms leave room for optimization in terms of necessary distance calculations. In this paper we present new algorithms for these tasks to considerably improve retrieval performance of all M-Tree-compatible data structures.

FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Meyer-Wegener, Klaus Prof. Dr.-Ing.
Lehrstuhl für Informatik 6 (Datenmanagement)

Einrichtungen weiterer Autorinnen und Autoren

Technische Universität Dresden


Guhlemann, S., Petersohn, U., & Meyer-Wegener, K. (2017). Reducing the Distance Calculations when Searching an M-Tree. Datenbank-Spektrum, 17(2), 155-167.

Guhlemann, Steffen, Uwe Petersohn, and Klaus Meyer-Wegener. "Reducing the Distance Calculations when Searching an M-Tree." Datenbank-Spektrum 17.2 (2017): 155-167.


Zuletzt aktualisiert 2018-11-08 um 02:09