Group meetup in the presence of obstacles

摘要

In this paper, we introduce an obstructed group nearest neighbor (OGNN) query that enables a group of pedestrians to meet at a common point of interest (e.g., a restaurant) with the minimum aggregate travel distance in the presence of obstacles such as buildings and lakes. The aggregate travel distance can be measured in terms of the total, the maximum or,the minimum travel distance of. all group members: In recent years, researchers have focused on. developing efficient algorithms for processing group nearest neighbor (GNN) queries in the Euclidean space and road networks, which ignores the impact of obstacles in computing travel distances. We propose the first comprehensive approach to process an OGNN query. We present efficient algorithms to compute aggregate obstructed distances, which is an essential component of Processing OGNN queries. We. exploit geometric properties to develop pruning techniques that reduce the search space and incur less processing overhead. Based on various search space refinement techniques, we propose two algorithms: a Group Based Query Method (GBQM) and a Centroid Based Query Method (CBQM) to evaluate OGNN queries. We validate the efficacy and effciency of our solution through extensive experiments using both real and synthetic datasets and present a comparative analysis among our proposed algorithms in terms of query processing overhead. (C) 2016 Elsevier Ltd. All rights reserved.