Technical Report PHD-2013-09

Title: Geospatial Route Search
Authors: Roy Levin
Supervisors: Yaron Kanza
Abstract: Recently, there has been a rapid growth in the popularity of smartphones and other GPS-enabled devices as basic navigation tools, especially for urban areas. However, most of the navigation software, nowadays, merely find a point-to-point route and cannot handle intricate search scenarios. This thesis introduces a more elaborate type of navigation, namely route search, that can plan effective routes for complex queries in heterogeneous environments, while dealing with uncertainties regarding geographic entities and traffic conditions. In a route-search, a user specifies her requirements in the form of a query, and the main task is to find a route that goes via geographical objects while satisfying the search specifications. For instance, a tourist in a foreign city, say San Francisco, wants to plan a route from her current location to some destination, via four types of entities: (1) a coffee shop, (2) an ATM, (3) a shoe store, and (4) a vegetarian restaurant. She may perform four separate local searches using some geographical search engine — a different search for each type of entity. Each local search will result in a ranked list of entities, with their locations depicted on four separate maps. Yet, joining the results of the four different searches, and constructing an effective route via relevant entities, is a complex task. On the one hand, going via the entities with the highest rank is more likely to satisfy the search requirements; however, such route may be ineffective and may travel back and forth in the city. On the other hand, choosing entities with low relevance for the purpose of creating a short route, may reduce the chances of satisfying the user, e.g., the route will go via a restaurant that is not really vegetarian. In realistic scenarios, planning should take into account additional complicating factors such as the opening hours of the entities to be visited and possible restrictions on the order by which the entities may be visited. We refer to such factors as temporal constraints. The exponential number of possible routes, magnified by the large number of objects for some types along with the various constraints that must be taken into account, make the problem of constructing an effective route computationally difficult. We present two approaches for dealing with the problem of route-search. The first is a pre-planned approach in which a full route, along with its departure time is calculated in advance. We present a pre-planned framework that finds the fastest route which answers a query, taking into account (1) uncertainties with respect to entities satisfying the user, (2) varying traffic conditions and (3) temporal constraints. We present three heuristic algorithms and evaluate them using real data. Our experiments show that the pre-planned approach is feasible and can effectively cope with highly complex planning scenarios. In addition, we also present a demo system which implements this framework. The second approach is a new type of search that is tailored for mobile devices such as smartphones. A smartphone user can provide feedback to the search while traveling. This allows the resulting route to be adjusted on the fly based on this feedback. Hence, the goal becomes finding the shortest route that will be traveled by the user, in practice. In addition, we extend the problem of interactive route-search to account for traffic conditions and temporal constraints. We formulate these problems, present heuristic algorithms for them and test them using real data we collected. Our experimental results show that interactive route search is suitable to be applied on smartphones. To provide further confirmation for this, we also implemented an Android based system for processing route search in an interactive fashion. Another question we study in this thesis is processing historical GPS data aggregated from multiple users. With that in mind, one related problem is called offline map-matching. It is a process of associating a sequence of inaccurate GPS location readings onto the real-world roads that were presumably traveled by the user. In our case, the algorithm must be robust in the sense that it can support different sampling rates which are unknown in advance. The main goals in map matching are (1) to provide an association which is as accurate as possible with respect to actual traveled roads, and (2) to compute the matching as efficiently as possible. We devised a map matching algorithm that is highly robust and that enables concurrent computation of the matching for a given sequence of GPS readings. The algorithm was developed as part of an international algorithmic challenge (the ACM SIGSPATIAL CUP 2012 contest), and we present the results of an experimental evaluation over the data of the contest. We show that our algorithm is efficient and robust in the sense that it maintains a high level of accuracy even when the sampling rate is low. The algorithm was among the winners of the contest. Due to the large quantities and the distributed nature of historical GPS data, we examined methods for producing representative samples of it in an efficient and scalable manner. In addition, as GPS data usually may convey sensitive private information, it should be anonymized before its publication while reducing anonymization cost. These problems led us to devise a generic distributed sampling framework. In this framework we deal with stratified sampling, in which the surveyed population is partitioned into homogeneous subgroups and the individuals are selected within the subgroups. In addition, since several surveys can be conducted in parallel, there are cases where it may be desired to share individuals to reduce costs, while in other surveys, sharing should be minimized. A multi-survey stratified sampling is the problem of choosing the individuals for several surveys, in parallel, according to the sharing constraints, without a bias. We present a scalable distributed algorithm, designed for the MapReduce framework, for answering stratified-sampling queries. An experimental evaluation illustrates the efficiency of our algorithms and their effectiveness for multi-survey stratified sampling.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2013
To the main CS technical reports page

Computer science department, Technion