III: Small: 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. This project addresses the emerging challenges posed by such datasets, which sometimes are also referred to as Spatial Big Data (SBD). SBD examples include trajectories of cell-phones and GPS devices, temporally detailed (TD) road maps, vehicle engine measurements, etc. SBD has the potential to transform society. 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. Eco-routing may leverage various forms of SBD to compare routes by fuel consumption or greenhouse gas (GHG) emissions rather than total distance or travel-time.

To develop next-generation eco-routing services, this project innovates in three areas. Frist, Lagrangian Xgraphs, a novel concept in computer science, is explored at conceptual, logical and physical database levels to model traveler's frame of reference, a major departure from traditional binary relationship (e.g., adjacency) graphs. Second, it probes the concept of route-collections, and scalable algorithms for finding route-collections. For example, to identify a route-collection over all possible start-times of a given time-interval, the project explores a critical time point approach which divides a given time-interval into a set of disjoint sub-intervals of stationary-rankings among alternative routes. The approach is not only novel but also very important for the field. Critical time points may become a vital component of dynamic programming (DP) solutions, which would need reconsideration in the face of emerging temporally detailed SBD that violate DP assumptions about stationary ranking of alternate solutions. Third, to address the increasing diversity of SBD methods, algorithm-ensembles and flexible architectures that allow rapid integration of new data sources and routing algorithms are developed.

The proposed work serves national goals for energy independence and sustainability by laying the ground work for eco-routing and other travel-related services that reduce fuel consumption and greenhouse gas emissions. By increasing the availability of SBD, the project also enhances the research infrastructure for other researchers. Educational activities include curriculum development and training of students in the emerging area of SBD and Eco-routing. Result dissemination is planned via publication in relevant peer-reviewed conferences and journals. More details are available on the project website (www.spatial.cs.umn.edu/eco-routing/).