6 Search Results for "Berger, Michael"

Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2023.62
Godzilla Onions: A Skit and Applet to Explain Euclidean Half-Plane Fractional Cascading (Media Exposition)

Authors: Richard Berger, Vincent Ha, David Kratz, Michael Lin, Jeremy Moyer, and Christopher J. Tralie

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
We provide a skit and an applet to illustrate fractional cascading in the context of half-plane range search for points in the Euclidean plane, which takes O(log N + h) output-sensitive time. In the video, a group of news anchors struggles to find the correct data structure to efficiently send out an early warning to the residents of Philadelphia who will be overtaken by a marching line of Godzillas. After exploring several options, the group eventually settles on onions and fractional cascading, only to discover that they themselves are in the line of fire! In the applet, we show step by step details of preprocessing to build the onions with fractional cascading and the subsequent query of the "Godzilla line" against the onion layers. Our video skit and applet can be found at https://ctralie.github.io/GodzillaOnions/
Cite as

Richard Berger, Vincent Ha, David Kratz, Michael Lin, Jeremy Moyer, and Christopher J. Tralie. Godzilla Onions: A Skit and Applet to Explain Euclidean Half-Plane Fractional Cascading (Media Exposition). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 62:1-62:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{berger_et_al:LIPIcs.SoCG.2023.62,
  author =	{Berger, Richard and Ha, Vincent and Kratz, David and Lin, Michael and Moyer, Jeremy and Tralie, Christopher J.},
  title =	{{Godzilla Onions: A Skit and Applet to Explain Euclidean Half-Plane Fractional Cascading}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{62:1--62:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.62},
  URN =		{urn:nbn:de:0030-drops-179129},
  doi =		{10.4230/LIPIcs.SoCG.2023.62},
  annote =	{Keywords: convex hulls, onions, fractional cascading, visualization, d3}
}
Document
DOI: 10.4230/OASIcs.Fog-IoT.2020.9
Next-Generation SDN and Fog Computing: A New Paradigm for SDN-Based Edge Computing

Authors: Eder Ollora Zaballa, David Franco, Marina Aguado, and Michael Stübert Berger

Published in: OASIcs, Volume 80, 2nd Workshop on Fog Computing and the IoT (Fog-IoT 2020)

Abstract
In the last few years, we have been able to see how terms like Mobile Edge Computing, Cloudlets, and Fog computing have arisen as concepts that reach a level of popularity to express computing towards network Edge. Shifting some processing tasks from the Cloud to the Edge brings challenges to the table that might have been non-considered before in next-generation Software-Defined Networking (SDN). Efficient routing mechanisms, Edge Computing, and SDN applications are challenging to deploy as controllers are expected to have different distributions. In particular, with the advances of SDN and the P4 language, there are new opportunities and challenges that next-generation SDN has for Fog computing. The development of new pipelines along with the progress regarding control-to-data plane programming protocols can also promote data and control plane function offloading. We propose a new mechanism of deploying SDN control planes both locally and remotely to attend different challenges. We encourage researchers to develop new ways to functionally deploying Fog and Cloud control planes that let cross-layer planes interact by deploying specific control and data plane applications. With our proposal, the control and data plane distribution can provide a lower response time for locally deployed applications (local control plane). Besides, it can still be beneficial for a centralized and remotely placed control plane, for applications such as path computation within the same network and between separated networks (remote control plane).
Cite as

Eder Ollora Zaballa, David Franco, Marina Aguado, and Michael Stübert Berger. Next-Generation SDN and Fog Computing: A New Paradigm for SDN-Based Edge Computing. In 2nd Workshop on Fog Computing and the IoT (Fog-IoT 2020). Open Access Series in Informatics (OASIcs), Volume 80, pp. 9:1-9:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ollorazaballa_et_al:OASIcs.Fog-IoT.2020.9,
  author =	{Ollora Zaballa, Eder and Franco, David and Aguado, Marina and Berger, Michael St\"{u}bert},
  title =	{{Next-Generation SDN and Fog Computing: A New Paradigm for SDN-Based Edge Computing}},
  booktitle =	{2nd Workshop on Fog Computing and the IoT (Fog-IoT 2020)},
  pages =	{9:1--9:8},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-144-3},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{80},
  editor =	{Cervin, Anton and Yang, Yang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.Fog-IoT.2020.9},
  URN =		{urn:nbn:de:0030-drops-120033},
  doi =		{10.4230/OASIcs.Fog-IoT.2020.9},
  annote =	{Keywords: SDN, P4, P4Runtime, control planes, Fog, Edge}
}
Document
DOI: 10.4230/OASIcs.Fog-IoT.2020.12
Detection of Fog Network Data Telemetry Using Data Plane Programming

