A Learned Bucket Index Supporting Spatial Queries

Folmer, Martin ; Karunanithi, Theevaahar ; Neumann, Raphael

4. term

Software, Master

2019

2019-06-06

14 pages

earned indexes have proven its potentialon one-dimensional and multidimensional relational data.In this paper, we investigate the applicability of learnedindexes in a spatial context. We devise a projectionfunction that orders spatial data into a learnable or-dering. Using this function, we train models over theordering of the data, and build an index consisting of ahierarchical structure and smaller utility components. Wespecifically build this index to accommodate range andnearest neighbor queries. To perform nearest neighborqueries, we convert them into range queries. We comparethe speed of the index to that of the R-tree on the rangeand nearest neighbor queries by testing on datasets ofdifferent distributions and sizes. Through our evaluation,we show that the learned index is able to outperformthe R-tree in most cases. With the implementation ofour learned spatial index, we show that, despite thechallenges that exist within a spatial context and theinherent uncertainty with models, learned indexes remainpowerful tools with potential in many types of data.

index ; learned index ; spatial data ; machine learning ; r-tree

Download
View record in AAU Student Projects