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.
