Volltext-Downloads (blau) und Frontdoor-Views (grau)

Vergleich von Quadtree, kd-tree und r-tree für statische und dynamische Geodaten

  • Mit der zunehmenden Bedeutung von Geodaten stellt sich die Frage, welche Indices für welche Anwendungszwecke geeignet sind. Ziel dieser Arbeit ist es, dies am Beispiel von je drei Quadtrees (quadtree, bucket-pr-quadtree, mx-cif quadtree), kd-trees (kd-tree, four-dimensional kd-tree, kdb-tree) und r-trees (guttman r-tree, str-tree, r*-tree) sowohl für statische wie auch dynamische Geodaten zu untersuchen. Als Variante der dynamischen Daten werden zudem Bewegungsdaten betrachtet. Der Vergleich erfolgt sowohl theoretisch, weshalb alle genannten Indices detailliert vorgestellt werden, als auch praktisch. Dazu wurde eine Testumgebung in Java realisiert, die das gezielte Testen von bestimmten Operationen auf den Indices ermöglicht. Als Ergebnis des theoretischen Vergleichs werden verschiedene Charakteristika den Indices zugeordnet, die eine grobe Vorabauswahl ermöglichen. Der praktische Vergleich zeigt anschließend die Resultate differenziert nach Punktgeometrien, Nicht Punktgeometrien und Bewegungsdaten. Als Resultat wird eine generell gute Eignung der r-trees und insbesondere des str-trees dargestellt. Gleichzeitig wird aber auch darauf hingewiesen, dass es Anwendungsszenarien (z.B. langsame I/O) gibt, in denen eine andere Wahl getroffen werden sollte.
  • The increasing importance of spatial data raises the question, which spatial index is most suitable for a specific application. The objective of this thesis is to compare three quadtrees (quadtree, bucket PR quadtree, MX-CIF quadtree), kd-trees (kd-tree, four dimensional kd-tree, KDB-tree) and r-trees (tree Guttman r-tree, st-tree, R *) using both static and dynamic spatial data. In addition to random dynamic operations moving objects are also considered. The comparison consists both of a theoretic part, in which all indices are discussed in detail, and a practical part. For the later a special test system was implemented in Java allowing benchmarks of specific index operations. Various characteristics are identified as a result of the theoretical comparison allowing a rough preselection. The practical comparison then shows the results for point geometries, non-point geometry and movement data. One conclusion of these results is a good suitability of the r-trees and in particular the str-tree for general use cases. But at the same time the results also show that in more specific use cases (e.g. slow I/O) such a conclusion is not possible and a different index should be considered.

Download full text files

Export metadata

Additional Services

Search Google Scholar

Statistics

frontdoor_oas
Metadaten
Author:Christopher Jung
URN:urn:nbn:de:101:1-201201107445
Year of Completion:2011
Document Type:Master's Thesis
Language:German
Publishing Institution:Hochschulbibliothek der Technischen Hochschule Köln
Date of Publication (online):2012/01/10
GND-Keyword:Quad-Baum; Raumdaten
Tag:Geodaten; Quadtree; kd-tree; r-tree
Quadtree; kd-tree; r-tree
Institutes:Informatik und Ingenieurwissenschaften (F10) / Fakultät 10 / Institut für Informatik
Dewey Decimal Classification:500 Naturwissenschaften und Mathematik / 550 Geowissenschaften
Open Access:Open Access