4 Search Results for "Schneider, Markus"


Document
Parallel Computation of Combinatorial Symmetries

Authors: Markus Anders and Pascal Schweitzer

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)


Abstract
In practice symmetries of combinatorial structures are computed by transforming the structure into an annotated graph whose automorphisms correspond exactly to the desired symmetries. An automorphism solver is then employed to compute the automorphism group of the constructed graph. Such solvers have been developed for over 50 years, and highly efficient sequential, single core tools are available. However no competitive parallel tools are available for the task. We introduce a new parallel randomized algorithm that is based on a modification of the individualization-refinement paradigm used by sequential solvers. The use of randomization crucially enables parallelization. We report extensive benchmark results that show that our solver is competitive to state-of-the-art solvers on a single thread, while scaling remarkably well with the use of more threads. This results in order-of-magnitude improvements on many graph classes over state-of-the-art solvers. In fact, our tool is the first parallel graph automorphism tool that outperforms current sequential tools.

Cite as

Markus Anders and Pascal Schweitzer. Parallel Computation of Combinatorial Symmetries. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{anders_et_al:LIPIcs.ESA.2021.6,
  author =	{Anders, Markus and Schweitzer, Pascal},
  title =	{{Parallel Computation of Combinatorial Symmetries}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus 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.2021.6},
  URN =		{urn:nbn:de:0030-drops-145875},
  doi =		{10.4230/LIPIcs.ESA.2021.6},
  annote =	{Keywords: graph isomorphism, automorphism groups, algorithm engineering, parallel algorithms}
}
Document
Distance Computations in the Hybrid Network Model via Oracle Simulations

Authors: Keren Censor-Hillel, Dean Leitersdorf, and Volodymyr Polosukhin

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)


