Evaluating a Flattened R-tree in MongoDB

Abstract

Denne oppgaven utforsker utviklingen og evalueringen av en flat R-tre-indeksstruktur for MongoDB. MongoDB, en ledende NoSQL-database, har blitt mye brukt for stordataapplikasjoner, men dens begrensninger når det gjelder håndtering av flerdimensjonal data ga ideen om å implementere en R-tre-indeks som kunne forbedre ytelsen ved flerdimensjonale spørringer.

Forskningen startet med en omfattende litteraturgjennomgang for å få en dyp forståelse av MongoDBs nåværende indekser, R-tre-strukturer, og de potensielle fordelene ved å integrere sistnevnte i MongoDB-miljøet. Et tidligere forsøk på å implementere et R-tre i MongoDB ble funnet og det ble brukt som et grunnlag for implementeringen presentert i denne oppgaven. Spørringene til den implementerte R-tre-indeksen ble testet med fire forskjellige datasett. Testene var primært utformet for å måle og sammenligne ytelsen til den nylig implementerte indeksen mot MongoDBs eksisterende indekseringsstruktur.

Resultatene viser at det implementerte R-treet ikke utkonkurrerer den eksisterende indekseringsstrukturen i MongoDB. Imidlertid viste R-treet lovende resultater under visse forhold, noe som indikerer at en R-tre-indeks kan prestere bedre enn den nåværende 2dsphere indeksen til MongoDB, hvis den blir implementert riktig. Studien understreker at implementasjonen av R-treet er den viktigste årsaken til resultatene, og at med en forbedret implementasjon kunne R-treet vært et gunstig tillegg til MongoDB. Selv om implementasjonen er mangelfull, så forbedrer den MongoDB sin håndtering av kartesiske koordinater Dette kan potensielt forbedre stordataprosessering og applikasjoner som har høye krav til prosesseringstid av romlige sprørringer. Oppgaven avslutter med forslag til videre arbeid som har som mål å forbedre R-tre-implementasjon.

This thesis explores the development and evaluation of a flattened R-tree indexing structure for MongoDB. MongoDB, a leading NoSQL database, has been extensively used for big data applications, but its limitations in handling spatial data provoked the idea of implementing an R-tree index that could enhance performance in spatial querying.

The research began with a comprehensive literature review to gain a profound understanding of MongoDB's current indexing capabilities, R-tree structures, and the potential advantages of integrating the latter within the MongoDB environment. A previous attempt at implementing an R-tree alongside MongoDB was found and it served as the base for the implementation presented in this thesis. The implemented R-tree index's query operations were tested with four different data sets. Tests were primarily designed to measure and compare the performance of the newly implemented index against MongoDB's existing geospatial indexing structure.

Results show that the implemented R-tree does not outperform the existing indexing structure in MongoDB. However, the R-tree showed promise under certain query conditions, indicating that an R-tree index can perform better than the current 2dsphere index in MongoDB if implemented properly. The study emphasizes that the implementation of the R-tree is the most significant cause of the results and that with an improved implementation, the R-tree could be an enriching addition to MongoDB. While the implementation has several shortcomings, it improves MongoDB's handling of Cartesian coordinates. This could potentially improve big data processing and applications that demand high-performance spatial querying. The thesis concludes with propositions for further work aiming to improve the R-tree implementation.