Handling big spatial data

Abstract

De siste årene har moderne tjenester og applikasjoner måtte håndtert mer og mer flerdimensjonale data enn noen gang tidligere. Satellitter, mobilenheter, sosiale nettverk og fremtidige IoT-enheter genererer store mengder data merket med tid, dato og sted. Håndtering av store mengder flerdimensjonal data skaper nye utfordringer for dagens databasesystemer som forsøker å indeksere, lagre og analysere slike data effektivt i sanntid.

Å gjøre om tilfeldig skriving til sekvensiell skriving har blitt stadig viktigere for innsetting av store mengder data. Tradisjonelle indeksstrukturer som B+-trær og R-trær takler store mengder med tilfeldig skriving svært dårlig på grunn av "in-place" skriving for oppdateringer og innsetting. Moderne databasesystemer har derfor tatt i bruk Log-Structured Merge-tree (LSM) i lagringslaget.

Behandling av flerdimensjonal data har fått mye oppmerksomhet den siste tiden på grunn av utviklingen av avanserte databasesystemer som krever høy gjennomstrømning og effektivitet for behandling av oppgaver eller transaksjoner i sanntid. Teknikker for å forbedre ytelsen inkluderer metoder for å redusere antall dimensjoner til dataen, fordi minnemodellene til moderne datamaskiner er endimensjonale.

Denne oppgaven implementerte en eksperimentell LSM-tre datastruktur som inkorporerer en R-tre indeks i diskkomponenten. Ved å benytte egenskapene til romfyllingskurver som Hilbert Curve og Z-Order-Curve, er det mulig å forandre flerdimensjonal geometriske objekter til én dimensjon og lage en sekvensiell ordning som beholder lokaliteten. En lagringslagstruktur ble foreslått i oppgaven, i tillegg til to forskjellige sammenslåingsstrategier, tråding og andre vurderinger å ta hensyn til for høy skriveytelse.

In recent years, modern services and applications handle more and more multi-dimensional data than ever before. Satellites, mobile devices, social networks and in the future IoT devices, generate huge amounts of data tagged with time, date and location. Handling large volumes of multi-dimensional data creates new challenges for today's data management systems that tries to index, store and analyze such data efficiently in real-time.

Transforming random writes to sequential writes have been increasingly important for insert-intensive workloads. Traditional index structures such as B\textsuperscript{+}-trees and R-trees perform very poorly with large quantities of random writes because of their usage of in-place writes for updates and insertion. Modern database systems have therefore implemented the Log-Structured Merge-tree (LSM) in their storage layer.

Managing multi-dimensional data has gained attention with the development of advanced database systems which require high real-time throughput and efficiency for processing tasks or transactions. Techniques to improve performance include efforts to reduce the dimensionality of the data, because the memory models of modern computers are one-dimensional.

This thesis implemented an experimental LSM-tree data structure which incorporates a R-tree index in the disk component. By utilizing the properties of space-filling curves such as the Hilbert curve and Z-Order curve, it is possible to map multi-dimensional geometric objects to one dimension and create a sequential order which conserves locality. A storage layer structure was suggested in the thesis, additionally two different merging strategies, threading and other minor considerations when tuning for write throughput.