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: h24b8b2bacc639070
Venue: VLDB
Year: 2022
Pagerank: 5.2724071e-05
Overall Rank: 8,809 | 40.78%
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
9,056	Aster: Enhancing LSM-structures for Scalable Graph Database	2025	SIGMOD	5.2295363e-05
9,181	Structural Designs Meet Optimality: Exploring Optimized LSM-tree Structures in A Colossal Configuration Space	2024	SIGMOD	5.2118872e-05
11,707	ST4ML: Machine Learning Oriented Spatio-Temporal Data Processing at Scale	2023	SIGMOD	4.9793485e-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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
123	Schism: a Workload-Driven Approach to Database Replication and Partitioning	2010	VLDB	0.00030762995
335	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00020660268
922	AsterixDB: A Scalable, Open Source BDMS	2014	VLDB	0.00013068048
1,178	Simba: Efficient In-Memory Spatial Analytics	2016	SIGMOD	0.00011632691
1,405	A Model for the Prediction of R-tree Performance	1996	PODS	0.0001076417
1,875	Storage Management in AsterixDB	2014	VLDB	9.4576907e-05
2,162	Selectivity Estimation in Spatial Databases	1999	SIGMOD	8.935022e-05
2,176	Efficient Processing of k Nearest Neighbor Joins using MapReduce	2012	VLDB	8.9159001e-05
2,827	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	7.967335e-05
3,445	Slalom: Coasting Through Raw Data via Adaptive Partitioning and Indexing	2017	VLDB	7.2943981e-05
4,219	Spatial Partitioning Techniques in SpatialHadoop	2015	VLDB	6.7262869e-05
4,251	Selectivity Estimation for Spatio-Temporal Queries to Moving Objects	2002	SIGMOD	6.7020655e-05
5,526	AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data	2015	VLDB	6.0937354e-05
6,418	Performance of Data-Parallel Spatial Operations	1994	VLDB	5.7907247e-05
6,578	Workload-Aware Indexing of Continuously Moving Objects	2009	VLDB	5.744723e-05
7,933	Tornado: A Distributed Spatio-Textual Stream Processing System	2015	VLDB	5.4233012e-05
8,158	ScalaGiST: Scalable Generalized Search Trees for MapReduce Systems [Innovative Systems Paper]	2014	VLDB	5.3875848e-05

Semantically Similar Papers

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