Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees

Funke, Stefan; Laue, Sören; Storandt, Sabine

Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees

Dateien

Funke_2-1tj8swzs708lo8.pdfGröße: 476 KBDownloads: 323

Datum

2017

Autor:innen

Funke, Stefan

Laue, Sören

Storandt, Sabine

Open Access-Veröffentlichung

Open Access Green

Sammlungen

Informatik und Informationswissenschaft

Publikationstyp

Beitrag zu einem Konferenzband

Publikationsstatus

Published

Erschienen in

ILLIOPOULOS, Costas S., ed. and others. 16th International Symposium on Experimental Algorithms (SEA 2017). Dagstuhl: Dagstuhl Publishing, 2017, 18. Leibniz International Proceedings in Informatics (LIPIcs). 75. ISSN 1868-8969. ISBN 978-3-95977-036-1. Available under: doi: 10.4230/LIPIcs.SEA.2017.18

Zusammenfassung

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.

Fachgebiet (DDC)

004 Informatik

Schlagwörter

personalized route planning, contraction hierarchies, linear program, separation oracle, approximate queries

Konferenz

16th International Symposium on Experimental Algorithms (SEA 2017), 21. Juni 2017 - 23. Juni 2017, London, UK

Zitieren

ISO 690

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, 21. Juni 2017 - 23. Juni 2017. In: ILLIOPOULOS, Costas S., ed. and others. 16th International Symposium on Experimental Algorithms (SEA 2017). Dagstuhl: Dagstuhl Publishing, 2017, 18. Leibniz International Proceedings in Informatics (LIPIcs). 75. ISSN 1868-8969. ISBN 978-3-95977-036-1. Available under: doi: 10.4230/LIPIcs.SEA.2017.18

BibTex

@inproceedings{Funke2017Perso-44380,
  year={2017},
  doi={10.4230/LIPIcs.SEA.2017.18},
  title={Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees},
  number={75},
  isbn={978-3-95977-036-1},
  issn={1868-8969},
  publisher={Dagstuhl Publishing},
  address={Dagstuhl},
  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: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/44380">
    <dc:creator>Laue, Sören</dc:creator>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:contributor>Laue, Sören</dc:contributor>
    <dc:rights>terms-of-use</dc:rights>
    <dcterms:title>Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees</dcterms:title>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/44380/1/Funke_2-1tj8swzs708lo8.pdf"/>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44380"/>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-12-19T12:58:47Z</dc:date>
    <dc:creator>Storandt, Sabine</dc:creator>
    <dc:language>eng</dc:language>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-12-19T12:58:47Z</dcterms:available>
    <dc:contributor>Funke, Stefan</dc:contributor>
    <dc:creator>Funke, Stefan</dc:creator>
    <dcterms:issued>2017</dcterms:issued>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/44380/1/Funke_2-1tj8swzs708lo8.pdf"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <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>

Universitätsbibliographie

Nein