Scalable Transfer Patterns
| dc.contributor.author | Bast, Hannah | |
| dc.contributor.author | Hertel, Matthias | |
| dc.contributor.author | Storandt, Sabine | |
| dc.date.accessioned | 2018-11-09T10:44:20Z | |
| dc.date.available | 2018-11-09T10:44:20Z | |
| dc.date.issued | 2016 | eng |
| dc.description.abstract | We consider the problem of Pareto-optimal route planning in public-transit networks of a whole country, a whole continent, or even the whole world. On such large networks, existing approaches suffer from either a very large space consumption, a very long preprocessing time or slow query processing. Transfer Patterns, a state-of-the-art technique for route planning in transit networks, achieves excellent query times, but the space consumption is large and the preprocessing time is huge. In this paper, we introduce a new scheme for the Transfer Pattern precomputation and query graph construction that reduces both the necessary preprocessing time and space consumption by an order of magnitude and more. Average query times are below 1 ms for local queries, independent of the size of the network, around 30 ms for non-local queries on the complete transit network of Germany, and an estimated 200 ms for a fictitious transit network covering the currently available data of the whole world. | eng |
| dc.description.version | published | eng |
| dc.identifier.doi | 10.1137/1.9781611974317.2 | eng |
| dc.identifier.uri | https://kops.uni-konstanz.de/handle/123456789/43756 | |
| dc.language.iso | eng | eng |
| dc.subject.ddc | 004 | eng |
| dc.title | Scalable Transfer Patterns | eng |
| dc.type | INPROCEEDINGS | eng |
| dspace.entity.type | Publication | |
| kops.citation.bibtex | @inproceedings{Bast2016Scala-43756,
year={2016},
doi={10.1137/1.9781611974317.2},
title={Scalable Transfer Patterns},
isbn={978-1-61197-431-7},
publisher={Siam},
address={Philadelphia},
booktitle={Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2016, Arlington, Virginia, USA, January 10, 2016},
pages={15--29},
editor={Goodrich, Michael and Mitzenmacher, Michael},
author={Bast, Hannah and Hertel, Matthias and Storandt, Sabine}
} | |
| kops.citation.iso690 | BAST, Hannah, Matthias HERTEL, Sabine STORANDT, 2016. Scalable Transfer Patterns. ALENEX 2016. Arlington, Virginia, USA, 10. Jan. 2016 - 10. Jan. 2016. In: GOODRICH, Michael, ed., Michael MITZENMACHER, ed.. Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2016, Arlington, Virginia, USA, January 10, 2016. Philadelphia: Siam, 2016, pp. 15-29. ISBN 978-1-61197-431-7. Available under: doi: 10.1137/1.9781611974317.2 | deu |
| kops.citation.iso690 | BAST, Hannah, Matthias HERTEL, Sabine STORANDT, 2016. Scalable Transfer Patterns. ALENEX 2016. Arlington, Virginia, USA, Jan 10, 2016 - Jan 10, 2016. In: GOODRICH, Michael, ed., Michael MITZENMACHER, ed.. Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2016, Arlington, Virginia, USA, January 10, 2016. Philadelphia: Siam, 2016, pp. 15-29. ISBN 978-1-61197-431-7. Available under: doi: 10.1137/1.9781611974317.2 | eng |
| kops.citation.rdf | <rdf:RDF
xmlns:dcterms="http://purl.org/dc/terms/"
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:bibo="http://purl.org/ontology/bibo/"
xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
xmlns:foaf="http://xmlns.com/foaf/0.1/"
xmlns:void="http://rdfs.org/ns/void#"
xmlns:xsd="http://www.w3.org/2001/XMLSchema#" >
<rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/43756">
<dc:language>eng</dc:language>
<bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/43756"/>
<dcterms:issued>2016</dcterms:issued>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-11-09T10:44:20Z</dcterms:available>
<dc:creator>Bast, Hannah</dc:creator>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:contributor>Hertel, Matthias</dc:contributor>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dcterms:abstract xml:lang="eng">We consider the problem of Pareto-optimal route planning in public-transit networks of a whole country, a whole continent, or even the whole world. On such large networks, existing approaches suffer from either a very large space consumption, a very long preprocessing time or slow query processing. Transfer Patterns, a state-of-the-art technique for route planning in transit networks, achieves excellent query times, but the space consumption is large and the preprocessing time is huge. In this paper, we introduce a new scheme for the Transfer Pattern precomputation and query graph construction that reduces both the necessary preprocessing time and space consumption by an order of magnitude and more. Average query times are below 1 ms for local queries, independent of the size of the network, around 30 ms for non-local queries on the complete transit network of Germany, and an estimated 200 ms for a fictitious transit network covering the currently available data of the whole world.</dcterms:abstract>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-11-09T10:44:20Z</dc:date>
<dc:creator>Storandt, Sabine</dc:creator>
<dcterms:title>Scalable Transfer Patterns</dcterms:title>
<dc:contributor>Bast, Hannah</dc:contributor>
<dc:contributor>Storandt, Sabine</dc:contributor>
<dc:creator>Hertel, Matthias</dc:creator>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
</rdf:Description>
</rdf:RDF> | |
| kops.conferencefield | ALENEX 2016, 10. Jan. 2016 - 10. Jan. 2016, Arlington, Virginia, USA | deu |
| kops.date.conferenceEnd | 2016-01-10 | eng |
| kops.date.conferenceStart | 2016-01-10 | eng |
| kops.flag.knbibliography | false | |
| kops.location.conference | Arlington, Virginia, USA | eng |
| kops.sourcefield | GOODRICH, Michael, ed., Michael MITZENMACHER, ed.. <i>Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2016, Arlington, Virginia, USA, January 10, 2016</i>. Philadelphia: Siam, 2016, pp. 15-29. ISBN 978-1-61197-431-7. Available under: doi: 10.1137/1.9781611974317.2 | deu |
| kops.sourcefield.plain | GOODRICH, Michael, ed., Michael MITZENMACHER, ed.. Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2016, Arlington, Virginia, USA, January 10, 2016. Philadelphia: Siam, 2016, pp. 15-29. ISBN 978-1-61197-431-7. Available under: doi: 10.1137/1.9781611974317.2 | deu |
| kops.sourcefield.plain | GOODRICH, Michael, ed., Michael MITZENMACHER, ed.. Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2016, Arlington, Virginia, USA, January 10, 2016. Philadelphia: Siam, 2016, pp. 15-29. ISBN 978-1-61197-431-7. Available under: doi: 10.1137/1.9781611974317.2 | eng |
| kops.title.conference | ALENEX 2016 | eng |
| relation.isAuthorOfPublication | a3ac49b1-8947-4bb2-840c-50a5cb77fdf4 | |
| relation.isAuthorOfPublication.latestForDiscovery | a3ac49b1-8947-4bb2-840c-50a5cb77fdf4 | |
| source.bibliographicInfo.fromPage | 15 | eng |
| source.bibliographicInfo.toPage | 29 | eng |
| source.contributor.editor | Goodrich, Michael | |
| source.contributor.editor | Mitzenmacher, Michael | |
| source.identifier.isbn | 978-1-61197-431-7 | eng |
| source.publisher | Siam | eng |
| source.publisher.location | Philadelphia | eng |
| source.title | Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2016, Arlington, Virginia, USA, January 10, 2016 | eng |