Group meetup in the presence of obstacles. (October 2016)

• Record Type: Journal Article
• Authors: Sultana, Nusrat; Hashem, Tanzima; Kulik, Lars
• Is Part Of: Information systems. Volume 61(2016)
• Page Start: 24
• Page End: 39
• Publication Date: 2016-10
• Subjects: Obstacles -- Obstructed distance -- Group nearest neighbor queries; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2016.04.003
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: 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 efficiency 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. Abstract : Highlights: We introduce GNN queries in the obstructed space. We develop pruning techniques to efficiently evaluate obstructed GNN queries. We propose two efficient techniques to compute aggregate obstructed distances. We conduct an extensive experimental analysis to compare our algorithms.