Voronoi-Based Geospatial Query Processing with MapReduce

TLDR

Geospatial queries are widely used in applications such as decision support, marketing, bioinformatics, and GIS, yet most existing methods assume centralized processing, and parallel approaches are limited to systems with modest parallelism and do not exploit cloud‑scale platforms. This paper investigates parallel geospatial query processing using the MapReduce programming model. We construct a Voronoi diagram spatial index for 2D data points, enabling efficient execution of a broad set of geospatial queries within MapReduce. Our experiments demonstrate that the Voronoi‑based MapReduce approach outperforms related work as the number of nodes increases.

Abstract

Geospatial queries (GQ) have been used in a wide variety of applications such as decision support systems, profile-based marketing, bioinformatics and GIS. Most of the existing query-answering approaches assume centralized processing on a single machine although GQs are intrinsically parallelizable. There are some approaches that have been designed for parallel databases and cluster systems, however, these only apply to the systems with limited parallel processing capability, far from that of the cloud-based platforms. In this paper, we study the problem of parallel geospatial query processing with the MapReduce programming model. Our proposed approach creates a spatial index, Voronoi diagram, for given data points in 2D space and enables efficient processing of a wide range of GQs. We evaluated the performance of our proposed techniques and correspondingly compared them with their closest related work while varying the number of employed nodes.