Ph.D Thesis

Ph.D StudentLevin Roy
SubjectGeospatial Route Search
DepartmentDepartment of Computer Science
Supervisor DR. Yaron Kanza
Full Thesis textFull thesis text - English Version


            In recent years, smartphones have become one of the most popular tools for local search and navigation. Yet, state-of-the-art navigation tools are still rather limited in their ability to cope with complex route-planning tasks, such as constructing an effective route from the location of the user to a target via a restaurant, a pharmacy and a coffee shop. Planning becomes even more challenging when taking into account uncertainties, such as the imprecise compliance of geographical entities with the user's requirements, opening and closing times of institutes, and the varying traffic conditions within urban areas. This thesis presents the problem of route search and shows how it can be modeled as a query over a probabilistic database. Since the problem is NP-hard, we present efficient heuristics to plan an effective route over large geospatial datasets. In addition, we also present a novel interactive search approach tailored for smartphones. The crux of this approach is that the user can provide feedback while traveling. The main challenge is to plan interactive routes that are more effective than non-interactive routes. Finally, the thesis also presents a study of techniques for processing large amounts of GPS data collected from multiple smartphone users.