Load balancing for distributed processing of spatial data stream

Abstract

A spatial big data stream is an unbounded and continuous data stream with geospatial features such as point, line, and polygon. With the evolution of Internet-of-Things technology, it has become much easier to acquire spatial big data streams from various sources such as smart cars, road network sensors, smart phones, and geo-tagged Social Network Services. Distributed and real-time processing are required to effectively process spatial big data streams

however, existing approaches such as spatial databases or spatial Hadoop are unable to meet these requirements. Distributed Stream Processing System implemented with spatial operations may be one of the most plausible solutions, but it also has a load imbalance issue. The spatial data streams inherently have a skewed and dynamically changing distribution

therefore, the system may display poor performance unless the entire load is efficiently distributed among workers. Previous studies to solve the load imbalance problem is not directly applicable to processing spatial queries since it does not consider the spatial locality of data. In this paper, we propose a load balancing algorithm, Adaptive Spatial Key Grouping (ASKG), which is specialized for spatial data stream. The main idea of ASKG is to learn the previous distribution of a data stream and utilize it to suggest a new grouping scheme that evenly distributes the incoming data stream into workers. By repeating the procedure periodically, the system can balance loads among workers adaptively to the spatial distribution of data stream. To evaluate the validity of our proposed algorithm in a variety of environments, we performed an evaluation with real datasets by varying the number of workers, input rate, and processing overhead. Compared to two other alternative algorithms, ASKG reduced load imbalance up to around 95%, leading directly to an increase in throughput of up to 147%, and to a decrease in latency of up to 99%.