![Chris Harrelson](https://storage.googleapis.com/gweb-research2023-media/pubtools/5.png)
Chris Harrelson
Research Areas
Authored Publications
Google Publications
Other Publications
Sort By
Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns
Hannah Bast
Erik Carlsson
Veselin Raychev
Algorithms - ESA 2010, 18th Annual European Symposium. Proceedings, Part I, Springer, pp. 290-301
Preview abstract
We show how to route on very large public transportation networks (up to half a billion arcs) with average query times of a few milliseconds. We take into account many realistic features like: traffic days, walking between stations, queries between geographic locations instead of a source and a target station, and multi-criteria cost functions. Our algorithm is based on two key observations: (1) many shortest paths share the same transfer pattern, i.e., the sequence of stations where a change of vehicle occurs; (2) direct connections without change of vehicle can be looked up quickly. We precompute the respective data; in practice, this can be done in time linear in the network size, at the expense of a small fraction of non-optimal results. We have accelerated public transportation routing on Google Maps with a system based on our ideas. We report experimental results for three data sets of various kinds and sizes.
View details
Approximate classification via earthmover metrics
Jittat Fakcharoenphol
Robert Krauthgamer
Kunal Talwar
Eva Tardos
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, SIAM, pp. 1079-1087