Meerdimensionale index

Meerdimensionaal indexeren is een poging objecten in een twee- of meerdimensionale ruimte zodanig te rangschikken dat ze snel op positie teruggevonden kunnen worden. Voor toepassingen valt te denken aan geografische informatiesystemen.

Inleiding

Objecten in een eendimensionale ruimte zijn eenvoudig op positie vergelijkbaar en kunnen dus worden gesorteerd, daarna kan een index worden gebruikt om een object op (of in de buurt van) een gegeven positie snel terug te vinden. Objecten in een meerdimensionale ruimte, zoals een plat vlak, kunnen natuurlijk niet zomaar op positie worden gesorteerd.

Eén oplossingsrichting is het verdelen van de ruimte in vakken, en het toekennen van een uniek nummer aan elk van die vakken. De nummers kunnen vervolgens worden gesorteerd en als basis voor een index dienen. De nummers moeten niet alleen verschillend zijn, maar ook (gemakkelijk) te berekenen zijn aan de hand van de coördinaten van het gezochte punt.

Voorbeelden

Het verdelen van een tweedimensionale ruimte in genummerde vakken wordt veelvuldig toegepast, dit is een eerste stap voor het opbouwen van een tweedimensionale index.

Atlas

Atlassen en stratenboeken bevatten achterin een 'normale' index, gesorteerd op de namen van plaatsen, rivieren, bergen enzovoorts. Achter elke naam staat een paginanummer en een vaknummer, die weer bestaat uit een kolom- en rijnummer. Soms staat er nog een kleine letter a, b, c of d achter die aangeeft in welk kwadrant van het vak het gezochte gevonden kan worden.

Het is nu mogelijk de lijst anders te sorteren, namelijk op paginanummer-rij/kolomnummer-kwadrantaanduiding. Het enige dat nog ontbreekt is een afbeelding van geografische coördinaten op deze nummers; als die er zou zijn, was het mogelijk bij een gegeven coördinatenpaar het vaknummer te berekenen, de index te gebruiken en zo snel bij een lijst namen te komen van objecten die zich in de buurt van de gegeven coördinaten bevinden.

Recursieve binaire vlakverdeling

In het hiernaast geschetste voorbeeld is een begrensde tweedimensionale ruimte (van (0,0) tot (16,16)) in tweeën verdeeld in zowel de x- als y-richting. Daarbij ontstaan vier vakken. Deze vakken kunnen elk weer opnieuw worden verdeeld in twee bij twee kleinere vakken, zoals geschetst in de rechterbovenhoek.

De nummering van de vakken is afhankelijk van het niveau en werkt als volgt.

deel de y-coördinaat door 8 (in dit voorbeeld) en rond het resultaat naar beneden af, bewaar de rest voor het volgende niveau; doe hetzelfde met de x-coördinaat;
de twee cijfers uit bovenstaande berekeningen vormen samen de code voor vakken van het eerste niveau (00, 01, 10 of 11 in de figuur);
vermenigvuldig de resten van de vorige stappen met 2 en rond de resultaten naar beneden af, bewaar de resten voor het volgende niveau;
de twee cijfers uit deze berekeningen vormen samen de volgende twee cijfers van de code voor de vakken van het volgende niveau;
ga verder met stap 3, zolang gewenst.

Het is nu mogelijk voor een willekeurig punt in de gegeven 2D-ruimte een vak te berekenen waar het in ligt, met de gewenste fijnmazigheid. De grootte van de vakken zal in de praktijk zo worden gekozen dat het aantal objecten per vak ruwweg even groot is als het aantal vakken.

De verkregen codes kunnen eenvoudig worden gesorteerd en als index dienen, waarmee de 2D-index een feit is.

Beperkingen

De meerdimensionale index zoals hierboven geschetst heeft een drietal belangrijke beperkingen:

het aantal verschillende objecten in een gegeven vak zal vaak groter zijn dan één; de gevonden objecten zullen na het vinden van het vak nog stuk voor stuk moeten worden beoordeeld;
sommige objecten overschrijden de grens tussen twee (of meer) vakken en moeten dus òf in elk van de vakken worden genoemd òf op vakgrenzen worden onderbroken;
puntobjecten die met een symbool worden weergegeven liggen weliswaar altijd in een vak maar kunnen door de afmetingen van het symbool zichtbaar zijn in méér dan een vak; dit maakt het nodig het object in aangrenzende vakken te noemen of bij het zoeken aangrenzende vakken op te vragen.

Zie ook