A Learned Bucket Index Supporting Spatial Queries

Student thesis: Master Thesis and HD Thesis

  • Martin Folmer
  • Theevaahar Karunanithi
  • Raphael Neumann
4. term, Software, Master (Master Programme)
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.
Publication date2019
Number of pages14
ID: 305265882