A Learned Bucket Index Supporting Spatial Queries

Studenteropgave: Kandidatspeciale og HD afgangsprojekt

  • Martin Folmer
  • Theevaahar Karunanithi
  • Raphael Neumann
4. semester, Software, Kandidat (Kandidatuddannelse)
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.
Antal sider14
ID: 305265882