Back to results

University of Thessaly (UTH)

Algorithms for processing closest-pairs and nearest-neighbors queries on big spatial data in parallel and distributed frameworks

Abstract

dc:description

Spatial Data refers to data related to the position or geolocation of objects and elements on, below or above the earth’s surface. Such data, often termed geospatial data, appear in geography related applications. Currently, numerous applications and sources are creating explosive amounts of data with spatial characteristics or with related geolocated information. Sensors, mobile apps, cars, GPS devices, unmanned aerial vehicles, ships, airplanes, telescopes, medical devices, web apps, social networking and IoT devices are examples of such applications and sources.Spatial data are harder to handle than data in traditional applications (e.g., names, numbers, dates, etc.) and have higher processing requirements. Furthermore, the big volume of spatial data in modern applications requires the use of multinode systems for their processing. Among them, shared-nothing parallel and distributed systems based on the MapReduce model and/or Resilient Distributed Datasets (RDDs) are common in research efforts.Efficient big spatial data management requires efficient processing of computationally demanding spatial query operations. The following demanding queries are applied on two datasets and combine join queries (since all possible combinations formed from these datasets are candidates for the final result) and nearest-neighbor queries (since the final result is formed according to a neighboring criterion).• The K Closest-Pairs Query (KCPQ): for each possible pair of elements from the two datasets, it discovers K pairs with the smallest distances among their elements.• The Distance Join Query (DJQ): this is a form of closest-pairs query which, for each possible pair of elements from the two datasets, returns pairs with distances smallerthan a given distance.• The All K Nearest-Neighbor Query (AKNNQ, also termed K Nearest-Neighbor Join): it discovers K nearest neighbors in the one dataset for each element of the other dataset,• The Group (K) NearestNeighbor(s) Query (GKNNQ): it returns K elements of the one dataset with the smallest sum of distances to every element of the other dataset.Although naive algorithms for the above queries are simple, they suffer from excessive computational, intermediate result storage and network communication cost and low load balancing among computing nodes, especially within a distributed environment. In this thesis, we focus on point data and employ techniques for faster and fewer computations, pruning of unnecessary computations, taking advantage of spatial locality and distribution of data, improving load balancing among computing nodes and optimizing the amount of data transferred between nodes. Based on these techniques,• we develop the first KCPQ and DJQ algorithms for Apache Spark, a popular parallel and distributed system that has attracted attention due to exploiting in-memory processing capabilities,• we develop AKNNQ algorithms for Apache Hadoop, the first widely accepted system implementing the MapReduce model,• we develop the first GKNNQ algorithms for both Apache Hadoop and SpatialHadoop, an extension specifically designed to manage big spatial datasets,• for each of the above queries, we perform extensive experimental tests to derive the best parameter settings for each algorithm and to compare the efficiency of the severalalternative algorithms we developed and ones appearing in the literature (for the cases where such algorithms already existed).

Degree

thesis:*
Grantor dc:publisher
University of Thessaly (UTH)
Year dc:date
2021

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Moutafis, Panagiotis
  • Μουτάφης, Παναγιώτης

Subjects

dc:subject × 28

Rights

dc:rights
Statement dc:rights
  • BY_4_0
Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/49345

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Moutafis, Panagiotis; Μουτάφης, Παναγιώτης. Algorithms for processing closest-pairs and nearest-neighbors queries on big spatial data in parallel and distributed frameworks. University of Thessaly (UTH), 2021. http://hdl.handle.net/10442/hedi/49345