AQWA: Adaptive query-workload-aware partitioning of big spatial data

The unprecedented spread of location-aware devices has resulted in a plethora of location-based services in which huge amounts of spa- tial data need to be efficiently processed by large-scale computing clusters. Existing cluster-based systems for processing spatial data employ static data-partitioning structures that cannot adapt to data changes, and that are insensitive to the query workload. Hence, these systems are incapable of consistently providing good per- formance. To close this gap, we present AQWA, an adaptive and query-workload-aware mechanism for partitioning large-scale spa- tial data. AQWA does not assume prior knowledge of the data dis- tribution or the query workload. Instead, as data is consumed and queries are processed, the data partitions are incrementally updated. With extensive experiments using real spatial data from Twitter, and various workloads of range and k-nearest-neighbor queries, we demonstrate that AQWA can achieve an order of magnitude en- hancement in query performance compared to the state-of-the-art systems.