The Case for Learned Spatial Indexes

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

TL;DR

This paper explores integrating machine learning models into classical spatial indexes (like Grid files and Quadtrees) to accelerate spatial range queries. By replacing standard binary search with a learned index during the partition "refinement" phase, the authors achieve up to a 39.5% speedup, demonstrating that 1D grid partitioning schemes benefit significantly more from learned indexes than 2D tree-based structures.

What Problem Does This Paper Address?

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 want to know if replacing traditional search algorithms with learned models inside spatial partitions actually speeds up spatial range queries, and under what conditions.

Methods

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.

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

Datasets

The authors evaluated their approach 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 (which follow the underlying data's geographic distribution) and uniform queries. They varied query selectivity from a highly specific 0.00001% (fetching a handful of records) up to a broader 1.0%.

Key Insights and Ideas

  • Selectivity dictates the bottleneck: For low selectivity queries (e.g., "find a coffee shop within 1 block"), the index lookup and refinement phases dominate the execution time. Here, learned indexes shine. For high selectivity queries (e.g., "find all taxi rides in Manhattan today"), the scan phase dominates, diluting the benefits of a faster search model.
  • 1D vs. 2D Partitioning: 1D grid partitioning techniques (Fixed/Adaptive grid) benefit massively from learned models, while 2D techniques (Quadtree, STR) do not.
  • The "Why" behind the 1D/2D divide: 2D trees do most of their pruning during the Index Lookup phase. This results in a large number of partitions that contain very few points (often <1,000). Running a learned model on such tiny arrays introduces overhead that negates its benefits. Conversely, 1D grids have fewer, much larger partitions, making the O(1) lookup of a learned model vastly superior to an 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 Query Performance: For skewed queries, a Fixed-grid using learned refinement is 1.23x to 1.83x faster than its closest 2D competitor (Quadtree).
  • The Quadtree Exception: Quadtrees still win for uniform queries (up to 2.68x faster than Fixed-grid on the OSM dataset) because they efficiently skip over sparse, unpopulated regions of the map during the lookup phase.
  • Build Times: Grid-based indexes are much faster to construct. Fixed-grid builds roughly 2x faster than the STRtree.

Limitations and Future Work

  • In-Memory Assumption: The study assumes all data and indexes fit entirely in RAM. The authors acknowledge that for disk-based systems, I/O costs would dominate. In an on-disk scenario, 2D partitioning is likely better because partition sizes can be strictly aligned with physical disk page sizes to minimize I/O.
  • Textbook Implementations: The paper uses standard, textbook implementations of Quadtrees and K-d trees. Future work could involve "learning" the tree structures themselves—for instance, by linearizing Quadtree cells using a Z-order curve and storing those cell identifiers directly in a learned index.

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 Jialin Ding and Ibrahim Sabek and Alfons Kemper},
  title = {{The Case for Learned Spatial Indexes}},
  booktitle = {AIDB@VLDB},
  year = {2020},
  url = {https://openreview.net/forum?id=K3gn1TB19n},
}

Loading related content...

Figure