Búsqueda avanzada

Efficient Large-scale Distance-Based Join Queries in SpatialHadoop


Efficient processing of Distance-Based Join Queries (DBJQs) in spatial databases is of paramount importance in many application domains (e.g. image processing, location-based systems, geographical information systems (GIS), continuous monitoring in streaming data settings, road network systems, etc.). The most representative and known DBJQs are the K Closest Pairs Query (KCPQ) and the e Distance Join Query (eDJQ). These types of join queries are characterized by a number of desired pairs (K) or a distance threshold (e) between the components of the pairs in the nal result, over two spatial datasets. Both are expensive operations, since two spatial datasets are combined with additional constraints, and they become even more costly operations for large-scale data. Given the increasing volume of spatial data originating from multiple sources and stored in distributed servers, it is not always efficient to perform DBJQs on a centralized server. For this reason, this paper addresses the problem of computing DBJQs on big spatial datasets in SpatialHadoop, an extension of Hadoop-MapReduce that supports efficient processing of spatial queries in a cloud-based setting. SpatialHadoop injects spatial data awareness in each Hadoop layer, i.e. language, storage, MapReduce and operations layers.We propose novel algorithms, based on plane-sweep, to perform efficient parallel DBJQs on large-scale spatial datasets in SpatialHadoop. In addition to the plane-sweep base technique, we present a methodology for improving the performance of the KCPQ algorithms by the computation of an upper bound of the distance of the K-th closest pair. To demonstrate the benets of our proposed methodologies, we present the results of the execution of an extensive set of experiments that demonstrate the efficiency and scalability of our proposals using big synthetic and real-world points datasets.

Palabras Clave:

eDJQ - KCPQ - MapReduce - Spatial Data Processing - Spatial Query Evaluation - SpatialHadoop





Este artículo tiene una licencia de uso CreativeCommons - Reconocimiento (by)

Descarga el artículo haciendo click aquí.