2 Search Results for "Schulz, Frank"

Document
DOI: 10.4230/LIPIcs.SEA.2020.17
Efficient Route Planning with Temporary Driving Bans, Road Closures, and Rated Parking Areas

Authors: Alexander Kleff, Frank Schulz, Jakob Wagenblatt, and Tim Zeitz

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
We study the problem of planning routes in road networks when certain streets or areas are closed at certain times. For heavy vehicles, such areas may be very large since many European countries impose temporary driving bans during the night or on weekends. In this setting, feasible routes may require waiting at parking areas, and several feasible routes with different trade-offs between waiting and driving detours around closed areas may exist. We propose a novel model in which driving and waiting are assigned abstract costs, and waiting costs are location-dependent to reflect the different quality of the parking areas. Our goal is to find Pareto-optimal routes with regards to arrival time at the destination and total cost. We investigate the complexity of the model and determine a necessary constraint on the cost parameters such that the problem is solvable in polynomial time. We present a thoroughly engineered implementation and perform experiments on a production-grade real world data set. The experiments show that our implementation can answer realistic queries in around a second or less which makes it feasible for practical application.
Cite as

Alexander Kleff, Frank Schulz, Jakob Wagenblatt, and Tim Zeitz. Efficient Route Planning with Temporary Driving Bans, Road Closures, and Rated Parking Areas. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kleff_et_al:LIPIcs.SEA.2020.17,
  author =	{Kleff, Alexander and Schulz, Frank and Wagenblatt, Jakob and Zeitz, Tim},
  title =	{{Efficient Route Planning with Temporary Driving Bans, Road Closures, and Rated Parking Areas}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.17},
  URN =		{urn:nbn:de:0030-drops-120910},
  doi =		{10.4230/LIPIcs.SEA.2020.17},
  annote =	{Keywords: driving bans, realistic road networks, route planning, shortest paths}
}
Document
DOI: 10.4230/DagSemProc.05061.6
Node Identification Schemes for Efficient XML Retrieval

Authors: Felix Weigel, Klaus U. Schulz, and Holger Meuss

Published in: Dagstuhl Seminar Proceedings, Volume 5061, Foundations of Semistructured Data (2005)

Abstract
Node identifiers (IDs) encoding part of the tree structure in XML documents can save I/O for table look-ups, thus speeding up the evaluation of path and tree queries on large persistent document collections. In particular, binary tree relations such as the extended XPath axes can be either decided for a given pair of node IDs, or reconstructed for a single node ID, without access to secondary storage. Several ID schemes have been proposed so far, which differ with respect to (1) expressiveness, i.e. which relations can be decided or reconstructed from IDs, (2) the runtime performance and asymptotic behaviour of decision and reconstruction operations, (3) the storage overhead for the IDs, and (4) robustness, i.e. behaviour in the presence of updates. First we review five ID schemes, positioning them in the trade-off between these four comparison criteria. Then a new ID scheme called BIRD, for Balanced Index-based ID scheme for Reconstruction and Decision, is introduced and illustrated throughout several examples of decision and reconstruction operations on IDs. We argue that emphasizing runtime performance and expressive power, BIRDs strategy in the above trade-off is best for many applications, especially where storage minimization is not the primary goal and updates occur in a bulk-fashion rather than in realtime. Our experimental results on document collections of up to one gigabyte prove BIRD to be most efficient in terms of expressiveness and runtime performance. Most notably, BIRD is the only scheme to support both decision and reconstruction of many relations in constant time. But also in terms of storage and robustness BIRD is highly competitive.
Cite as

Felix Weigel, Klaus U. Schulz, and Holger Meuss. Node Identification Schemes for Efficient XML Retrieval. In Foundations of Semistructured Data. Dagstuhl Seminar Proceedings, Volume 5061, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{weigel_et_al:DagSemProc.05061.6,
  author =	{Weigel, Felix and Schulz, Klaus U. and Meuss, Holger},
  title =	{{Node Identification Schemes for Efficient XML Retrieval}},
  booktitle =	{Foundations of Semistructured Data},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5061},
  editor =	{Frank Neven and Thomas Schwentick and Dan Suciu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05061.6},
  URN =		{urn:nbn:de:0030-drops-2292},
  doi =		{10.4230/DagSemProc.05061.6},
  annote =	{Keywords: node identification scheme, labelling scheme, numbering scheme, naming scheme, tree encoding, BIRD}
}
  • Refine by Author
  • 1 Kleff, Alexander
  • 1 Meuss, Holger
  • 1 Schulz, Frank
  • 1 Schulz, Klaus U.
  • 1 Wagenblatt, Jakob
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Transportation
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Shortest paths

  • Refine by Keyword
  • 1 BIRD
  • 1 driving bans
  • 1 labelling scheme
  • 1 naming scheme
  • 1 node identification scheme
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2005
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact