Incremental Partitioning for Efficient Spatial Data Analytics

Summary: Incrementally maintains block-level spatial partitions under bulk inserts and deletes in distributed file systems, bridging scalable analytics with update support. Formalizes the NP-hard problem, introduces a query-aware cost model, and delivers three outperforming implementations. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 13131
Venue: VLDB
Year: 2022
Pagerank: 5.3934068e-05
Overall Rank: 8,644 | 40.70%
DOI: 10.14778/3494124.3494150

Incoming Non-self Citations Over Time

Authors

1. Tin Vu (University of California Riverside)
2. Ahmed Eldawy (University of California Riverside)
3. Vagelis Hristidis (University of California Riverside)
4. Vassilis Tsotras (University of California Riverside)

BibTeX Citation

@article{vu_vldb22,
        title = {{Incremental Partitioning for Efficient Spatial Data Analytics}},
        author = {Vu, Tin and Eldawy, Ahmed and Hristidis, Vagelis and Tsotras, Vassilis},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {3},
        pages = {713--726},
        doi = {10.14778/3494124.3494150},
        url = {https://doi.org/10.14778/3494124.3494150},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,896	Aster: Enhancing LSM-structures for Scalable Graph Database	2025	SIGMOD	5.3495662e-05
9,021	Structural Designs Meet Optimality: Exploring Optimized LSM-tree Structures in A Colossal Configuration Space	2024	SIGMOD	5.3305499e-05
11,392	ST4ML: Machine Learning Oriented Spatio-Temporal Data Processing at Scale	2023	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
126	Schism: a Workload-Driven Approach to Database Replication and Partitioning	2010	VLDB	0.00030779127
329	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00021068647
1,015	AsterixDB: A Scalable, Open Source BDMS	2014	VLDB	0.00012647763
1,175	Simba: Efficient In-Memory Spatial Analytics	2016	SIGMOD	0.00011812263
1,373	A Model for the Prediction of R-tree Performance	1996	PODS	0.0001098638
1,874	Storage Management in AsterixDB	2014	VLDB	9.5750002e-05
2,127	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.127762e-05
2,137	Efficient Processing of k Nearest Neighbor Joins using MapReduce	2012	VLDB	9.110238e-05
2,774	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	8.1372328e-05
3,413	Slalom: Coasting Through Raw Data via Adaptive Partitioning and Indexing	2017	VLDB	7.4326381e-05
4,148	Spatial Partitioning Techniques in SpatialHadoop	2015	VLDB	6.872045e-05
4,174	Selectivity Estimation for Spatio-Temporal Queries to Moving Objects	2002	SIGMOD	6.8515543e-05
5,395	AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data	2015	VLDB	6.2331619e-05
6,298	Performance of Data-Parallel Spatial Operations	1994	VLDB	5.9227722e-05
6,458	Workload-Aware Indexing of Continuously Moving Objects	2009	VLDB	5.8736158e-05
7,794	Tornado: A Distributed Spatio-Textual Stream Processing System	2015	VLDB	5.5429908e-05
7,990	ScalaGiST: Scalable Generalized Search Trees for MapReduce Systems [Innovative Systems Paper]	2014	VLDB	5.5107935e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,480	LocationSpark: A Distributed In-Memory Data Management System for Big Spatial Data	2016	VLDB
2	5,202	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB
3	6,547	Optimal Splitters for Temporal and Multi-version Databases	2013	SIGMOD
4	3,429	Angle-based Space Partitioning for Efficient Parallel Skyline Computation	2008	SIGMOD
5	6,619	(Almost) Optimal Parallel Block Access for Range Queries	2000	PODS
6	1,044	Fine-grained Partitioning for Aggressive Data Skipping	2014	SIGMOD
7	12,141	A Demonstration of AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data	2015	VLDB
8	12,191	A Partitioning Framework for Aggressive Data Skipping	2014	VLDB
9	5,395	AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data	2015	VLDB
10	4,148	Spatial Partitioning Techniques in SpatialHadoop	2015	VLDB