Isochrone Queries for SQL

An isochrone in a spatial network is a possibly disconnected subgraph that covers all space points from which a specific point of interest is reachable within a given time period at a specific point in time. Isochrones have interesting applications, for example, geomarketing (e.g., positioning of franchise stores) or urban planing (e.g., finding spots in the city that are hard to reach by public transportation).

Isochrones are particularly interesting as part of a larger query that combines spatial and non-spatial aspects. Answering such queries is challenging, in particular when multimodal networks are involved. Multimodal networks, in addition to pedestrian networks, also include components like public transportation and road networks with live traffic data and better model human behavior related to movement. For such networks, the isochrones vary over time and cannot easily be precomputed. State-of-the-art techniques for isochrones are too slow for complex, interactive, and incremental queries, for example, a graphical user interface that allows users to vary arrival time and time period of the isochrones with an interactive slider.

The goal of this PhD project is to extend SQL with the notion of isochrones and develop efficient evaluation strategies for SQL with isochrones. In particular, interactive responsive time for complex query patterns and multi-modal networks should be achieved. The focus will be on new index structures for isochrones and cost-based query optimization in the context of complex queries. The outcome of the PhD project are new algorithms and indexing techniques that are implemented – possibly as part of a GIS-enabled relational database system like PostgreSQL – and are empirically evaluated on real world datasets or synthetic benchmarks.