Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


26. Bereichssuche



Mehrdimensionale Bereichssuche

Sowohl das Gitterverfahren als auch 2D-Bäume lassen sich unmittelbar auf mehr als zwei Dimensionen verallgemeinern: Einfache, direkte Verallgemeinerungen der obigen Algorithmen führen unmittelbar zu Bereichssuchverfahren, die für mehr als zwei Dimensionen geeignet sind. Die Natur der mehrdimensionalen Räume erfordert jedoch eine gewisse Vorsicht und läßt vermuten, daß sich die Leistungsfähigkeitsmerkmale der Algorithmen für eine spezielle Anwendung schwer vorhersagen lassen.

Um das Gitterverfahren für eine k-dimensionale Suche zu implementieren, definieren wir einfach grid als k-dimensionales Feld und benutzen einen Index pro Dimension. Das Hauptproblem besteht darin, einen sinnvollen Wert für size zu wählen. Dieses Problem wird sehr deutlich, wenn ein großes k betrachtet wird: Welchen Gittertyp sollten wir für eine 10-dimensionale Suche verwenden? Die Schwierigkeit ergibt sich daraus, daß wir selbst dann, wenn wir nur drei Aufteilungen pro Dimension benutzen, 310 Gitterquadrate benötigen, von denen die meisten für sinnvolle Werte von N leer sind.

Die Verallgemeinerung von 2D- auf kD-Bäume ist gleichfalls unmittelbar möglich: Während der Bewegung im Baum abwärts durchlaufe man die Dimensionen einfach zyklisch (so wie wir dies für zwei Dimensionen getan haben, indem wir zwischen x und y wechselten). Wie zuvor haben die sich ergebenden Bäume bei einer zufälligen Verteilung die gleichen Merkmale wie binäre Suchbäume. Wie zuvor existiert auch eine natürliche Entsprechung zwischen den Bäumen und einem einfachen geometrischen Prozeß. Im dreidimensionalen Fall entspricht das Abzweigen bei jedem Knoten der Zerlegung des betreffenden dreidimensionalen Gebiets mittels einer Ebene; im allgemeinen Fall zerlegen wir das betreffende k-dimensionale Gebiet mittels einer (k-1)-dimensionalen Hyperebene.

Falls k sehr groß ist, ist es wahrscheinlich, daß die kD-Bäume sehr unausgeglichen sind, was wiederum daran liegt, daß in der Praxis auftretende Punktmengen nicht genügend umfangreich dafür sind, daß sich die Zufälligkeit über eine große Zahl von Dimensionen erstrecken kann. In typischen Fällen haben alle Punkte in einem Teilbaum für mehrere Dimensionen den gleichen Wert, was zu verschiedenen Verzweigungen in nur einer Richtung in den Bäumen führt. Eine Möglichkeit, wie dieses Problem abgeschwächt werden kann, besteht darin, immer diejenige Dimension zu verwenden, die die Punktmenge in der besten Weise zerlegt, anstatt die Dimensionen einfach zyklisch zu durchlaufen. Diese Methode kann auch für 2D-Bäume angewandt werden. Sie erfordert, daß in jedem Knoten zusätzliche Information (welche Dimension ausgewählt werden sollte) gespeichert wird, verringert jedoch die Unausgeglichenheit, besonders in Bäumen mit vielen Dimensionen.

Zusammenfassend kann gesagt werden, daß, obwohl man leicht sehen kann, wie sich unsere Programme für die Bereichssuche auf die Behandlung mehrdimensionaler Probleme übertragen lassen, ein solcher Schritt für eine umfangreiche Anwendung nicht leichtfertig ausgeführt werden sollte. Große Datenbanken mit vielen Attributen pro Datensatz können tatsächlich sehr komplizierte Objekte sein, und oft sind gründliche Kenntnisse der Merkmale einer Datenbank erforderlich, um für eine spezielle Anwendung ein effizientes Verfahren für die Bereichssuche zu entwickeln. Dies ist ein sehr wichtiges Problem, welches gegenwärtig noch aktiv erforscht wird.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]