Improving Write Performance for Multidimensional Data

Abstract

Mengden romlig data som blir generert hver dag øker raskt. Sosiale medier og sensorer genererer data som inneholder geografisk informasjon, og nødvendigheten for indeksstrukturer som kan håndtere en høy skrivelast med flerdimensjonal data blir større. En indeksstruktur som kan håndtere data med flere dimensjoner er R-trær, og flere designløsninger har blitt utviklet for å forbedre dens skriveytelse. En annen indeksstruktur som har blitt konstruert spesifikt for data med store mengder skriveoperasjoner er Log-Structured Merge-Tree (LSM-tre). En måte å implementere R-trær som komponenter i et LSM-tree har også blitt utviklet av AsterixDB.

Vi vil i denne oppgaven utforske om forbedringene for skriveytelse i R-trær kan bli implementert i strukturen i LSM-trær. Vi ønsker spesifikt å utforske bruken av bulklasting og bulkinnsetting av flerdimensjonale dataobjekter og om det er kompatibelt med den nivå-baserte strukturen i LSM-trær. Andre forbedringer av R-trær og LSM-trær vil også bli undersøkt, i tillegg til ordningsteknikker som er et nødvendig element for komponentene i LSM-trær.

Til slutt har vi implementert en designløsning bestående av hovedstrukturen til LSM-trær med R-trær som komponenter i nivåene. Underveis i vår evaluering fant vi at designløsningen foreslått kan oppnå opp til 34% bedre skriveytelse enn det tradisjonelle R-treet foreslått av Guttman.

The amount of spatial data generated each day is increasing at a rapid rate. As geographical information is part of data generated from social media and sensors, the need for storage structures that can handle high write loads of multidimensional data is increasing. An index structure that can handle data with multiple dimensions is R-trees, and multiple improvements have been made to increase its write performance. Another index structure that has been created specifically to handle a high load of write operations is the Log-Structured Merge-Tree (LSM-tree). In addition, a way of implementing R-trees as components in the LSM-tree have been explored by AsterixDB.

In this thesis we will explore if improvements made for write performance in R-trees can be utilized in an LSM-tree structure. Specifically, we will explore the use of bulk-loading and bulk-insertion of multidimensional data objects and its compatibility with the level-based structure of the LSM-tree. In addition, different improvements to the R-tree and the LSM-tree will be explored, as well as ordering schemes that is required for components in the LSM-tree.

A design utilizing the LSM-tree structure with R-tree structured components have been implemented and explored. During our evaluation it was found that the design can achieve up to 34% better write performance than the traditional R-tree proposed by Guttman.