SATO: A spatial data partitioning framework for scalable query processing

Scalable spatial query processing relies on effective spatial data partitioning for query parallelization, data pruning, and load bal-ancing. These are often challenged by the intrinsic characteristics of spatial data, such as high skew in data distribution and high complexity of irregular multi-dimensional objects. In this demo, we present SATO, a spatial data partitioning framework that can quickly analyze and partition spatial data with an optimal spatial partitioning strategy for scalable query processing. SATO works in following steps: 1) Sample, which samples a small fraction of in-put data for analysis, 2) Analyze, which quickly analyzes sampled data to find an optimal partition strategy, 3) Tear, which provides data skew aware partitioning and supports MapReduce based scal-able partitioning, and 4) Optimize, which collects succinct parti-tion statistics for potential query optimization. SATO also provides multiple level partitioning, which can be used to significantly im-prove window based queries in cloud based spatial query process-ing systems. SATO comes with a visualization component that pro-vides heat maps and histograms for qualitative evaluation. SATO has been implemented within the Hadoop-GIS, a high performance spatial data warehousing system over MapReduce. SATO is also released as an independent software package to support various scalable spatial query processing systems. Our experiments have demonstrated that SATO can generate much balanced partition-ing that can significantly improve spatial query performance with MapReduce comparing to traditional spatial partitioning approaches.