Obstructed group nearest neighbor queries in spatial databases

Abstract

A group nearest neighbor (GNN) query is an important class of information and enquiry services. Researchers have focused on developing e cient algorithms to evaluate variant of GNN queries in recent years. In this thesis, we introduce obstructed group nearest neighbor (OGNN) queries that enable a group of pedestrians located at di erent places to meet at a data point such as a restaurant that minimizes their aggregate travel distance in presence of obstacles such as buildings and lakes. We propose the rst comprehensive approach to process an OGNN query. The obstructed distance between two point locations is de ned as the length of the shortest path that connects them without crossing any obstacles. The aggregate obstructed distance is measured in terms of the total or the maximum travel distance of the group members in an obstructed space. We develop two techniques, Single Point Aggregate Obstructed Distance (SPAOD) computation and Multi Point Aggregate Ob- structed Distance (MPAOD), for computing aggregate obstructed distance between a data point and a set of query points, which is an essential part in evaluating GNNs in an obstructed space. SPAOD computation does not retrieve an obstacle multiple times but may retrieve additional obstacles, which are not required for computing the aggregate obstructed distance. On the other hand, MPAOD may retrieve the same obstacle multiple times but does not retrieve any obstacle, which is not required for computing the aggregate obstructed distance. We propose two methods: Group Based Query Method(GBQM) and Centroid Based Query Method (CBQM) to evaluate OGNN queries. The key idea of GBQM and CBQM is to incrementally retrieve data points until the actual obstructed GNN has been found. GBQM retrieves the Euclidean group nearest neighbors with respect to the locations of group members, whereas CBQM retrieves the Euclidean nearest neighbors with respect to the centroid of the locations of group members. We validate the e cacy and e ciency of our solutions with an extensive experiments using both real and synthetic datasets and present a comparative analysis among our proposed algorithms in terms of query processing overhead.