Logo: University of Southern California

Finding the Fastest Way from Here to There Right Now

A Viterbi team is creating TransDec, a "dynamic data warehouse" for traffic decision-making and much more
By: Eric Mankin
January 28, 2013 —

The Viterbi School of Engineering’s Cyrus Shahabi and his team are working with the METRANS Transportation Center to develop a new system for gathering and understanding traffic data. The system may soon be improving your smartphone or online map navigation.

The Transportation Decision-Making (TransDec) system developed by the Integrated Media Systems Center (IMSC) is “a data-driven framework for decision making in transportation systems,” aimed at collecting and organizing massive quantities of traffic data about conditions in Los Angeles County. TransDec fuses data from 11,200 freeway and arterial loop-detectors (with a sampling rate of one reading per sensor per minute) covering 3,420 miles, real-time location information of 2,000 transit vehicles, and approximately 800 events (e.g., accidents, road closures, emergiencies) per day.

Shahabi, a professor in the Viterbi School's Department of Computer Science and director of the Viterbi School's IMSC and his Information Laboratory (InfoLAB), is attacking the problem from two sides.

The idea: from sensors to storage to engine to users.
First is data access. For example, Google now turns traffic data into the widely used maps seen on TV news and even cell phone apps that display freeway congestion. But Shahabi’s work with the Los Angeles County Metropolitan Transportation Authority (LA Metro) and METRANS goes beyond what now exists in three ways, on three levels.

First, said Shahabi, the data used in the current displays is not retained, but simply thrown away. “We, however, store all the data for future data mining on Microsoft’s Azure cloud platform.”

Second, “we continuously query the data for computing traffic parameters over a region and over time where we can ask questions about it in real-time. It is not just displaying it. The system can answer a variety of queries on the performance of corridors and regions in real-time and compare with historical averages, and detect phenomena such as accidents in real-time." This is enabled, said Shahabi, by extending Microsoft’s StreamInsight technology.

This kind of on-the-fly processing, he adds, can’t be done in current systems, “because the data doesn’t go through any processing. It’s just displayed and thrown out."

The third level is detailed analysis of the stored data to answer complex questions. At a METRANS presentation about the system, presided over by METRANS Director Genevieve Giuliano, Shahabi discussed the database ramifications of what seems like a simple question: how far apart in time are two points on the map?

Determining the direct, as-the-crow-flies aerial distance is a query that can be answered by a simple application of solid geometry. But people travel on roads between points, not in straight Euclidian lines, said Shahabi. A computer program that can bring a whole set of local roads and traffic conditions into the picture and pick the fastest route is not a trivial question, but one the new system can solve using an algorithm devised by Dr. Ugur Demiryurek, Associate Director of IMSC.

The shortest road distance doesn’t always mean the fastest, and the departure time from the source is often a critical factor. The new system exploits the BIG historical data to predict how traffic will change during the course of a commute on road networks.  The system then "computes the best path given the prediction of traffic in front of the drivers, ensuring a driver had picked the best route from the start," Demiryurek said.

Cyrusguilano 2
Cyrus Shahabi and METRANS director Genevieve Giuliano.
A second element is a new, faster and cheaper way of gathering traffic data. Traditionally, such data is collected by sensors known as loop detectors which are embedded in the highway. An alternative is emerging. Visual sensors wired to video processing hardware and software that can interpret images to distinguish vehicles can perform the same function at least as well, but at a much lower cost, both per unit and per installation.

"Replacing loop detectors requires interrupting traffic, while replacing the camera presents no such requirement,” said IMSC Associate Director Seon Ho Kim, whose algorithm for traffic inference from video data is being used in the project.

Shahabi’s vision: “These real-time sense-analyze-store building blocks are so generic that they can be utilized in so many applications, that essentially we are laying the foundations for a dynamic data warehouse, i.e. Google for dynamic data.”

Shahabi is working with USC Stevens Center for Innovation on the possibilities for a new startup - a next generation navigation application called ClearPath, which considers current and predictive traffic information on road networks. Shahabi has been a principal in one startup, as founder and chief technology officer of Geosemble Technologies, a company that specializes in automatically integrating web information into satellite and aerial imagery and maps.  Geosemble Technologies was acquired by Terrago Technologies in July 2012.