Orthogonale Bereichsabfrage mit kd-Trees.
Einige Datenbankabfragen können geometrisch als höherdimensionale Bereichsanfragen
interpretiert werden. Um diese effizient durchzuführen, lassen sich kd-Trees
als Datenstruktur einsetzen.
Das in dieser Projektarbeit erstellte Applet visualisiert 2-dimensionale
Rohdaten und stellt die entsprechende Baumstruktur graphisch dar.
Weiter lassen sich Bereichsanfragen als schrittweise Simulation
durchführen, um dem Benutzer zu erlauben, den Suchvorgang nachzuvollziehen.
Problemstellung
Eine Menge von 2-dimensionalen Datenpunkten soll in einer Datenstruktur
gespeichert werden, die sich durch geringen Speicherbedarf auszeichnet und
achsenparallele rechteckige Bereichsabfragen effizient verarbeitet.
Algorithmus
Der verwendete Algorithmus wurde auf Grundlage der Beschreibung in [1]
entwickelt.
In der Literatur wird gezeigt, dass ein kd-Tree für eine Menge von n Punkten
in der Ebene einen Speicherbedarf von O(n) hat und in O(n log n) Zeit
aufgebaut werden kann. Eine rechteckige Suchanfrage benötigt O(n^(1/2) + k)
Laufzeit, wobei k für die Anzahl der zurückgegebenen Punkte steht.
Die beiden Algorithmen zum Aufbau des Baumes und zur
Suchanfrage sind in folgender pdf-Datei erläutert: Erläuterungen.
Download
Download der ausführbaren Datei.
Literaturverzeichnis
[1] Mark de Berg et al.: Computational Geometry – Algorithms and
Applications. Third Edition. Springer. 2008. ISBN: 978-3-540-77973-5.