Distributed MapReduce processing of location-based aggregate queries in road networks

Recently, the research community focuses on processing various types of location-based queries (or LBQs for short) (e.g., the range and nearest neighbor queries) on spatial objects of the same type in road networks, in which the road distance from objects to the query object is an important metric for determining the query result and needs to be calculated based on the connectivity of the network. The LBQs can be used to find the spatial objects with better spatial closeness (i.e., the shorter road distance to the query object). In many applications, information about the neighboring relationship between different types of objects may be more attractive to the user. As such, the location-based aggregate queries (or LBAggQs for short) are proposed, which consider not only the spatial closeness of objects but also the neighboring relationship between objects. However, the processing techniques for the LBAggQs are mainly based on a centralized paradigm, and hence suffer from highly dynamic environments where a large number of LBAggQs is issued concurrently. In this paper, a distributed processing technique, based on the MapReduce platform, is developed to answer multiple LBAggQs. Three tables \(T^{dist}_{o,o}\) $T_{o,o}^{\mathit{dist}}$ , \(T^{dist}_{o,p}\) $T_{o,p}^{\mathit{dist}}$ , and \(T^{dist}_{p,p}\) $T_{p,p}^{\mathit{dist}}$ are first used to maintain information of the road distances between objects, and then evenly partitioned by a grid structure. With the three tables, a MapReduce-based algorithm, called the MRSAggDQ algorithm, is designed for query processing in a distributed manner. Finally, an extensive set of experiments using two real road networks is conducted to measure the average running time for different numbers of LBAggQs to be processed concurrently. The experimental results demonstrate the efficiency and the scalability of the proposed methods.