Lune

VLDB2022Top-tier venue

Incremental Partitioning for Efficient Spatial Data Analytics

Tin Vu, Ahmed Eldawy, Vagelis Hristidis, Vassilis J. Tsotras

Abstract

Big spatial data has become ubiquitous, from mobile applications to satellite data. In most of these applications, data is continuously growing to huge volumes. Existing systems for big spatial data organize records at either the record-level or block-level. Systems that use record-level structures include key-value stores and LSM-Tree stores, which support insert and delete operations and they are optimized for highly-selective queries. On the other hand, systems like GeoSpark that use block-level structures (e.g. 128 MB each) are more efficient for analytical queries, but they cannot incrementally maintain the partitioned data and do not support delete operations. This paper proposes a general framework that enables block-level systems to incrementally maintain spatial partitions, in the presence of bulk insertions and deletions, in distributed file system (DFS) blocks. We first formally study the incremental spatial partitioning problem for big data and demonstrate its NP-hardness. Then, we propose a cost model to estimate the performance of queries on the partitioned data and the effect of modifying it as the data grows. After that, we provide three different implementations of the incremental partitioning framework. Comprehensive experiments on large real datasets show that our proposed partitioning algorithms outperforms state-of-the-art spatial partitioning methods.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. LISA: A Learned Index Structure for Spatial DataPengfei Li, Hua Lu, Qian Zheng, Long Yang et al.SIGMOD 2020 · 158 citations
  2. EvenDB: optimizing key-value storage for spatial localityEran Gilad, Edward Bortnikov, Anastasia Braginsky, Yonatan Gottesman et al.EuroSys 2020 · 29 citations
  3. SOLAR: Efficient Spatial Queries on Real-Time LSM-Based StorageJingyi Yang, Jiachen Shi, Jian Chen, Gao CongICDE 2026 · 1 citation
  4. Out-of-Core Parallel Spatial Join Outperforming In-Memory Systems: A BFS-DFS Hybrid ApproachLyuheng Yuan, Da Yan, Akhlaque Ahmad, Jiao Han et al.HPDC 2025
  5. SSTD: A Distributed System on Streaming Spatio-Textual DataYue Chen, Zhida Chen, Gao Cong, Ahmed R. Mahmood et al.VLDB 2020
Dusk over the sea between two cliffs drawn in fine vertical lines