Obstructed Group Trip Planning Queries in Spatial Databases

Group trip planning (GTP) queries facilitate a group of individuals to visit together a series of points of interest (POIs) of various categories (e.g., a restaurant followed by a shopping mall) while minimizing the aggregate travel distance for the group. Researchers have developed a number of efficient algorithms for processing GTP queries in the Euclidean space and road networks. However, none of them consider the presence of obstacles (e.g., trees, buildings or lakes) in their research problem. This research work proposes an obstructed group trip planning (OGTP) query, enabling a group of pedestrians to organize a trip within an environment containing obstacles. For a given pair of source-destination locations of the group members, a sequence of required categories of POIs, an OGTP query identifies a set of POI locations, one from each required category, that together minimize the total or maximum obstructed travel distance for group members as they move from their starting points to their final destinations through the selected POIs. We develop the first solution for processing OGTP queries. We apply the Euclidean lower bound and elliptical properties to filter out POIs that cannot optimize the group trip distance. The efficiency of OGTP query processing algorithm depends on the cost of obstructed group trip distance computations. Thus, we also propose an obstructed group trip distance (OGTD) computation technique that utilizes elliptical properties to optimize performance. This approach reduces the number of obstacles retrieved from the database, prevents redundant retrieval of the same obstacles, and efficiently reuses previously computed obstructed distances. In order to verify the efficiency and effectiveness of our proposed algorithm, we perform experiments using a real dataset which runs successfully.