Trade-off Aware Queries in Road Networks

• Author / Creator

  Ferreira Costa, Camila

• This thesis discusses bi-criteria optimization queries in road networks, in particular queries that allow users to consider trade-offs between alternative solutions. In order to measure the proximity of two nodes in a road network, a cost optimal path between them is typically computed, for instance, the fastest path. However, optimal paths can depend on more than one cost criterion. For example, when planning a bicycle route, minimizing only the distance is usually not sufficient. The user may also be interested in taking into consideration the incline of the path. Since different criteria might conflict with each other, typically there is not a single solution (a path in the example given above) that optimizes all criteria at the same time. Therefore, in this thesis we rely on the notion of skyline queries to generate a set of interesting solutions such that the user can select the preferred criteria trade-off out of the returned options. Skyline queries find a set of non-dominated solutions that are optimal for any arbitrary combination of the considered criteria. An element dominates another if it is as good or better in all dimensions and better in at least one dimension. Within this context, we first consider k-Diverse Nearest Neighbors Queries. In the original definition of k-nearest neighbor (k-NN) queries there is no concern regarding diversity of the answer set, even though in some scenarios it may be interesting. For instance, if one is looking for restaurants close by, it may be more interesting to return restaurants of different categories or ethnicities which are nonetheless relatively close. Thus, differently from a traditional k-NN query, there are two competing criteria to be optimized: closeness and diversity. Using skyline queries we can find diverse k-NNs close to a given query point and that are optimal solutions for any combination of the weights a user could give to the two competing criteria. Next, we explore trade-off aware queries in the context of spatial crowdsourcing. Spatial crowdsourcing is a relatively new platform where requesters submit location-specific tasks to be performed by workers that needto travel to those locations. Examples of these tasks include taking pictures or performing small repairs. Tasks are assigned to proper workers based on a particular objective, such as maximizing the number of assigned tasks. Previous works focus on optimizing a single criterion. We, on the other hand, consider the scenario where a worker is traveling along a given path, for instance from work to home, and is willing to perform tasks, that are not far away from the original path, in exchange for a reward. We assume that the worker wants to minimize the detour from his/her original path while maximizing the reward received for performing tasks. We investigate two variants of this problem. The first one considers an offline setting where all tasks are known beforehand, whereas in the second variant tasks appear dynamically. We show that all proposed problems are NP-Hard and present exact (whenever applicable) and heuristic approaches to solve them. Moreover, within the context of each problem, we present an experimental evaluation using real datasets and varying several parameters, and discuss the results obtained. Finally, we conclude this thesis by presenting a summary of our findings for each proposed problem and suggestions for future work.

• Subjects / Keywords

  • Spatial Crowdsourcing
  • In-Route Task Selection
  • Diverse Nearest Neighbors Queries

• Graduation date

  Fall 2020

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/r3-t0q5-tj76

• License

  Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.