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.4451309e-05
Overall Rank: 1,878 | 87.38%
DOI: 10.14778/3407790.3407829

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,636	Are Updatable Learned Indexes Ready?	2022	VLDB	8.1941043e-05
2,866	APEX: A High-Performance Learned Index on Persistent Memory	2022	VLDB	7.9258875e-05
3,697	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB	7.0882335e-05
3,803	CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm	2022	VLDB	7.0127652e-05
4,375	DILI: A Distribution-Driven Learned Index	2023	VLDB	6.6292167e-05
4,850	The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data	2023	SIGMOD	6.3808017e-05
4,890	Can Learned Models Replace Hash Functions?	2023	VLDB	6.3682031e-05
5,041	LSched: A Workload-Aware Learned Query Scheduler for Analytical Database Systems	2022	SIGMOD	6.3006152e-05
5,537	Updatable Learned Indexes Meet Disk-Resident DBMS - From Evaluations to Design Choices	2023	SIGMOD	6.0919359e-05
5,571	FILM: a Fully Learned Index for Larger-than-Memory Databases	2023	VLDB	6.080267e-05
6,595	LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves	2023	VLDB	5.7413481e-05
6,663	Range Search over Encrypted Multi-Attribute Data	2023	VLDB	5.7166181e-05
6,719	Replicated Layout for In-Memory Database Systems	2022	VLDB	5.6985717e-05
6,821	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD	5.6720444e-05
7,395	LiteHST: A Tree Embedding based Method for Similarity Search	2023	SIGMOD	5.5370691e-05
8,179	Towards Designing and Learning Piecewise Space-Filling Curves	2023	VLDB	5.3826446e-05
8,196	WISK: A Workload-aware Learned Index for Spatial Keyword Queries	2023	SIGMOD	5.3794981e-05
8,369	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	5.3450708e-05
8,879	Spatial Query Optimization With Learning	2024	VLDB	5.2568354e-05
9,145	One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting	2024	SIGMOD	5.220115e-05
9,919	Waffle: In-memory Grid Index for Moving Objects with Reinforcement Learning-based Configuration Tuning System	2022	VLDB	5.1103839e-05
10,002	BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data	2024	SIGMOD	5.0979044e-05
10,168	PLATON: Top-down R-tree Packing with Learned Partition Policy	2023	SIGMOD	5.0682654e-05
10,475	LINE: A Learned Index with Group-Enhanced Leaves and Cache-Optimized Inner Tree	2026	SIGMOD	4.9793485e-05
10,480	Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions	2026	SIGMOD	4.9793485e-05
10,656	LM-Tree: A Hybrid Learned Index for Similarity Search in Metric Spaces	2026	SIGMOD	4.9793485e-05
10,751	Toward Drift-Aware Database Benchmarking	2026	VLDB	4.9793485e-05
11,064	LiBox: A Learned Index as an Array to Minimize Last-Mile Search	2026	VLDB	4.9793485e-05
11,113	Optimizing Block Skipping for High-Dimensional Data with Learned Adaptive Curve	2025	SIGMOD	4.9793485e-05
11,660	Efficient Cost Modeling of Space-filling Curves	2024	VLDB	4.9793485e-05
11,788	Demonstrating Waffle: A Self-driving Grid Index	2023	VLDB	4.9793485e-05
11,843	Faster and Better Solution to Embed Lp Metrics by Tree Metrics	2022	SIGMOD	4.9793485e-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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0008122792
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051312804
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046284649
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045337853
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00031645463
264	A Class of Data Structures for Associative Searching	1984	PODS	0.00022757762
335	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00020660268
430	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018409112
463	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017804544
555	SageDB: A Learned Database System	2019	CIDR	0.00016506678
743	Client-Server Paradise	1994	VLDB	0.00014311524
779	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014030069
868	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013354403
886	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.0001325914
1,132	Qd-tree: Learning Data Layouts for Big Data Analytics	2020	SIGMOD	0.00011898257
1,226	Fractals for Secondary Key Retrieval	1989	PODS	0.00011431306
1,446	LISA: A Learned Index Structure for Spatial Data	2020	SIGMOD	0.00010629222
1,903	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.4032472e-05
2,064	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.0942902e-05
3,034	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.7330662e-05
7,303	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	5.5598057e-05

Semantically Similar Papers

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