Authors: Zifan Zhou, Eder Ollora Zaballa, Michael Stübert Berger, and Ying Yan

Published in: OASIcs, Volume 80, 2nd Workshop on Fog Computing and the IoT (Fog-IoT 2020)

Abstract
Fog computing has been introduced to deliver Cloud-based services to the Internet of Things (IoT) devices. It locates geographically closer to IoT devices than Cloud networks and aims at offering latency-critical computation and storage to end-user applications. To leverage Fog computing for computational offloading from end-users, it is important to optimize resources in the Fog nodes dynamically. Provisioning requires knowledge of the current network state, thus, monitoring mechanisms play a significant role to conduct resource management in the network. To keep track of the state of devices, we use P4, a data-plane programming language, to describe data-plane abstraction of Fog network devices and collect telemetry without the intervention of the control plane or adding a big amount of overhead. In this paper, we propose a software-defined architecture with a programmable data plane for data telemetry detection that can be integrated into Fog network resource management. After the implementation of detecting data telemetry based on In-Band Network Telemetry (INT) within a Mininet simulation, we show the available features and preliminary Fog resource management based on the collected data telemetry and future telemetry-based traffic engineering possibilities.
Cite as

Zifan Zhou, Eder Ollora Zaballa, Michael Stübert Berger, and Ying Yan. Detection of Fog Network Data Telemetry Using Data Plane Programming. In 2nd Workshop on Fog Computing and the IoT (Fog-IoT 2020). Open Access Series in Informatics (OASIcs), Volume 80, pp. 12:1-12:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{zhou_et_al:OASIcs.Fog-IoT.2020.12,
  author =	{Zhou, Zifan and Ollora Zaballa, Eder and Berger, Michael St\"{u}bert and Yan, Ying},
  title =	{{Detection of Fog Network Data Telemetry Using Data Plane Programming}},
  booktitle =	{2nd Workshop on Fog Computing and the IoT (Fog-IoT 2020)},
  pages =	{12:1--12:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-144-3},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{80},
  editor =	{Cervin, Anton and Yang, Yang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.Fog-IoT.2020.12},
  URN =		{urn:nbn:de:0030-drops-120062},
  doi =		{10.4230/OASIcs.Fog-IoT.2020.12},
  annote =	{Keywords: SDN, P4, P4Runtime, control planes, Fog, Edge}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.25
Patching Colors with Tensors

Authors: Cornelius Brand

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
We describe a generic way of exponentially speeding up algorithms which rely on Color-Coding by using the recently introduced technique of Extensor-Coding (Brand, Dell and Husfeldt, STOC 2018). To demonstrate the usefulness of this "patching" of Color-Coding algorithms, we apply it ad hoc to the exponential-space algorithms given in Gutin et al. (Journal Comp. Sys. Sci. 2018) and obtain the fastest known deterministic algorithms for, among others, the k-internal out-branching and k-internal spanning tree problems. To realize these technical advances, we make qualitative progress in a special case of the detection of multilinear monomials in multivariate polynomials: We give the first deterministic fixed-parameter tractable algorithm for the k-multilinear detection problem on a class of arithmetic circuits that may involve cancellations, as long as the computed polynomial is promised to satisfy a certain natural condition. Furthermore, we explore the limitations of using this very approach to speed up algorithms by determining exactly the dimension of a crucial subalgebra of extensors that arises naturally in the instantiation of the technique: It is equal to F_{2k+1}, the kth odd term in the Fibonacci sequence. To determine this dimension, we use tools from the theory of Gröbner bases, and the studied algebraic object may be of independent interest. We note that the asymptotic bound of F_{2k+1} ~~ phi^(2k) = O(2.619^k) curiously coincides with the running time bound on one of the fastest algorithms for the k-path problem based on representative sets due to Fomin et al. (JACM 2016). Here, phi is the golden ratio.
Cite as

Cornelius Brand. Patching Colors with Tensors. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{brand:LIPIcs.ESA.2019.25,
  author =	{Brand, Cornelius},
  title =	{{Patching Colors with Tensors}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{25:1--25:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.25},
  URN =		{urn:nbn:de:0030-drops-111467},
  doi =		{10.4230/LIPIcs.ESA.2019.25},
  annote =	{Keywords: Color-Coding, Extensor-Coding, internal out-branching, colorful problems, algebraic algorithms, multilinear detection, deterministic algorithms, exterior algebra}
}
Document
DOI: 10.4230/DagSemProc.07462.13
Integrated Human Behavior Modeling

Authors: Michael Berger, Dagmar Beyer, and Stephan Prueckner

Published in: Dagstuhl Seminar Proceedings, Volume 7462, Assisted Living Systems - Models, Architectures and Engineering Approaches (2008)

Abstract
In order to prevent emergencies or critical situations where humans are the origin, a timely provision of information thus obtained for the coordinating services and the on-site staff (e.g., emergency dispatch centers, emergency physicians, police) is necessary. The detection of critical situations and the early alarming, e.g., in case of deterioration of the person’s health status or a critical incident in a public space like a stadium, could prevent acute emergency cases and the resulting negative impact on individual persons and the environment. To analyze the current situation, the human behavior must be understood, analyzed and modeled on the basis of, e.g., monitored activities, user mobility, and selected biological parameters. Only an integrated and comprehensive human behavior model can be the basis for the prevention of emergency cases.
Cite as

Michael Berger, Dagmar Beyer, and Stephan Prueckner. Integrated Human Behavior Modeling. In Assisted Living Systems - Models, Architectures and Engineering Approaches. Dagstuhl Seminar Proceedings, Volume 7462, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{berger_et_al:DagSemProc.07462.13,
  author =	{Berger, Michael and Beyer, Dagmar and Prueckner, Stephan},
  title =	{{Integrated Human Behavior Modeling}},
  booktitle =	{Assisted Living Systems - Models, Architectures and Engineering Approaches},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7462},
  editor =	{Arthur I. Karshmer and J\"{u}rgen Nehmer and Hartmut Raffler and Gerhard Tr\"{o}ster},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07462.13},
  URN =		{urn:nbn:de:0030-drops-14574},
  doi =		{10.4230/DagSemProc.07462.13},
  annote =	{Keywords: Human Behavior Modeling}
}
Document
DOI: 10.4230/DagSemProc.04351.11
Continuous Semantics for Termination Proofs

Authors: Ulrich Berger

Published in: Dagstuhl Seminar Proceedings, Volume 4351, Spatial Representation: Discrete vs. Continuous Computational Models (2005)

Abstract
We prove a general strong normalization theorem for higher type rewrite systems based on Tait's strong computability predicates and a strictly continuous domain-theoretic semantics. The theorem applies to extensions of Goedel's system $T$, but also to various forms of bar recursion for which termination was hitherto unknown.
Cite as

Ulrich Berger. Continuous Semantics for Termination Proofs. In Spatial Representation: Discrete vs. Continuous Computational Models. Dagstuhl Seminar Proceedings, Volume 4351, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{berger:DagSemProc.04351.11,
  author =	{Berger, Ulrich},
  title =	{{Continuous Semantics for Termination Proofs}},
  booktitle =	{Spatial Representation: Discrete vs. Continuous Computational Models},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4351},
  editor =	{Ralph Kopperman and Michael B. Smyth and Dieter Spreen and Julian Webster},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04351.11},
  URN =		{urn:nbn:de:0030-drops-1300},
  doi =		{10.4230/DagSemProc.04351.11},
  annote =	{Keywords: Higher-order term rewriting , termination , domain theory}
}
  • Refine by Author
  • 2 Berger, Michael Stübert
  • 2 Ollora Zaballa, Eder
  • 1 Aguado, Marina
  • 1 Berger, Michael
  • 1 Berger, Richard
  • Show More...

  • Refine by Classification
  • 2 Networks → Programmable networks
  • 1 Computing methodologies → Algebraic algorithms
  • 1 Human-centered computing → Visualization toolkits
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Parameterized complexity and exact algorithms
  • Show More...

  • Refine by Keyword
  • 2 Edge
  • 2 Fog
  • 2 P4
  • 2 P4Runtime
  • 2 SDN
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2020
  • 1 2005
  • 1 2008
  • 1 2019
  • 1 2023

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