Group Processing of Multiple k-Farthest Neighbor Queries in Road Networks

Advances in mobile technologies and map-based applications enables users to utilize sophisticated spatial queries, including {k} -nearest neighbor and shortest path queries. Often, location-based servers are used to handle multiple simultaneous queries because of the popularity of map-based applications. This study focuses on the efficient processing of multiple concurrent {k} -farthest neighbor ( {k} FN) queries in road networks. For a positive integer k , query point q , and set of data points P , a {k} FN query returns k data points farthest from the query point q. For addressing multiple concurrent spatial queries, traditional location-based servers based on one-query-at-a-time processing are unsuitable owing to high redundant computation costs. Therefore, we propose a group processing of multiple {k} FN (GMP) algorithm to process multiple {k} FN queries in road networks. The proposed GMP algorithm uses group computation to avoid the redundant computation of network distances between the query and data points. The experiments using real-world roadmaps demonstrate the proposed solution's effectiveness and efficiency.