Abstract:
Planning user trips in an e ective and e cient manner has become an important topic in recent
years. In this thesis, we introduce Group Trip Scheduling (GTS) queries, a novel query type in spatial
databases. Family members normally have many outdoor tasks to perform within a short time for
the proper management of home. For example, the members of a family may need to go to a bank
to withdraw or deposit money, a pharmacy to buy medicine, or a supermarket to buy groceries.
Similarly, organizers of an event may need to visit di erent types of points of interests (POIs) such as
restaurants and shopping centers to perform many tasks. A GTS query distributes the tasks among
group members in an optimized manner. Given source and destination locations of n group members,
a GTS query schedules n individual trips such that each POI type is included in a scheduled trip
and the aggregate trip overhead distance for visiting required POI types is minimized. The aggregate
trip overhead distance can be either the summation or the maximum of the trip overhead distances
of group members. Each trip starts at a member's source location, goes through any number of POI
types, and ends at the member's destination location. The trip distance of a group member is measured
as the distance between her source to destination via the POIs that the group member visits. The
trip overhead distance of a group member is measured by deducting the distance between the source
and destination locations of a group member from the trip distance. We develop an e cient approach
to process GTS queries and variants for both Euclidean space and road networks. The number of
possible combinations of trips among group members increases with the increase of the number of
POIs that in turn increases the query processing overhead. We exploit geometric properties to re ne
the POI search space and prune POIs to reduce the number of possible combinations of trips among
group members. We propose a dynamic programming technique to eliminate the trip combinations
that cannot be part of the query answer. We perform experiments using real and synthetic datasets
and show that our approach outperforms a straightforward approach with a large margin.
