Project abstract for group shekhars

Investigating Spatial Big Data for Next Generation Routing Services

Increasingly, location-aware datasets are of a size, variety, and update rate that exceed the capability of spatial computing technologies. Examples of such datasets, which are called Spatial Big Data (SBD), include temporally detailed (TD) road maps and vehicle engine measurements. SBD has the potential to transform society. For instance, a recent McKinsey Global Institute report estimates that personal location data could save consumers hundreds of billions of dollars annually by 2020 by helping vehicles avoid congestion via next-generation-routing services such as eco-routing.

This project aims to develop computational techniques instrumental for creating the envisaged SBD based next-generation-routing services. Specifically, these researchers plan to revisit the ambiguous and partial-nature of a traditional routing query in the light of SBD. A traditional routing query, usually specified by a start and an end location, identifies a unique (or a small set of) route(s), given historical and current travel-times. In contrast, SBD has the potential to identify a much larger set of solutions, e.g., one route each for thousands of possible start-times in a week, significantly increasing computational costs. This group formalizes the ambiguous and partial-nature of the traditional query in the form of all-start-time Lagrangian shortest paths (ALSP) problem on TD roadmaps. Given a TD roadmap, a source, a destination, and a start-time interval, an ALSP problem determines a collection of routes which includes the shortest path for every start time in the interval. The ALSP output includes both the shortest paths and the corresponding set of time instants when the paths are optimal. These researchers are exploring the computational structure of the ALSP problem to exploit the inherent parallelism to maximum possible extent. Some candidate strategies include concurrency across consecutive start-times and concurrency across disjoint sub-intervals of start-times. 

A bibliography of this group’s publications acknowledging MSI is attached.