Recently, the join processing of large-scale datasets in MapReduce environments has become an important issue. However, the existing MapReduce-based join algorithms suffer from too much overhead for constructing and updating the data index. Moreover, the similarity computation cost is high because the existing algorithms partition data without considering the data distribution. In this paper, we propose two grid-based join algorithms for MapReduce. First, we propose a similarity join algorithm that evenly distributes join candidates using a dynamic grid index, which partitions data considering data density and similarity threshold. We use a bottom-up approach by merging initial grid cells into partitions and assigning them to MapReduce jobs. Second, we propose a k-NN join query processing algorithm for MapReduce. To reduce the data transmission cost, we determine an optimal grid cell size by considering the data distribution of randomly selected samples. Then, we perform kNN join by assigning the only related join data to a reducer. From performance analysis, we show that our similarity join query processing algorithm and our k-NN join algorithm outperform existing algorithms by up to 10 times, in terms of query processing time.

With the advances in wireless Internet and mobile positioning technology, location-based services (LBSs) have become popular. In LBSs, users must send their exact locations in order to use the services, but they may be subject to several privacy threats. To solve this problem, query processing algorithms based on a cloaking method have been proposed. The algorithms use spatial cloaking methods to blur the user's exact location in a region satisfying the required privacy threshold (k). With the cloaked region, an LBS server can execute a spatial query processing algorithm preserving their privacy. However, the existing algorithms cannot provide good query processing performance. To resolve this problem, we, in this paper, propose a k-NN query processing algorithm based on network Voronoi diagram for spatial networks. Therefore, our algorithm can reduce network expansion overhead and share the information of the expanded road network. In order to demonstrate the efficiency of our algorithms, we have conducted extensive performance evaluations. The results show that our algorithm achieves better performance on retrieval time than the existing algorithms, such as PSNN and kRNN. This is because our k-NN query processing algorithm can greatly reduce a network expansion cost for retrieving k POIs.