Benchmarks
1996-6
NGTGEODESIA
1for each level do
Compute_quadcodes(level, bbox) II zie functie hierna
2. ranges of SLC codes can be joined to larger ranges
De functie Overlap_SLC (bbox) berekent de verzameling Fig. 9.
SLC-intervallen die behoren bij een specifiek zoekgebied Overlap_SLC
bbox (fig. 9). Vervolgens worden voor ieder niveau de (bbox).
quadcodes (of Morton-intervallen) corresponderend met
de bbox berekend (stap 1). Dit gebeurt met de functie
Compute_quadcodes (level, bbox) (fig. 10), die op zijn
beurt de recursieve functie Add_quad_level (quaddomain,
minSLC, maxSLC, bbox) gebruikt. Deze recursieve functie
voegt de nieuwe intervallen voor het aangegeven domein
toe aan de verzameling intervallen (fig. 11).
Initialize quaddomain afhankelijk van niveau
set_of_ranges=() begin met lege verzameling
minSLC=0; maxSLC=(nr[level])A2 - 1 II de SLC intervallen
Add_quad_level(quaddomain, minSLC, maxSLC, bbox)
Merk op dat wanneer het aantal intervallen te groot wordt Fig. 10.
(bijvoorbeeld voor de database where-clause), er een aantal Compute_quad-
mogelijkheden is om het aantal intervallen te reduceren: codes(level, bbox).
ga niet tot het laagste niveau van de Quadtree;
verenig intervallen als er een klein gat tussen hen bestaat;
reduceer het totale aantal niveaus waarmee begonnen
wordt (bijvoorbeeld slechts vijf).
if (minSLC==maxSLC) do
1. add (minSLC, maxSLC) to set_of_ranges //klaar
else
2. split quaddomain in quad[0], quadjl], quad[2], quad[3]
3. for i=0 to 3 do
3a. new_minSLC minSLC i*((maxSLC+l-minSLC)/4))
new_maxSLC minSLC (i+l)*((maxSLC+l-minSLC)/4)) -1
3b. if bbox FULL_COVERS quad[i]
add (new_minSLC,new_maxSLC) to set_of_ranges klaar
3c. else if bbox PARTIAL_CO VERS quad[i] recursie
add_quad_leve!(quad[i], new_minSLC, new_maxSLC, bbox)
Twee vormen benchmarks worden gepresenteerd. In de
eerste worden metingen met betrekking tot het aantal
intervallen (en de reductie hiervan) gepresenteerd. In de
tweede worden resultaten met echte (kadastrale) informatie
gegeven.
Aantal intervallen
In het voorgaande werd reeds besproken dat het aantal
intervallen geproduceerd door de functie Overlap_SLC een
probleem kan worden. Om deze reden is er een functie be-
Fig. 11.
Add_quad_level
(quaddomain,
minSLC, maxSLC,
bbox).
Fig. 12.
Verhouding
benodigde cellen
met een 5 niveau
grid SLC).
248
schikbaar, die kleine openingen tussen
opeenvolgende intervallen sluit. Deze
functie blijft itereren totdat het vereis
te aantal intervallen is bereikt. Iedere
keer als twee opeenvolgende inter
vallen worden samengevoegd, worden
er (ongewenste) cellen meegenomen.
Wanneer bijvoorbeeld de intervallen
(10,17) en (20,23) worden samenge
voegd, zal het resulterende interval
(10,23) de ongewenste cellen 18 en 19
bevatten. Voor iedere test werden
honderd willekeurige zoekgebieden
gegenereerd op de volgende wijze:
de ligging van het gebied is wille
keurig binnen het gehele domein
(uniform verdeeld);
de lengte van de zijden van het vier
kante zoekgebied is willekeurig ge
nomen uit het interval [0,75 x X,
1,25 x X], waarbij X gelijk is aan de
opgegeven gemiddelde grootte. De
SLC-waarden zijn gebaseerd op een
5 niveau Field-tree.
Tabel 1 toont de metingen voor zes
verschillende zoekgebiedgrootten (X is
0,25, 0,5, 12, 4, en 8 km) en voor zes
verschillende bovengrenzen voor het
maximale aantal toegestane intervallen
(hoogstens 6, 10, 15, 20, en 30 inter
vallen). Bij de honderd willekeurige
zoekgebieden is het gemiddelde aantal
initiële SLC-intervallen (zonder ope
ningen 0 te sluiten): 13,1 (X=0,25),
22,5 (X=0,5), 40,3 (X=l), 77,9 (X=2),
155,6 (X=4) en 308,6 (X=8). Deze
aantallen intervallen in de where-clause
kunnen een probleem zijn voor som
mige RDBMSen. De effectiviteit van
het reduceren van de intervallen kan
men aangeven door de verhouding te
berekenen tussen het aantal cellen dat
wordt geselecteerd door de geredu
ceerde intervallen en het aantal werke-
Verhouding tussen geselecteerde
en benodigde aantal cellen
10 intervallen
15 intervallen
20 intervallen
30 intervallen
Omvang
gebied
