| dc.description.abstract | I disse dager produserer vi enorme mengder data, mer spesifikt stedfestet data, og behovet for raske indekseringsmetoder er avgjørende for hvordan vi får tilgang til denne dataen. I dag bruker de fleste databasesystemene varianter av R-trær eller Quadtrær med geohashing for å indeksere dataene. Denne oppgaven presenterer et forslag til et design for å forbedre disse standardiserte metodene for indeksering ved å transformere flerdimensjonale data til én dimensjon ved hjelp av romfyllingskurver (space-filling curves), nærmere bestemt Z-order kurven. Ved å gjøre dette kan vi utnytte hurtigtilgangsmetoder for endimensjonale indekseringsmetoder som B-trær, som er O(log n) for søk, innsetting og sletting. Prototypen benytter seg av et UB-tre (Universal B-tre), som er en utvidelse av B+-treet, for å indeksere datapunkter. Dette treet lagrer objektpekere i løvnodene, og sorteres i henhold til deres Z-verdier.
I denne oppgaven har vi funnet en måte å optimalisere k-NN spørringer for avgrensningsbokser ved å bruke en oppfinnelse fra Herzog Tropf, nemlig Bigmin. Resultatene viser at prototypen nesten er dobbelt så rask som et normalt "collection scan"-søk. En sammenligning med MongoDB sin egen "geospatial" spørringsmotor blir gjort, og resultatene viser at MongoDB både er raskere og mer konsistent enn prototypen. Videre diskuterer vi undersøkelser som kan gjøres for å forbedre spørringshastigheten til prototypen. | |
| dc.description.abstract | As we produce immense amounts of data, specific location data, there is an increasing need for fast indexing methods to access the data. Today, most database systems use some variants of R-tree or Quadtree with geohashes to index the data. This thesis provides a possible design and a prototype to improve these standardised methods for indexing by mapping multi-dimensional data to one dimension using space-filling curves, specifically the Z-order curve. By doing this, we can exploit fast access methods of one-dimensional indexing methods such as B-trees, which is O(log n) for search, insert, and delete. Our prototype uses a UB-tree (Universal B-tree), representing an extension of the B+-tree, to index the data points. This tree will store object pointers at its leaf nodes, and sort them according to their Z-values.
We have, in this thesis, found a way to optimise k-NN queries for bounding boxes by using an invention by Herzog Tropf, called Bigmin. The prototype performs almost double as fast as a normal collection scan search. However, a comparison against MongoDBs own geospatial query engine is made, and the results show that MongoDB is both faster and more consistent than the prototype. Further, we discuss investigations that can be made to improve the query speed of the prototype. | |