The Case for Learned Spatial Indexes

Varun Pandey, Alexander van Renen, Andreas Kipf, Ibrahim Sabek, Jialin Ding, Alfons Kemper

Abstract

Spatial data is ubiquitous. Massive amounts of data are generated every day from billions of GPS-enabled devices such as cell phones, cars, sensors, and various consumer-based applications such as Uber, Tinder, location-tagged posts in Facebook, Twitter, Instagram, etc. This exponential growth in spatial data has led the research community to focus on building systems and applications that can process spatial data efficiently. In the meantime, recent research has introduced learned index structures. In this work, we use techniques proposed from a state-of-the art learned multi-dimensional index structure (namely, Flood) and apply them to five classical multi-dimensional indexes to be able to answer spatial range queries. By tuning each partitioning technique for optimal performance, we show that (i) machine learned search within a partition is faster by 11.79% to 39.51% than binary search when using filtering on one dimension, (ii) the bottleneck for tree structures is index lookup, which could potentially be improved by linearizing the indexed partitions (iii) filtering on one dimension and refining using machine learned indexes is 1.23x to 1.83x times faster than closest competitor which filters on two dimensions, and (iv) learned indexes can have a significant impact on the performance of low selectivity queries while being less effective under higher selectivities.

Introduction

The explosion of spatial data—from GPS devices, ride-sharing apps, and social media check-ins—demands highly efficient spatial databases. Recently, the database community has been captivated by "learned indexes," which use machine learning models to predict the location of a key in a sorted dataset, often outperforming traditional structures like B-trees. However, spatial data is multi-dimensional, meaning it lacks a single inherent sort order. This paper investigates whether the impressive performance gains of 1D learned indexes can be grafted onto classical multi-dimensional spatial partitioning techniques. Specifically, the authors explore replacing traditional search algorithms with learned models inside spatial partitions to accelerate spatial range queries.

Methodology

The authors break spatial query processing into three distinct phases:

  1. Index Lookup: Finding the spatial partitions that intersect with the query.
  2. Refinement: Finding the query's lower bound within a specific partition.
  3. Scan: Iterating through the points to find matches.

They evaluate five classic spatial partitioning schemes: Fixed-grid, Adaptive-grid, Quadtree, K-d tree, and STR packed R-tree.

Illustration of the different partitioning techniques evaluated in the study.

The core innovation occurs in the Refinement phase. Within each spatial partition, data is sorted along a single dimension (e.g., longitude). Instead of using a standard binary search to find the query's starting point, the authors implement RadixSpline, a state-of-the-art learned index. They tune partition sizes for each technique to find the optimal balance between index lookup, refinement, and scanning time.

Experimental Setup

The approach was evaluated using three large-scale datasets with distinct spatial distributions:

  • NYC Taxi Rides: 305 million ride locations (highly clustered in central New York).
  • NYC Tweets: 83 million geo-tagged tweets (more geographically spread out).
  • Open Street Maps (OSM): 200 million point records representing map nodes.

To test robustness, they generated two types of query workloads: skewed queries (following the underlying data's geographic distribution) and uniform queries. They varied query selectivity from a highly specific 0.00001% up to a broader 1.0%.

Performance Analysis

The effectiveness of learned indexes is heavily influenced by query selectivity and the underlying partitioning scheme.

Query time breakdown comparing Machine Learned (ML) refinement vs. Binary Search (BS) across different selectivity levels.

The Impact of Selectivity

For low selectivity queries, index lookup and refinement phases dominate execution time. In these scenarios, learned indexes provide significant gains (e.g., a 25% gain for ML over BS). As selectivity increases, the scan phase becomes the primary bottleneck, which dilutes the benefits of a faster search model.

1D vs. 2D Partitioning

1D grid partitioning techniques (Fixed/Adaptive grid) benefit significantly more from learned models than 2D tree-based structures (Quadtree, STR). 2D trees perform most pruning during the lookup phase, resulting in many small partitions (often <1,000 points). The overhead of a learned model on such small arrays often negates its benefits. In contrast, 1D grids produce fewer, larger partitions where the O(1) lookup of a learned model is vastly superior to O(log N) binary search.

Key Results

  • Refinement Speedup: Replacing binary search with a learned index within a partition yields an 11.79% to 39.51% speedup when filtering on one dimension.
  • Overall Performance: For skewed queries, a Fixed-grid using learned refinement is 1.23x to 1.83x faster than its closest 2D competitor (Quadtree).
  • Build Times: Grid-based indexes are much faster to construct. Fixed-grid builds roughly 2x faster than the STRtree.

Conclusion

This study demonstrates that integrating machine learning into spatial indexing can yield substantial performance improvements, particularly for 1D partitioning schemes under low selectivity. While 2D trees remain competitive for uniform queries, learned 1D grids excel on skewed real-world data. Future work could explore "learning" the tree structures themselves, perhaps by linearizing multi-dimensional cells using space-filling curves like Z-order and indexing them with learned models.

Summary updated

Abstract

Spatial data is ubiquitous. Massive amounts of data are generated every day from billions of GPS-enabled devices such as cell phones, cars, sensors, and various consumer-based applications such as Uber, Tinder, location-tagged posts in Facebook, Twitter, Instagram, etc. This exponential growth in spatial data has led the research community to focus on building systems and applications that can process spatial data efficiently. In the meantime, recent research has introduced learned index structures. In this work, we use techniques proposed from a state-of-the art learned multi-dimensional index structure (namely, Flood) and apply them to five classical multi-dimensional indexes to be able to answer spatial range queries. By tuning each partitioning technique for optimal performance, we show that (i) machine learned search within a partition is faster by 11.79\% to 39.51\% than binary search when using filtering on one dimension, (ii) the bottleneck for tree structures is index lookup, which could potentially be improved by linearizing the indexed partitions (iii) filtering on one dimension and refining using machine learned indexes is 1.23x to 1.83x times faster than closest competitor which filters on two dimensions, and (iv) learned indexes can have a significant impact on the performance of low selectivity queries while being less effective under higher selectivities.
BibTeX
@inproceedings{pandey2020case,
  author = {Varun Pandey and Alexander van Renen and Andreas Kipf and Ibrahim Sabek and Jialin Ding and Alfons Kemper},
  title = {{The Case for Learned Spatial Indexes}},
  booktitle = {AIDB@VLDB},
  year = {2020},
  url = {https://openreview.net/forum?id=K3gn1TB19n},
}
Figure