TITLE: R*-Grove: Balanced Spatial Partitioning for Large-scale Datasets 

ABSTRACT: The rapid growth of big spatial data urged the research community to develop
several big spatial data systems. Regardless of their architecture, one of the
fundamental requirements of all these systems is to spatially partition the
data efficiently across machines. The core challenges of big spatial
partitioning are building high spatial quality partitions while simultaneously
taking advantages of distributed processing models by providing load balanced
partitions. Previous works on big spatial partitioning are to reuse existing
index search trees as-is, e.g., the R-tree family, STR, Kd-tree, and Quad-tree,
by building a temporary tree for a sample of the input and use its leaf nodes
as partition boundaries. However, we show in this paper that none of those
techniques has addressed the mentioned challenges completely. This paper
proposes a novel partitioning method, termed R*-Grove, which can partition very
large spatial datasets into high quality partitions with excellent load balance
and block utilization. This appealing property allows R*-Grove to outperform
existing techniques in spatial query processing. R*-Grove can be easily
integrated into any big data platforms such as Apache Spark or Apache Hadoop.
Our experiments show that R*-Grove outperforms the existing partitioning
techniques for big spatial data systems. With all the proposed work publicly
available as open source, we envision that R*-Grove will be adopted by the
community to better serve big spatial data research.
The rapid growth of big spatial data urged the research community to develop
several big spatial data systems. Regardless of their architecture, one of the
fundamental requirements of all these systems is to spatially partition the
data efficiently across machines. The core challenges of big spatial
partitioning are building high spatial quality partitions while simultaneously
taking advantages of distributed processing models by providing load balanced
partitions. Previous works on big spatial partitioning are to reuse existing
index search trees as-is, e.g., the R-tree family, STR, Kd-tree, and Quad-tree,
by building a temporary tree for a sample of the input and use its leaf nodes
as partition boundaries. However, we show in this paper that none of those
techniques has addressed the mentioned challenges completely. This paper
proposes a novel partitioning method, termed R*-Grove, which can partition very
large spatial datasets into high quality partitions with excellent load balance
and block utilization. This appealing property allows R*-Grove to outperform
existing techniques in spatial query processing. R*-Grove can be easily
integrated into any big data platforms such as Apache Spark or Apache Hadoop.
Our experiments show that R*-Grove outperforms the existing partitioning
techniques for big spatial data systems. With all the proposed work publicly
available as open source, we envision that R*-Grove will be adopted by the
community to better serve big spatial data research.
R*-Grove: Balanced Spatial Partitioning for Large-scale Datasets
http://arxiv.org/abs/2007.11651v1