# WISK: A Workload-aware Learned Index for Spatial Keyword Queries

arXiv: https://arxiv.org/abs/2302.14287 · HTML: https://mlsanity.com/paper/2302.14287/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 83 references that are in the map.
- First posted on arXiv 28 Feb 2023.

## Builds on (most cited first, 20 of 20)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSP](https://mlsanity.com/paper/1809.02721/) (2018)
- [ALEX: An Updatable Adaptive Learned Index](https://mlsanity.com/paper/1905.08898/) (2019)
- [Online 3D Bin Packing with Constrained Deep Reinforcement Learning](https://mlsanity.com/paper/2006.14978/) (2020)
- [RadixSpline: A Single-Pass Learned Index](https://mlsanity.com/paper/2004.14541/) (2020)
- [Learning Multi-dimensional Indexes](https://mlsanity.com/paper/1912.01668/) (2019)
- [Benchmarking Learned Indexes](https://mlsanity.com/paper/2006.12804/) (2020)
- [Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads](https://mlsanity.com/paper/2006.13282/) (2020)
- [Dynamic Context Selection for Document-level Neural Machine Translation via Reinforcement Learning](https://mlsanity.com/paper/2010.04314/) (2020)
- [Are We Ready For Learned Cardinality Estimation?](https://mlsanity.com/paper/2012.06743/) (2020)
- [Qd-tree: Learning Data Layouts for Big Data Analytics](https://mlsanity.com/paper/2004.10898/) (2020)
- [The PGM-index: a multicriteria, compressed and learned approach to data indexing](https://mlsanity.com/paper/1910.06169/) (2019)
- [t-Soft Update of Target Network for Deep Reinforcement Learning](https://mlsanity.com/paper/2008.10861/) (2020)
- [Updatable Learned Index with Precise Positions](https://mlsanity.com/paper/2104.05520/) (2021)
- [A Sigmoidal Approximation for Chance-Constrained Nonlinear Programs](https://mlsanity.com/paper/2004.02402/) (2020)
- [A Reinforcement Learning Based R-Tree for Spatial Data Indexing in Dynamic Environments](https://mlsanity.com/paper/2103.04541/) (2021)
- [GB-KMV: An Augmented KMV Sketch for Approximate Containment Similarity Search](https://mlsanity.com/paper/1809.00458/) (2018)

## Built on by (most cited first, 6 of 6)

- [A Survey of Learned Indexes for the Multi-dimensional Space](https://mlsanity.com/paper/2403.06456/) (2024)
- [Accelerating String-Key Learned Index Structures via Memoization-based Incremental Training](https://mlsanity.com/paper/2403.11472/) (2024)
- [EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean Pathfinding](https://mlsanity.com/paper/2408.11341/) (2024)
- [ACE: A Cardinality Estimator for Set-Valued Queries](https://mlsanity.com/paper/2503.14929/) (2025)
- [Sig2Model: A Boosting-Driven Model for Updatable Learned Indexes](https://mlsanity.com/paper/2509.20781/) (2025)
- [A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval](https://mlsanity.com/paper/2609.19855/) (2026)

## Abstract (arXiv)

Spatial objects often come with textual information, such as Points of Interest (POIs) with their descriptions, which are referred to as geo-textual data. To retrieve such data, spatial keyword queries that take into account both spatial proximity and textual relevance have been extensively studied. Existing indexes designed for spatial keyword queries are mostly built based on the geo-textual data without considering the distribution of queries already received. However, previous studies have shown that utilizing the known query distribution can improve the index structure for future query processing. In this paper, we propose WISK, a learned index for spatial keyword queries, which self-adapts for optimizing querying costs given a query workload. One key challenge is how to utilize both structured spatial attributes and unstructured textual information during learning the index. We first divide the data objects into partitions, aiming to minimize the processing costs of the given query workload. We prove the NP-hardness of the partitioning problem and propose a machine learning model to find the optimal partitions. Then, to achieve more pruning power, we build a hierarchical structure based on the generated partitions in a bottom-up manner with a reinforcement learning-based approach. We conduct extensive experiments on real-world datasets and query workloads with various distributions, and the results show that WISK outperforms all competitors, achieving up to 8x speedup in querying time with comparable storage overhead.