Effectively Learning Spatial Indices

Summary: Proposes a learned index for 2D spatial data using rank-space ordering to form an indexable sequence and block-wise learning for scalability. A recursive partitioning strategy, with experiments on 100M+ points, yields query speedups of over an order of magnitude versus R-trees and prior learned indexes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h8961beac75f60add
Venue: VLDB
Year: 2020
Pagerank: 9.4498401e-05
Overall Rank: 1,877 | 87.39%
DOI: 10.14778/3407790.3407829
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Jianzhong Qi (University of Melbourne)
2. Guanli Liu (University of Melbourne)
3. Christian S. Jensen (Aalborg University)
4. Lars Kulik (University of Melbourne)

BibTeX Citation

@article{qi_vldb20,
        title = {{Effectively Learning Spatial Indices}},
        author = {Qi, Jianzhong and Liu, Guanli and Jensen, Christian S. and Kulik, Lars},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {11},
        pages = {2341--2354},
        doi = {10.14778/3407790.3407829},
        url = {https://doi.org/10.14778/3407790.3407829},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 32 of 32 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,582	Are Updatable Learned Indexes Ready?	2022	VLDB	8.2641447e-05
2,861	APEX: A High-Performance Learned Index on Persistent Memory	2022	VLDB	7.9295281e-05
3,621	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB	7.1510804e-05
3,710	CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm	2022	VLDB	7.0775695e-05
4,366	DILI: A Distribution-Driven Learned Index	2023	VLDB	6.6330579e-05
4,851	The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data	2023	SIGMOD	6.377837e-05
4,890	Can Learned Models Replace Hash Functions?	2023	VLDB	6.3663299e-05
5,043	LSched: A Workload-Aware Learned Query Scheduler for Analytical Database Systems	2022	SIGMOD	6.2979214e-05
5,378	Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices	2023	SIGMOD	6.1551053e-05
5,405	FILM: a Fully Learned Index for Larger-than-Memory Databases	2023	VLDB	6.1435108e-05
6,597	LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves	2023	VLDB	5.7386302e-05
6,613	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD	5.7326443e-05
6,667	Range Search over Encrypted Multi-Attribute Data	2023	VLDB	5.7139119e-05
6,715	Replicated Layout for In-Memory Database Systems	2022	VLDB	5.6989853e-05
7,397	LiteHST: A Tree Embedding based Method for Similarity Search	2023	SIGMOD	5.5344479e-05
8,186	Towards Designing and Learning Piecewise Space-Filling Curves	2023	VLDB	5.3800965e-05
8,204	WISK: A Workload-aware Learned Index for Spatial Keyword Queries	2023	SIGMOD	5.3769515e-05
8,374	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	5.3425405e-05
8,888	Spatial Query Optimization With Learning	2024	VLDB	5.2543468e-05
9,154	One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting	2024	SIGMOD	5.2176438e-05
9,926	Waffle: In-memory Grid Index for Moving Objects with Reinforcement Learning-based Configuration Tuning System	2022	VLDB	5.1079647e-05
10,007	BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data	2024	SIGMOD	5.0954911e-05
10,172	PLATON: Top-down R-tree Packing with Learned Partition Policy	2023	SIGMOD	5.0658661e-05
10,486	LINE: A Learned Index with Group-Enhanced Leaves and Cache-Optimized Inner Tree	2026	SIGMOD	4.9769913e-05
10,491	Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions	2026	SIGMOD	4.9769913e-05
10,667	LM-Tree: A Hybrid Learned Index for Similarity Search in Metric Spaces	2026	SIGMOD	4.9769913e-05
10,761	Toward Drift-Aware Database Benchmarking	2026	VLDB	4.9769913e-05
11,073	LiBox: A Learned Index as an Array to Minimize Last-Mile Search	2026	VLDB	4.9769913e-05
11,122	Optimizing Block Skipping for High-Dimensional Data with Learned Adaptive Curve	2025	SIGMOD	4.9769913e-05
11,666	Efficient Cost Modeling of Space-filling Curves	2024	VLDB	4.9769913e-05
11,794	Demonstrating Waffle: A Self-driving Grid Index	2023	VLDB	4.9769913e-05
11,849	Faster and Better Solution to Embed Lp Metrics by Tree Metrics	2022	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 23 of 23 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0019923528
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011402175
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00081200096
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051292389
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046363107
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045319457
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00031633451
265	A Class of Data Structures for Associative Searching	1984	PODS	0.00022748432
336	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00020652147
422	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018488849
458	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017880664
555	SageDB: A Learned Database System	2019	CIDR	0.0001650754
744	Client-Server Paradise	1994	VLDB	0.00014305129
768	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014107655
869	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013363241
886	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.00013253709
1,128	Qd-tree: Learning Data Layouts for Big Data Analytics	2020	SIGMOD	0.00011901941
1,228	Fractals for Secondary Key Retrieval	1989	PODS	0.00011427053
1,440	LISA: A Learned Index Structure for Spatial Data	2020	SIGMOD	0.00010638444
1,904	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.3990319e-05
2,065	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.0904572e-05
3,035	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.7296096e-05
7,306	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	5.5571749e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,858	Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects	2009	VLDB
2	6,613	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD
3	835	Benchmarking Learned Indexes	2021	VLDB
4	2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD
5	3,621	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB
6	8,888	Spatial Query Optimization With Learning	2024	VLDB
7	1,651	Indexing Land Surface for Efficient kNN Query	2008	VLDB
8	4,851	The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data	2023	SIGMOD
9	10,053	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB
10	40	The Case for Learned Index Structures	2018	SIGMOD