Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing

Summary: Waffle: a disk-based spatial index combining space- and data-partitioning to be workload-aware and query-sensitive, balancing fast spatial queries with low-cost updates. Offers optimal-page bulk-loading, zero-overlap dynamic updates, and adaptive maintenance to tune the query/update tradeoff to workload and query distributions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13321
Venue: VLDB
Year: 2023
Pagerank: 4.5372925e-05
Overall Rank: 8,359 | 41.85%
DOI: 10.14778/3574245.3574253

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,948	One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting	2024	SIGMOD	4.423786e-05
9,827	PLATON: Top-down R-tree Packing with Learned Partition Policy	2023	SIGMOD	4.2751057e-05
10,312	A Workload-Aware Encrypted Index for Efficient Privacy-Preserving Range Queries	2026	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 27 of 27 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.0032169493
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018397217
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538
47	Nearest Neighbor Queries	1995	SIGMOD	0.0007015885
56	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00065631356
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.0005181666
102	The Case for Learned Index Structures	2018	SIGMOD	0.00049545203
148	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041182766
284	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028994728
354	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00026137988
598	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00019474545
631	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00018935493
1,067	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00014327945
1,478	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00011762542
1,768	Closest Pair Queries in Spatial Databases	2000	SIGMOD	0.00010622873
1,889	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00010200865
1,933	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010038508
1,983	Optimizing Multidimensional Index Trees for Main Memory Access	2001	SIGMOD	9.8638201e-05
2,115	LISA: A Learned Index Structure for Spatial Data	2020	SIGMOD	9.5257379e-05
2,144	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.4416732e-05
2,360	Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring	2005	SIGMOD	8.9605432e-05
2,457	The Spatial Skyline Queries	2006	VLDB	8.769229e-05
2,678	Effectively Learning Spatial Indices	2020	VLDB	8.3252088e-05
3,255	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3160522e-05
3,650	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD	6.8783391e-05
6,202	A Benchmark for Evaluating Moving Object Indexes	2008	VLDB	5.1593242e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,029	Spatial Online Sampling and Aggregation	2016	VLDB	6.51315e-05
12,497	Efficient Query Processing on Unstructured Tetrahedral Meshes	2006	SIGMOD	4.1945683e-05
9,489	Waffle: An Online Oblivious Datastore for Protecting Data Access Patterns	2023	SIGMOD	4.3341665e-05
9,767	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2856106e-05
9,256	An Adaptive Updating Protocol for Reducing Moving Object Database Workload	2010	VLDB	4.3690661e-05
8,636	WISK: A Workload-aware Learned Index for Spatial Keyword Queries	2023	SIGMOD	4.4801284e-05
6,819	Workload-Aware Indexing of Continuously Moving Objects	2009	VLDB	4.9158166e-05
5,790	AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data	2015	VLDB	5.3269734e-05
11,279	Demonstrating Waffle: A Self-driving Grid Index	2023	VLDB	4.1945683e-05
9,605	Waffle: In-memory Grid Index for Moving Objects with Reinforcement Learning-based Configuration Tuning System	2022	VLDB	4.3177432e-05