MRSLICE: Efficient RkNN Query Processing in SpatialHadoop

Abstract

Nowadays, with the continuously increasing volume of spatial data, it is difficult to execute spatial queries efficiently in spatial data-intensive applications, because of the limited computational capability and storage resources of centralized environments. Due to that, shared-nothing spatial cloud infrastructures have received increasing attention in the last years. SpatialHadoop is a full-edged MapReduce framework with native support for spatial data. SpatialHadoop also supports spatial indexing on top of Hadoop to perform efficiently spatial queries (e.g., k-Nearest Neighbor search, spatial intersection join, etc.). The Reverse k-Nearest Neighbor (RkNN) problem, i.e., finding all objects in a dataset that have a given query point among their corresponding k-nearest neighbors, has been recently studied very thoroughly. RkNN queries are of particular interest in a wide range of applications, such as decision support systems, resource allocation, profile-based marketing, location-based services, etc. In this paper, we present the design and implementation of an RkNN query MapReduce algorithm, so-called MRSLICE, in SpatialHadoop. We have evaluated the performance of the MRSLICE algorithm on SpatialHadoop with big real-world datasets. The experiments have demonstrated the efficiency and scalability of our proposal in comparison with other RkNNQ MapReduce algorithms in SpatialHadoop. © 2019, Springer Nature Switzerland AG.