DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2017.18

Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees

Authors: Stefan Funke, Sören Laue, and Sabine Storandt

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract

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.

Cite as

Stefan Funke, Sören Laue, and Sabine Storandt. Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{funke_et_al:LIPIcs.SEA.2017.18,
  author =	{Funke, Stefan and Laue, S\"{o}ren and Storandt, Sabine},
  title =	{{Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.18},
  URN =		{urn:nbn:de:0030-drops-76255},
  doi =		{10.4230/LIPIcs.SEA.2017.18},
  annote =	{Keywords: personalized route planning, contraction hierarchies, linear program, separation oracle, approximate queries}
}

Document

DOI: 10.4230/LIPIcs.ESA.2016.16

Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane

Authors: Thomas Bläsius, Tobias Friedrich, Anton Krohmer, and Sören Laue

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract

Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require a runtime of Omega(n^2). Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics like Log-likelihood and greedy routing our algorithm discovers embeddings that are very close to the ground truth.

Cite as

Thomas Bläsius, Tobias Friedrich, Anton Krohmer, and Sören Laue. Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.ESA.2016.16,
  author =	{Bl\"{a}sius, Thomas and Friedrich, Tobias and Krohmer, Anton and Laue, S\"{o}ren},
  title =	{{Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.16},
  URN =		{urn:nbn:de:0030-drops-63670},
  doi =		{10.4230/LIPIcs.ESA.2016.16},
  annote =	{Keywords: hyperbolic random graphs, embedding, power-law graphs, hyperbolic plane}
}

Search Results

Documents authored by Laue, Sören

Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees

Abstract

Cite as

Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane

Abstract

Cite as

Thanks for your feedback!

Could not send message