KOPS - The Institutional Repository of the University of Konstanz

Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees

Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees

Cite This

Files in this item

Checksum: MD5:3b989ac46e8ebcc7e32d479c56e12c4a

FUNKE, Stefan, Sören LAUE, Sabine STORANDT, 2017. Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees. 16th International Symposium on Experimental Algorithms (SEA 2017). London, UK, Jun 21, 2017 - Jun 23, 2017. In: ILLIOPOULOS, Costas S., ed. and others. 16th International Symposium on Experimental Algorithms (SEA 2017). Dagstuhl:Dagstuhl Publishing, 18. ISSN 1868-8969. ISBN 978-3-95977-036-1. Available under: doi: 10.4230/LIPIcs.SEA.2017.18

@inproceedings{Funke2017Perso-44380, title={Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees}, year={2017}, doi={10.4230/LIPIcs.SEA.2017.18}, number={75}, isbn={978-3-95977-036-1}, issn={1868-8969}, address={Dagstuhl}, publisher={Dagstuhl Publishing}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, booktitle={16th International Symposium on Experimental Algorithms (SEA 2017)}, editor={Illiopoulos, Costas S.}, author={Funke, Stefan and Laue, Sören and Storandt, Sabine}, note={Article Number: 18} }

<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/rdf/resource/123456789/44380"> <dc:creator>Funke, Stefan</dc:creator> <dc:creator>Laue, Sören</dc:creator> <dcterms:title>Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees</dcterms:title> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44380"/> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/44380/1/Funke_2-1tj8swzs708lo8.pdf"/> <dc:contributor>Storandt, Sabine</dc:contributor> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/44380/1/Funke_2-1tj8swzs708lo8.pdf"/> <dc:rights>terms-of-use</dc:rights> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:contributor>Laue, Sören</dc:contributor> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:contributor>Funke, Stefan</dc:contributor> <dc:language>eng</dc:language> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-12-19T12:58:47Z</dcterms:available> <dcterms:issued>2017</dcterms:issued> <dc:creator>Storandt, Sabine</dc:creator> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-12-19T12:58:47Z</dc:date> <dcterms:abstract xml:lang="eng">In a personalized route planning query, a user can specify how relevant different criteria as travel time, gas consumption, scenicness, etc. are for his individual definition of an optimal route. Recently developed acceleration schemes for personalized route planning, which rely on preprocessing, achieve a significant speed-up over the Dijkstra baseline for a small number of criteria. But for more than five criteria, either the preprocessing becomes too complicated or the query answering is slow. In this paper, we first present a new LP-based preprocessing technique which allows to deal with many criteria efficiently. In addition, we show how to further reduce query times for all known personalized route planning acceleration schemes by considering approximate queries. We design a data structure which allows not only to have personalized costs but also individual approximation guarantees per query, allowing to trade solution quality against query time at the user's discretion. This data structure is the first to enable a speed-up of more than 100 for ten criteria while accepting only 0.01% increased costs.</dcterms:abstract> </rdf:Description> </rdf:RDF>

Downloads since Dec 19, 2018 (Information about access statistics)

Funke_2-1tj8swzs708lo8.pdf 209

This item appears in the following Collection(s)

Search KOPS


Browse

My Account