2 Search Results for "Mansmann, Florian"

Document

DOI: 10.4230/LIPIcs.SEA.2024.19

Algorithms for Gradual Polyline Simplification

Authors: Nick Krumbholz, Stefan Funke, Peter Schäfer, and Sabine Storandt

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract

Displaying line data is important in many visualization applications, and especially in the context of interactive geographical and cartographic visualization. When rendering linear features as roads, rivers or movement data on zoomable maps, the challenge is to display the data in an appropriate level of detail. A too detailed representation results in slow rendering and cluttered maps, while a too coarse representation might miss important data aspects. In this paper, we propose the gradual line simplification (GLS) problem, which aims to compute a fine-grained succession of consistent simplifications of a given input polyline with certain quality guarantees. The core concept of gradual simplification is to iteratively remove points from the polyline to obtain increasingly coarser representations. We devise two objective functions to guide this simplification process and present dynamic programs that compute the optimal solutions in 𝒪(n³) for an input line with n points. For practical application to large inputs, we also devise significantly faster greedy algorithms that provide constant factor guarantees for both problem variants at once. In an extensive experimental study on real-world data, we demonstrate that our algorithms are capable of producing simplification sequences of high quality within milliseconds on polylines consisting of over half a million points.

Cite as

Nick Krumbholz, Stefan Funke, Peter Schäfer, and Sabine Storandt. Algorithms for Gradual Polyline Simplification. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{krumbholz_et_al:LIPIcs.SEA.2024.19,
  author =	{Krumbholz, Nick and Funke, Stefan and Sch\"{a}fer, Peter and Storandt, Sabine},
  title =	{{Algorithms for Gradual Polyline Simplification}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.19},
  URN =		{urn:nbn:de:0030-drops-203847},
  doi =		{10.4230/LIPIcs.SEA.2024.19},
  annote =	{Keywords: Polyline simplification, Progressive simplification, Fr\'{e}chet distance}
}

Document

DOI: 10.4230/DagSemProc.09211.2

09211 Executive Summary – Visualization and Monitoring of Network Traffic

Authors: Daniel A. Keim, Aiko Pras, Jürgen Schönwälder, Pak Chung Wong, and Florian Mansmann

Published in: Dagstuhl Seminar Proceedings, Volume 9211, Visualization and Monitoring of Network Traffic (2009)

Abstract

The seamless operation of the Internet requires being able to monitor and visualize the actual behaviour of the network. Today, IP network operators usually collect network flow statistics from critical points of their network infrastructure. Flows aggregate packets that share common properties. Flow records are stored and analyzed to extract accounting information and increasingly to identify and isolate network problems or security incidents. While network problems or attacks significantly changing traffic patterns are relatively easy to identify, it tends to be much more challenging to identify creeping changes or attacks and faults that manifest themselves only by very careful analysis of initially seemingly unrelated traffic pattern and their changes. There are currently no deployable good solutions and research in this area is just starting. In addition, the large volume of flow data on high capacity networks and exchange points requires to move to probabilistic sampling techniques, which require new analysis techniques to calculate and also visualize the uncertainty attached to data sets.

Cite as

Daniel A. Keim, Aiko Pras, Jürgen Schönwälder, Pak Chung Wong, and Florian Mansmann. 09211 Executive Summary – Visualization and Monitoring of Network Traffic. In Visualization and Monitoring of Network Traffic. Dagstuhl Seminar Proceedings, Volume 9211, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{keim_et_al:DagSemProc.09211.2,
  author =	{Keim, Daniel A. and Pras, Aiko and Sch\"{o}nw\"{a}lder, J\"{u}rgen and Wong, Pak Chung and Mansmann, Florian},
  title =	{{09211 Executive Summary – Visualization and Monitoring of Network Traffic}},
  booktitle =	{Visualization and Monitoring of Network Traffic},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9211},
  editor =	{Daniel A. Keim and Aiko Pras and J\"{u}rgen Sch\"{o}nw\"{a}lder and Pak Chung Wong},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09211.2},
  URN =		{urn:nbn:de:0030-drops-21574},
  doi =		{10.4230/DagSemProc.09211.2},
  annote =	{Keywords: Computer Networks, Internet, Monitoring of Networks and Services, Visualization Animation}
}

Refine by Author
1 Funke, Stefan
1 Keim, Daniel A.
1 Krumbholz, Nick
1 Mansmann, Florian
1 Pras, Aiko
Show More...

Refine by Classification
1 Theory of computation → Computational geometry
1 Theory of computation → Design and analysis of algorithms

Refine by Keyword
1 Computer Networks
1 Fréchet distance
1 Internet
1 Monitoring of Networks and Services
1 Polyline simplification
Show More...

Refine by Type
2 document

Refine by Publication Year
1 2009
1 2024