| |
11
des Datenraumes (die Linie x= 0.5 und die Linie y= 0.5) durchschneidet, kann nur durch die leere
Quadrantenreihenfolge approximiert werden. Wenn das Polygon, das approximiert werden muß, sehr
groß ist scheint eine
A
pproximation durch eine leere Reihenfolge oder durch eine sehr kurze
Reihenfolge gerechtfertigt zu sein. Für kleine Polygone ist der Verhältnisannäherungsfehler zu groß.
Der relative Raum Aufwand für die Objektapproximation ist so unbegrenzt. In Wirklichkeit sind die
Objekte, welche sich durch die leeren Quadrantenreihenfolgen angenähert haben, Kandidaten für jede
Anfrage, die der Nutzer stellt. Je mehr Objekte mit kurzer Quadrantenreihenfolge in der Datenbank
gespeichert werden, um so schlechter ist die Trennschärfe (die Auswahlkraft) des Index.
3.4 Optimierte Redundanz
Um einen unbegrenzten Approximationsaufwand zu verhindern, schlägt Orenstein [Böh 99]* eine
Kombination der einfachen Methode und der Ein-Reihenfolge Darstellung vor.
Er adoptiert die
I
dee von der Aufspaltung der Objekte von der einfachen Methode, aber er zerlegt
nicht unbedingt jedes Objekt bis die Basisauflösung erreicht ist. Stattdessen schlägt er zwei
verschieden Kriterien vor (bezeichnet als größenbegrenzt und fehlerbegrenzt) um die Zahl der
Quadranten zu kontrollieren, in die ein Objekt zerlegt wird. Jedes Unterobjekt wird in dem Index
gespeichert, in dem man seine Quadrantenreihenfolge benutzt, die als String dargestellt wird. Ob
gleich diese Konzept eine Objektduplizierung einschließt (welche nach Orenstein als Redundanz
bezeichnet wird), ist die Zahl der Datensätze, welche in dem Index gespeichert werden, nicht direkt
durch die Rasterauflösung wie in der einfachen Methode determiniert. Anders als in der Ein-
Reihenfolge Methode, ist es nicht notwendig, kleine Objekte durch leere Reihenfolgen oder durch sehr
kurze Reihenfolgen zu repräsentieren. Übereinstimmend mit Orenstein ist eine Aufspaltung in
-4
Teile typisch für eine zufriedenstellende Suchleistung. Orensteins Methode erleichtert die Probleme
der zwei vorher genannten Methoden, aber eine Doppelbeseitigung ist immer noch erforderlich und
die Schlüssel sind immer noch Reihenfolgen mit unterschiedlicher Länge. Orenstein begründet den
optimalen Grad der Redundanzen nur experimentell. Eine analytische Lösung wurde von Gaede (Gae
95) vorgeschlagen, der die Komplexität der gespeicherten Polygone identifizierte, beschrieben durch
ihre Parameter und ihre fractale Dimension, als den Hauptparameter für die Optimierung. Einweitere
Problem, das entsteht, wenn Redundanzen erlaubt sind, entsteht in Verbindung mit dem zweiten Filter
in einer Mehr-Schritt-Umgebung. Informationen welche für ein schnelles Filtern von falschen Hits
benutz werden können, so wie die ergänzende herkömmliche Approximation (Minimum Boundaring
Rectangles MRB) sollten wegen ihrer hohen Speicherfähigkeit keine Subjekt der Duplizierung sein.
Um eine Duplizierung einer solchen Information zu verhindern, muss dies in einer separaten Tabelle
gespeichert werden, welche
rgänzende Verbindungen im Frageprozess enthält. Eine weiter
Konseqenz aus der Analyse von Gaede ist, dass die Anzahl der Intervalle, welche von der
Fragenfenstern generiert werden, proportional zur Zahl der Rasterzellen ist, welche von der Grenze
des Anfragefensters geschnitten werden. Das bedeutet, dass eine zu feine Auflösung der Raster zur
einer großen Zahl von Intervallen führt und auf diese Weise das Ausführungsverhalten beeinfluss,
wenn eine relationale Datenbank genutzt wird. Der Grund ist, dass die Intervalle durch der
Datenbankserver transferriert und bearbeitet werden müssen, was nicht vermeidbar ist, wenn die Zahl
der Intervalle sehr hoch ist.
|  |
|
| |
|
|
