Plane-sweep algorithms for the K Group Nearest-Neighbor Query
Fecha
2015Materia
Resumen
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.
Colecciones
Ítems relacionados
Mostrando ítems relacionados por Título, autor o materia.
-
The K group nearest-neighbor query on non-indexed RAM-resident data
Roumelis G., Vassilakopoulos M., Corral A., Manolopoulos Y. (2016)Data sets that are used for answering a single query only once (or just a few times) before they are replaced by new data sets appear frequently in practical applications. The cost of buiding indexes to accelerate query ... -
Nearest Neighbor Algorithms using xBR-Trees
Roumelis, G.; Vassilakopoulos, M.; Corral, A. (2011)One of the common queries in spatial databases is the (K) Nearest Neighbor Query that discovers the (K) closest objects to a query object. Processing of spatial queries, in most cases, is accomplished by indexing spatial ... -
Prepartitioning in MapReduce Processing of Group Nearest-Neighbor Query
Moutafis P., Mavrommatis G., Velentzas P. (2020)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 ...