Download the full-sized PDF of Group Trip Planning Queries in Spatial DatabasesDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Graduate Studies and Research, Faculty of


This file is in the following collections:

Theses and Dissertations

Group Trip Planning Queries in Spatial Databases Open Access


Other title
Group Trip Planning
Spatial Databases
Type of item
Degree grantor
University of Alberta
Author or creator
Ahmadi, Elham
Supervisor and department
Mario A. Nascimento (Computing Science)
Examining committee member and department
Joerg Sander (Computing Science)
Zachary Friggstad(Computing Science)
Zhi-Jun (Tony) Qiu (civil and environmental engineering)
Wendy Osborn (Department of Mathematics and Computer Science U of Lethbridge)
Mario A. Nascimento(Computing Science)
Department of Computing Science

Date accepted
Graduation date
2017-11:Fall 2017
Doctor of Philosophy
Degree level
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.
This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for the purpose of private, scholarly or scientific research. 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.
Citation for previous publication
Elham Ahmadi and Mario A. Nascimento. IBS: An efficient stateful algo- rithm for optimal sequenced group trip planning queries in road networks. In Proc. of the 18th Intl. Conf. on Mobile Data Mangement (MDM), pages 24–33, 2017.Elham Ahmadi, Camila F. Costa, and Mario A. Nascimento. Best-compromise in-route nearest neighbor queries. In Proc. of the 25th Intl. Conf. on Ad- vances in Geographic Information Systems (ACM SIGSPATIAL)-Submitted. ACM, 2017.Elham Ahmadi and Mario A. Nascimento. A mixed breadth-depth first search strategy for sequenced group trip planning queries. In Proc. of the 16th Intl. Conf. on Mobile Data Management (MDM), 2015.Elham Ahmadi and Mario A. Nascimento. k-closest pairs queries in road networks. In Proc. of the 17th Intl. Conf. on Mobile Data Mangement (MDM), pages 232–241, 2016.Elham Ahmadi and Mario A. Nascimento. k-optimal meeting points based on preferred paths. In Proc. of the 24th Intl. Conf. on Advances in Geographic Information Systems (ACM SIGSPATIAL), pages 47:1–47:4, 2016.

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 1714996
Last modified: 2017:11:08 18:13:02-07:00
Filename: Ahmadi_Elham_201709_PhD.pdf
Original checksum: b29128fd7b59f1f0d31770ebc0ab7864
Well formed: false
Valid: false
Status message: Invalid page tree node offset=812804
Status message: Unexpected error in findFonts java.lang.ClassCastException: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject cannot be cast to edu.harvard.hul.ois.jhove.module.pdf.PdfDictionary offset=5729
Status message: Invalid name tree offset=1689640
Status message: Invalid name tree offset=1689640
Status message: Invalid name tree offset=1684513
File title: Introduction
Activity of users you follow
User Activity Date