Prepartitioning in MapReduce Processing of Group Nearest-Neighbor Query
Open Access
- 20 November 2020
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 380-385
Abstract
Given two datasets of points (called Query and Training), the Group (K) Nearest-Neighbor (GKNN) query retrieves (K) points of the Training with the smallest sum of distances to every point of the Query. This spatial query has been studied during the recent years and several performance improving techniques and pruning heuristics have been proposed. In a previous work, we presented the first MapReduce algorithm, consisting of alternating local and parallel phases, which can be used to effectively process the GKNN query when the Query fits in memory, while the Training one belongs to the Big Data category. In subsequent works, we presented several improvements on the first version of the algorithm. In this paper we present yet another improvement, which consists in the prepartitioning of the Training dataset. As shown in the experimentation section, this technique significantly reduces data transfer and total running time of the algorithm. Furthermore, the prepartitioning of the Training dataset is performed only once and can be reused with multiple Query datasets, leading to faster response times.Keywords
This publication has 13 references indexed in Scilit:
- MapReduce algorithms for the K group nearest-neighbor query2019
- The K Group Nearest-Neighbor Query on Non-indexed RAM-Resident Data2016
- Plane-Sweep Algorithms for the K Group Nearest-Neighbor Query2015
- Nearest group queries2013
- Reverse Top-k Group Nearest Neighbor Search2013
- Robust Prediction and Outlier Detection for Spatial Datasets2012
- Voronoi-based aggregate nearest neighbor query processing in road networks2010
- Privacy preserving group nearest neighbor queries2010
- Aggregate nearest neighbor queries in spatial databasesACM Transactions on Database Systems, 2005
- Data clusteringACM Computing Surveys, 1999