Frequency Data Compression for Public Transportation Network Algorithms (Extended Abstract)
| Autor: | Hannah Bast, Sabine Storandt |
|---|---|
| Rok vydání: | 2021 |
| Zdroj: | Proceedings of the International Symposium on Combinatorial Search. 4:205-206 |
| ISSN: | 2832-9163 2832-9171 |
| DOI: | 10.1609/socs.v4i1.18302 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|