Abstract
The Hybrid network model was introduced in [Augustine et al., SODA '20] for laying down a theoretical foundation for networks which combine two possible modes of communication: One mode allows high-bandwidth communication with neighboring nodes, and the other allows low-bandwidth communication over few long-range connections at a time. This fundamentally abstracts networks such as hybrid data centers, and class-based software-defined networks. Our technical contribution is a density-aware approach that allows us to simulate a set of oracles for an overlay skeleton graph over a Hybrid network. As applications of our oracle simulations, with additional machinery that we provide, we derive fast algorithms for fundamental distance-related tasks. One of our core contributions is an algorithm in the Hybrid model for computing exact weighted shortest paths from Õ(n^{1/3}) sources which completes in Õ(n^{1/3}) rounds w.h.p. This improves, in both the runtime and the number of sources, upon the algorithm of [Kuhn and Schneider, PODC ’20], which computes shortest paths from a single source in Õ(n^{2/5}) rounds w.h.p. We additionally show a 2-approximation for weighted diameter and a (1+ε)-approximation for unweighted diameter, both in Õ(n^{1/3}) rounds w.h.p., which is comparable to the ̃ Ω(n^{1/3}) lower bound of [Kuhn and Schneider, PODC ’20] for a (2-ε)-approximation for weighted diameter and an exact unweighted diameter. We also provide fast distance approximations from multiple sources and fast approximations for eccentricities.

Cite as

Keren Censor-Hillel, Dean Leitersdorf, and Volodymyr Polosukhin. Distance Computations in the Hybrid Network Model via Oracle Simulations. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.STACS.2021.21,
  author =	{Censor-Hillel, Keren and Leitersdorf, Dean and Polosukhin, Volodymyr},
  title =	{{Distance Computations in the Hybrid Network Model via Oracle Simulations}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{21:1--21:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.21},
  URN =		{urn:nbn:de:0030-drops-136663},
  doi =		{10.4230/LIPIcs.STACS.2021.21},
  annote =	{Keywords: Distributed graph algorithms, Hybrid network model, Distance computations}
}
Document
Short Paper
Granular Spatial Calculi of Relative Directions or Movements with Parallelism: Consistent Account (Short Paper)

Authors: Reinhard Moratz, Leif Sabellek, and Thomas Schneider

Published in: LIPIcs, Volume 142, 14th International Conference on Spatial Information Theory (COSIT 2019)


Abstract
The OPRA* calculus family, originally suggested by Frank Dylla, adds parallelism to the OPRA calculus family which is very popular in Qualitative Spatio-temporal Reasoning (QSTR). Adding parallelism enables the direct representation of parallel moving objects, which is relevant in many applications like traffic monitoring. However, it turned out that it is hard to derive a sound geometric analysis. So far no sound spatial reasoning was supported. Our new generic analysis based on combining condensed semantics lower bounds with upper bounds from algebraic mappings of related calculi already leads to a close and sound approximization. This approximization can be easily augmented with a manual analysis of few geometrically underconstrained cases and then yields a complete analysis of possible configurations in this oriented point framework. This for the first time enables sound standard QSTR constraint reasoning for the OPRA* calculus family.

Cite as

Reinhard Moratz, Leif Sabellek, and Thomas Schneider. Granular Spatial Calculi of Relative Directions or Movements with Parallelism: Consistent Account (Short Paper). In 14th International Conference on Spatial Information Theory (COSIT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 142, pp. 28:1-28:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{moratz_et_al:LIPIcs.COSIT.2019.28,
  author =	{Moratz, Reinhard and Sabellek, Leif and Schneider, Thomas},
  title =	{{Granular Spatial Calculi of Relative Directions or Movements with Parallelism: Consistent Account}},
  booktitle =	{14th International Conference on Spatial Information Theory (COSIT 2019)},
  pages =	{28:1--28:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-115-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{142},
  editor =	{Timpf, Sabine and Schlieder, Christoph and Kattenbeck, Markus and Ludwig, Bernd and Stewart, Kathleen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2019.28},
  URN =		{urn:nbn:de:0030-drops-111206},
  doi =		{10.4230/LIPIcs.COSIT.2019.28},
  annote =	{Keywords: qualitative spatial-temporal reasoning, composition table, condensed semantics, homomorphic embeddings}
}
Document
Data Warehousing: from Occasional OLAP to Real-time Business Intelligence (Dagstuhl Seminar 11361)

Authors: Markus Schneider, Gottfried Vossen, and Esteban Zimányi

Published in: Dagstuhl Reports, Volume 1, Issue 9 (2012)


Abstract
This report documents the outcomes of the Dagstuhl Seminar 11361 "Data Warehousing: from Occasional OLAP to Real-time Business Intelligence". In the past, data warehousing and analytical processing (OLAP) have produced fundamental and important technologies for the design, management, and use of information systems for decision support. Indeed, many industrial and administrative organizations have successfully used data warehouses to collect essential indicators that help them improve their business processes and their decision making efforts. Recent developments like column stores instead of row stores at the physical level, real-time data warehousing and Business Intelligence applications at the conceptual level, and decision support for new emerging applications have raised new research questions. This seminar has focused on the following five main topics: (i) Real-Time Data Warehouses and Business Intelligence, (ii) Spatio-Temporal Data Warehousing, (iii) Situational Business Intelligence, (iv) Query Processing in Data Warehouses, and (v) Knowledge Extraction and Management in Data Warehouses. These topics were discussed in parallel groups and each group identified open research issues and new challenges.

Cite as

Markus Schneider, Gottfried Vossen, and Esteban Zimányi. Data Warehousing: from Occasional OLAP to Real-time Business Intelligence (Dagstuhl Seminar 11361). In Dagstuhl Reports, Volume 1, Issue 9, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@Article{schneider_et_al:DagRep.1.9.1,
  author =	{Schneider, Markus and Vossen, Gottfried and Zim\'{a}nyi, Esteban},
  title =	{{Data Warehousing: from Occasional OLAP to Real-time Business Intelligence (Dagstuhl Seminar 11361)}},
  pages =	{1--25},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{9},
  editor =	{Schneider, Markus and Vossen, Gottfried and Zim\'{a}nyi, Esteban},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.1.9.1},
  URN =		{urn:nbn:de:0030-drops-33178},
  doi =		{10.4230/DagRep.1.9.1},
  annote =	{Keywords: Business Intelligence, Data Warehouses, OLAP, Spatio-temporal information, ETL, Service Orientation, Query optimization}
}
  • Refine by Author
  • 1 Anders, Markus
  • 1 Censor-Hillel, Keren
  • 1 Leitersdorf, Dean
  • 1 Moratz, Reinhard
  • 1 Polosukhin, Volodymyr
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Spatial and physical reasoning
  • 1 Computing methodologies → Symbolic calculus algorithms
  • 1 Information systems → Spatial-temporal systems
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Distributed algorithms
  • Show More...

  • Refine by Keyword
  • 1 Business Intelligence
  • 1 Data Warehouses
  • 1 Distance computations
  • 1 Distributed graph algorithms
  • 1 ETL
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2021
  • 1 2011
  • 1 2019

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