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: 13322
Venue: VLDB
Year: 2023
Pagerank: 4.5329424e-05
Overall Rank: 8,354 | 41.94%
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,952	One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting	2024	SIGMOD	4.4195459e-05
9,826	PLATON: Top-down R-tree Packing with Learned Partition Policy	2023	SIGMOD	4.2710095e-05
10,324	A Workload-Aware Encrypted Index for Efficient Privacy-Preserving Range Queries	2026	VLDB	4.1905499e-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.0032118946
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018380955
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
48	Nearest Neighbor Queries	1995	SIGMOD	0.0006954126
56	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00065500256
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00051785122
101	The Case for Learned Index Structures	2018	SIGMOD	0.00049778866
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
301	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028396714
356	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00026091196
597	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00019450818
628	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00018957327
1,055	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00014391376
1,464	Learning Multi-dimensional Indexes	2020	SIGMOD	0.0001184772
1,769	Closest Pair Queries in Spatial Databases	2000	SIGMOD	0.00010608375
1,887	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00010201938
1,924	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010075677
1,987	Optimizing Multidimensional Index Trees for Main Memory Access	2001	SIGMOD	9.8561164e-05
2,108	LISA: A Learned Index Structure for Spatial Data	2020	SIGMOD	9.5283642e-05
2,144	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.4375327e-05
2,342	Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring	2005	SIGMOD	9.0005088e-05
2,457	The Spatial Skyline Queries	2006	VLDB	8.7618183e-05
2,676	Effectively Learning Spatial Indices	2020	VLDB	8.326321e-05
3,259	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3101573e-05
3,653	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD	6.8725114e-05
6,171	A Benchmark for Evaluating Moving Object Indexes	2008	VLDB	5.1705603e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,032	Spatial Online Sampling and Aggregation	2016	VLDB	6.5131946e-05
12,506	Efficient Query Processing on Unstructured Tetrahedral Meshes	2006	SIGMOD	4.1905499e-05
8,443	Waffle: An Online Oblivious Datastore for Protecting Data Access Patterns	2023	SIGMOD	4.5043421e-05
9,769	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2815042e-05
9,166	An Adaptive Updating Protocol for Reducing Moving Object Database Workload	2010	VLDB	4.380727e-05
8,636	WISK: A Workload-aware Learned Index for Spatial Keyword Queries	2023	SIGMOD	4.4758336e-05
6,766	Workload-Aware Indexing of Continuously Moving Objects	2009	VLDB	4.9280867e-05
5,800	AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data	2015	VLDB	5.3218628e-05
11,281	Demonstrating Waffle: A Self-driving Grid Index	2023	VLDB	4.1905499e-05
9,605	Waffle: In-memory Grid Index for Moving Objects with Reinforcement Learning-based Configuration Tuning System	2022	VLDB	4.3136057e-05