Plane-Sweep Algorithms for the K Group Nearest-Neighbor Query

George Roumelis, Michael Vassilakopoulos, Antonio Corral, Yannis Manolopoulos

2015

Abstract

One of the most representative and studied queries in Spatial Databases is the (K) Nearest-Neighbor (NNQ), that discovers the (K) nearest neighbor(s) to a query point. An extension that is important for practical applications is the (K) Group Nearest Neighbor Query (GNNQ), that discovers the (K) nearest neighbor(s) to a group of query points (considering the sum of distances to all the members of the query group). This query has been studied during the recent years, considering data sets indexed by efficient spatial data structures. We study (K) GNNQs, considering non-indexed data sets, since this case is frequent in practical applications. And we present two (RAM-based) Plane-Sweep algorithms, that apply optimizations emerging from the geometric properties of the problem. By extensive experimentation, using real and synthetic data sets, we highlight the most efficient algorithm.

Paper Citation

in Harvard Style

Roumelis G., Vassilakopoulos M., Corral A. and Manolopoulos Y. (2015). Plane-Sweep Algorithms for the K Group Nearest-Neighbor Query . In Proceedings of the 1st International Conference on Geographical Information Systems Theory, Applications and Management - Volume 1: GISTAM, ISBN 978-989-758-099-4, pages 83-93. DOI: 10.5220/0005375300830093

in Bibtex Style

@conference{gistam15,
author={George Roumelis and Michael Vassilakopoulos and Antonio Corral and Yannis Manolopoulos},
title={Plane-Sweep Algorithms for the K Group Nearest-Neighbor Query},
booktitle={Proceedings of the 1st International Conference on Geographical Information Systems Theory, Applications and Management - Volume 1: GISTAM,},
year={2015},
pages={83-93},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005375300830093},
isbn={978-989-758-099-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 1st International Conference on Geographical Information Systems Theory, Applications and Management - Volume 1: GISTAM,
TI - Plane-Sweep Algorithms for the K Group Nearest-Neighbor Query
SN - 978-989-758-099-4
AU - Roumelis G.
AU - Vassilakopoulos M.
AU - Corral A.
AU - Manolopoulos Y.
PY - 2015
SP - 83
EP - 93
DO - 10.5220/0005375300830093