A Learned Bucket Index Supporting Spatial Queries
Authors
Folmer, Martin ; Karunanithi, Theevaahar ; Neumann, Raphael
Term
4. term
Education
Publication year
2019
Pages
14
Abstract
Lærte indeks—maskinlæringsbaserede modeller, der forudsiger hvor data ligger—har vist potentiale for én- og flerdimensionelle relationelle data. Denne afhandling undersøger, om sådanne indeks også fungerer godt for rumlige data. Vi udvikler en projektionsfunktion, der ordner rumlige punkter, så en model kan lære rækkefølgen. Med denne ordning træner vi modeller og bygger et indeks med en hierarkisk struktur og mindre hjælpekomponenter. Indekset er designet til at understøtte områdeforespørgsler (find alle objekter i et givent område) og nærmeste nabo-forespørgsler (find det nærmeste objekt). For at besvare nærmeste nabo-forespørgsler omdanner vi dem til områdeforespørgsler. Vi sammenligner hastigheden af vores indeks med et R-tree på datasæt af forskellige størrelser og fordelinger. Vores evaluering viser, at det lærte indeks overgår R-tree i de fleste tilfælde. Resultaterne indikerer, at på trods af udfordringer i en rumlig kontekst og den usikkerhed, der er forbundet med lærte modeller, er lærte indeks fortsat et stærkt værktøj med potentiale for mange typer data.
Learned indexes—machine learning models that predict where data is located—have shown promise for one- and multi-dimensional relational data. This thesis examines whether such indexes also work well for spatial data. We design a projection function that orders spatial points so a model can learn the ordering. Based on this ordering, we train models and build an index with a hierarchical structure and small utility components. The index is designed to support range queries (find all objects in a given area) and nearest neighbor queries (find the closest object). To answer nearest neighbor queries, we convert them into range queries. We compare the speed of our index with an R-tree on datasets of different sizes and distributions. Our evaluation shows that the learned index outperforms the R-tree in most cases. These results indicate that, despite challenges specific to spatial data and the uncertainty inherent in learned models, learned indexes remain a powerful tool with potential for many types of data.
[This abstract was generated with the help of AI]
Keywords
Documents