Please activate JavaScript!
Please install Adobe Flash Player, click here for download

uni'wissen 01-2014_ENG

“We log in. The route planner recognizes us and knows exactly how we like to travel.” “Let’s say you want to travel from Freiburg to Munich. Then enter this here.” Prof. Dr. Hannah Best types FREIBURG, then MUNICH. A map of Southern Germany appears on her computer screen, which is projected onto the wall of her office by a video projector. A blue line runs over autobahn A5 to Karlsruhe and then A8 toward Bavaria. A good four hours for 412 kilometers: Google Maps shows the classical route. “But maybe you don’t want to take that route but rather pass by Lake Constance, maybe even making a stop in Villingen-Schwennigen,” says Bast as she clicks on the line and drags it slowly southward. The route planner reacts immediately, recommending a new route for every millimeter the line moves. The number of kilometers and the probable duration of each new trip appear in parentheses almost instantly. The fact that Google Maps needs only a fraction of a second to calculate routes is in part due to the research of Hannah Bast. She holds the chair in algorithms and data structures at the Depart- ment of Computer Science of the University of Freiburg. Two years ago she received a Google Focused Research Award for her work. The award is worth nearly a million US dollars. According to Google, its purpose is to support areas of research that are interesting for the company itself and for the international computer science scene. A route planner that needs but the blink of an eye to calculate journeys doubtlessly fulfills these criteria. But lightning-fast computers are not the only reason why Google users see immediately how much time their chosen route will take as they drag the blue line across the screen. “The computer is of course capable of trying out a million possi- bilities relatively quickly and then suggesting the most sensible and fastest one,” says Bast, “but this would take a minute even for the best comput- ers.” So instead Bast and her colleagues did a little cheating. Instead of making the computer 21