WikiDer > Mehrdimensionaler Index
Mehrdimensionaler Indexierungsindex ist ein Versuch, Objekte in eine zwei- oder mehrdimensionale Platz können so angeordnet werden, dass sie schnell in Position gefunden werden können Geografisches Informationssystem.
Vorwort
Objekte in a eindimensionaler Raum sind in der Lage leicht vergleichbar und können somit sortiert, dann ein Index werden verwendet, um ein Objekt schnell an (oder in der Nähe) einer bestimmten Position zu lokalisieren.Objekte in a mehrdimensional Raum, wie eine ebene Fläche, kann natürlich nicht nur nach Position sortiert werden.
Eine Lösungsrichtung besteht darin, den Raum in Fächer zu unterteilen und a einzigartig Nummer zu jedem dieser Kästchen. Die Zahlen können dann sortiert und als Grundlage für a . verwendet werden Index Dienen. Die Zahlen müssen nicht nur unterschiedlich sein, sondern auch (einfach) mit dem Koordinaten des gewünschten Punktes.
Beispiele
Das Aufteilen eines zweidimensionalen Raums in nummerierte Kästchen ist weit verbreitet, dies ist ein erster Schritt zum Erstellen eines zweidimensionalen Indexes.
Atlas
Atlanten und Straßenbücher enthalten hinten einen 'normalen' Index, sortiert nach den Namen von Orten, Flüssen, Bergen usw. Hinter jedem Namen steht eine Seiten- und eine Kastennummer, die wiederum aus einer Spalten- und Zeilennummer besteht. Manchmal gibt es einen kleinen Buchstaben a, b, c oder d, der angibt, in welchem Quadrant des Themas zu finden.
Es ist nun möglich, die Liste anders zu sortieren, nämlich nach Seitennummer-Zeilen-/Spaltennummer-Quadrantenbezeichnung. Es fehlt nur noch ein Bild von geografische Koordinaten auf diesen Zahlen; Wenn ja, wäre es möglich, die Boxnummer für ein bestimmtes Koordinatenpaar zu berechnen, den Index zu verwenden und schnell zu einer Liste mit Namen von Objekten zu gelangen, die sich in der Nähe der angegebenen Koordinaten befinden.
Rekursive binäre Ebenendivision
Im nebenstehenden Beispiel wird ein begrenzter zweidimensionaler Raum (von (0,0) bis (16,16)) sowohl in x- als auch in y-Richtung zweigeteilt. Dadurch entstehen vier Fächer. Diese Boxen können jeweils in zwei mal zwei kleinere Boxen unterteilt werden, wie in der oberen rechten Ecke skizziert.
Die Nummerierung der Boxen hängt vom Level ab und funktioniert wie folgt.
- dividiere die y-Koordinate durch 8 (in diesem Beispiel) und runde das Ergebnis ab, speichere den Rest für die nächste Ebene; machen Sie dasselbe mit der x-Koordinate;
- die beiden Zahlen aus den obigen Berechnungen bilden zusammen den Code für die Fächer der ersten Stufe (00, 01, 10 oder 11 in der Abbildung);
- multiplizieren Sie die Reste aus den vorherigen Schritten mit 2 und runden Sie die Ergebnisse ab, speichern Sie die Reste für die nächste Stufe;
- die zwei Ziffern aus diesen Berechnungen bilden zusammen die nächsten zwei Ziffern des Codes für die Fächer der nächsten Stufe;
- fahren Sie mit Schritt 3 so lange wie gewünscht fort.
Es ist nun möglich, für einen beliebigen Punkt im gegebenen 2D-Raum eine Box mit der gewünschten Feinkörnigkeit zu berechnen. In der Praxis wird die Größe der Fächer so gewählt, dass die Anzahl der Gegenstände pro Fach ungefähr der Anzahl der Fächer entspricht.
Die erhaltenen Codes lassen sich einfach sortieren und als Index verwenden, wodurch der 2D-Index zur Tatsache wird.
Einschränkungen
Der oben beschriebene mehrdimensionale Index weist drei wichtige Einschränkungen auf:
- die Anzahl der verschiedenen Objekte in einer bestimmten Box ist oft größer als eins; die gefundenen Objekte müssen nach dem Auffinden des Subjekts einzeln bewertet werden;
- einige Objekte überschreiten die Grenze zwischen zwei (oder mehr) Kästchen und müssen daher entweder in jedem der Kästchen erwähnt oder an Kästchengrenzen unterbrochen werden;
- Punktobjekte, die mit einem Symbol dargestellt werden, befinden sich immer in einer Box, können jedoch aufgrund der Abmessungen des Symbols in mehr als einer Box sichtbar sein; dies erfordert die Benennung des Objekts in benachbarten Boxen oder das Abfragen benachbarter Boxen bei der Suche.