Frequency Data Compression for Public Transportation Network Algorithms (Extended Abstract)

Timetable information in public transportation networks exhibit a large degree of redundancy; e. g. consider a bus going from station A to station B at 6: 00, 6: 15, 6: 30, 6: 45, 7: 00, 7: 15, 7: 30, .. ., 20: 00, the very same data can be provided by a frequency-based representation as ’6: 00-20: 00, every 15 minutes’ in considerably less space. Nevertheless a common graph model for routing in public transportation networks is the time-expanded representation where for each arrival/departure event a single node is created. We will introduce a frequency-based graph model which allows for a significantly more compact representation of the network, resulting also in a speed-up for station-to-station queries. Moreover we will describe a new variant of Dijkstra’s algorithm, where also the labels are frequency-based. This approach allows for accelerating profile queries in public transportation networks.

Authors

• Hannah Bast
• Sabine Storandt

Keywords

• public transport
• profile queries
• compression