Group Trip Planning Queries in Spatial Databases

  • Author / Creator
    Ahmadi, Elham
  • Trip planning queries are considered an important part of Location Based Services. As the first part of our research, we investigated Sequenced Group Trip PLanning Queries (SGTP) queries. Given a set of source locations and destinations for a group of n users, and a sequence of Categories of Interests (COIs) that the group is interested to visit altogether, a SGTP query returns for each user, the route from his/her source location to his/her destination such that all users go through the same Points of Interests (POIs), while minimizing the group total travel distance. As the second phase of our research, we assumed that users are interested to visit a POI belonging to the predefined COI altogether with the goal of minimizing the total detour distance towards group’s preferred paths. In the third phase of this research, we investigated a combination of trip planning and path nearest neighbor queries, which we refere to as “Best-Compromise In-Route Nearest Neighbor”. We investigated the problem where a user, traveling on his/her preferred path, needs to visit one (of many) POI while minimizing his/her total travel distance and also minimizing the detour distance incurred to reach the chosen POI. Finally, we studied the k-CPQs in road networks. Given two sets of nodes P and Q on a road network, a k-Closest Pairs Query (k-CPQ) finds the pairs from P × Q which have the k smallest network distances. Although this problem has been well studied in the Euclidean and metric spaces, this is the first time it is being investigated in the more realistic case of road networks.

  • Subjects / Keywords
  • Graduation date
    2017-11:Fall 2017
  • Type of Item
  • Degree
    Doctor of Philosophy
  • DOI
  • License
    This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
  • Language
  • Institution
    University of Alberta
  • Degree level
  • Department
    • Department of Computing Science
  • Supervisor / co-supervisor and their department(s)
    • Mario A. Nascimento (Computing Science)
  • Examining committee members and their departments
    • Mario A. Nascimento(Computing Science)
    • Joerg Sander (Computing Science)
    • Zhi-Jun (Tony) Qiu (civil and environmental engineering)
    • Wendy Osborn (Department of Mathematics and Computer Science U of Lethbridge)
    • Zachary Friggstad(Computing Science)