The Prospect of Merging R-trees

Abstract

Romlig data benyttes i forskjellige applikasjoner og forskingsområder. I nyere tid har det vært en eksplosjon i mengden romlig data generert av smarttelefoner, satellitter og geomerketede sensorer. Denne oppgaven fokuserer først og fremst på R-trær siden de er indekser med et generelt bruksområde, kan håndtere en stor variasjon spørringer og er kompatible med enorme datasett. I dette prosjektet blir metoder for innsetting av store mengder data inn til et R-tre studert og utdypet. Flette sammen adskilte datastrukturer til en ny indeks, som dekker hele datasettet, oppstår som et alternativ til bulk lasting og innsetting. Bulk lasting pleier å benytte seg av sortering av data for å bygge datastrukturen, mens bulk innsetting kan gi dårligere resultater for spørringer, gitt datasett og metode implementert.

Forskjellige varianter av romdata og R-trær diskuteres i detalj. Dette inkluderer hvordan R-trær takler tidsdimensjoner, og hvilke justeringer som er nødvendig for å utvide R-trær til parallelle og distribuerte systemer. Nå som vi nærmer oss det neste tiåret, hvor flere maskiner fortsetter å produsere mer romdata med ulike typer tilleggsinformasjon, må aksess-metodene kunne operere effektivt over klustere. Dagens mest fremtredende løsninger, som innebærer å utføre bulk lasting parallelt over distribuerte(parallelle) systemer, diskuteres i tillegg til bulk innsettings metoder.

En ny flettemetode ble utarbeidet med fordelene fra bulk innsetting. Avhandlingen inneholder også en komparativ studie av fremtredende metoder fra fletting, bulk lasting og innseting. Undersøkelsen skisserer ytelsesegenskapene til de ulike metodene. Fletting viser seg å være lovende under visse forhold. Ut ifra resultatene er det klart at mange variabler må tas i betraktning når et R-tre skal bygges for en gitt oppgave. Dermed er en trent kostnadsmodel muligens veien fremover.

Spatial data are found in numerous applications and research areas. In recent times, there has been a rapid explosion in the amount of spatial data generated by devices such as smart phones, satellites and geotagged sensors. This thesis mainly focuses on the access method Rtree as it is a general-purpose data structure, can handle a variety of spatial quires, and compatible with the massive volume of data. In this project methods and techniques for ingesting large amounts of rapidly produced spatial data into a R-tree are studied and elaborated. The process of merging separate data structures into a new index that cover, the whole data set, arise as an alternative to bulk loading and insertion. Bulk loading tends to rely upon pre-sorting the data to build the data structure, and bulk insertion may give worse query performance given the dataset and method implemented.

The variants of spatial data and R-trees are discussed in detail. This entails, How R-trees have adapted to tackle temporal dimensions, and what adjustments are necessary to extend R-trees to parallel or distributed environments. As we head into the next decade where more devices continue to produce spatial information with various associated information, the access methods for spatial data must be able to operate efficiently on clusters. The state of the art methods for parallelizing bulk loading R-trees on parallel systems are discussed. Also, the state of the art bulk insertion methods are examined.

A new merging method was devised, to bridge the advantages of bulk insertion. The thesis also includes a comparative study of prominent methods from merging, bulk loading and insertion. The study outlines the performance characteristics of the various methods on real and synthetic datasets. Merging was found to promising under certain conditions. From the results, it is clear that many variables must be taken into consideration when constructing a R-tree for a specified application. Given the results, a learned cost model may be the way forward.