TY - JOUR
A1 - Casel, Katrin
A1 - Fischbeck, Philipp
A1 - Friedrich, Tobias
A1 - Göbel, Andreas
A1 - Lagodzinski, Julius Albert Gregor
T1 - Zeros and approximations of Holant polynomials on the complex plane
JF - Computational complexity : CC
N2 - We present fully polynomial time approximation schemes for a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into partition functions of abstract combinatorial structures known as polymers in statistical physics. Our method involves establishing zero-free regions for the partition functions of polymer models and using the most significant terms of the cluster expansion to approximate them. Results of our technique include new approximation and sampling algorithms for a diverse class of Holant polynomials in the low-temperature regime (i.e. small external field) and approximation algorithms for general Holant problems with small signature weights. Additionally, we give randomised approximation and sampling algorithms with faster running times for more restrictive classes. Finally, we improve the known zero-free regions for a perfect matching polynomial.
KW - Holant problems
KW - approximate counting
KW - partition functions
KW - graph
KW - polynomials
Y1 - 2022
U6 - https://doi.org/10.1007/s00037-022-00226-5
SN - 1016-3328
SN - 1420-8954
VL - 31
IS - 2
PB - Springer
CY - Basel
ER -
TY - JOUR
A1 - Friedrich, Tobias
A1 - Katzmann, Maximilian
A1 - Krohmer, Anton
T1 - Unbounded Discrepancy of Deterministic Random Walks on Grids
JF - SIAM journal on discrete mathematics
N2 - Random walks are frequently used in randomized algorithms. We study a derandomized variant of a random walk on graphs called the rotor-router model. In this model, instead of distributing tokens randomly, each vertex serves its neighbors in a fixed deterministic order. For most setups, both processes behave in a remarkably similar way: Starting with the same initial configuration, the number of tokens in the rotor-router model deviates only slightly from the expected number of tokens on the corresponding vertex in the random walk model. The maximal difference over all vertices and all times is called single vertex discrepancy. Cooper and Spencer [Combin. Probab. Comput., 15 (2006), pp. 815-822] showed that on Z(d), the single vertex discrepancy is only a constant c(d). Other authors also determined the precise value of c(d) for d = 1, 2. All of these results, however, assume that initially all tokens are only placed on one partition of the bipartite graph Z(d). We show that this assumption is crucial by proving that, otherwise, the single vertex discrepancy can become arbitrarily large. For all dimensions d >= 1 and arbitrary discrepancies l >= 0, we construct configurations that reach a discrepancy of at least l.
KW - deterministic random walk
KW - rotor-router model
KW - single vertex discrepancy
Y1 - 2018
U6 - https://doi.org/10.1137/17M1131088
SN - 0895-4801
SN - 1095-7146
VL - 32
IS - 4
SP - 2441
EP - 2452
PB - Society for Industrial and Applied Mathematics
CY - Philadelphia
ER -
TY - JOUR
A1 - Friedrich, Tobias
A1 - Kötzing, Timo
A1 - Krejca, Martin Stefan
T1 - Unbiasedness of estimation-of-distribution algorithms
JF - Theoretical computer science
N2 - In the context of black-box optimization, black-box complexity is used for understanding the inherent difficulty of a given optimization problem. Central to our understanding of nature-inspired search heuristics in this context is the notion of unbiasedness. Specialized black-box complexities have been developed in order to better understand the limitations of these heuristics - especially of (population-based) evolutionary algorithms (EAs). In contrast to this, we focus on a model for algorithms explicitly maintaining a probability distribution over the search space: so-called estimation-of-distribution algorithms (EDAs). We consider the recently introduced n-Bernoulli-lambda-EDA framework, which subsumes, for example, the commonly known EDAs PBIL, UMDA, lambda-MMAS(IB), and cGA. We show that an n-Bernoulli-lambda-EDA is unbiased if and only if its probability distribution satisfies a certain invariance property under isometric automorphisms of [0, 1](n). By restricting how an n-Bernoulli-lambda-EDA can perform an update, in a way common to many examples, we derive conciser characterizations, which are easy to verify. We demonstrate this by showing that our examples above are all unbiased. (C) 2018 Elsevier B.V. All rights reserved.
KW - Estimation-of-distribution algorithm
KW - Unbiasedness
KW - Theory
Y1 - 2019
U6 - https://doi.org/10.1016/j.tcs.2018.11.001
SN - 0304-3975
SN - 1879-2294
VL - 785
SP - 46
EP - 59
PB - Elsevier
CY - Amsterdam
ER -
TY - JOUR
A1 - Bläsius, Thomas
A1 - Friedrich, Tobias
A1 - Krejca, Martin S.
A1 - Molitor, Louise
T1 - The impact of geometry on monochrome regions in the flip Schelling process
JF - Computational geometry
N2 - Schelling's classical segregation model gives a coherent explanation for the wide-spread phenomenon of residential segregation. We introduce an agent-based saturated open-city variant, the Flip Schelling Process (FSP), in which agents, placed on a graph, have one out of two types and, based on the predominant type in their neighborhood, decide whether to change their types; similar to a new agent arriving as soon as another agent leaves the vertex. We investigate the probability that an edge {u,v} is monochrome, i.e., that both vertices u and v have the same type in the FSP, and we provide a general framework for analyzing the influence of the underlying graph topology on residential segregation. In particular, for two adjacent vertices, we show that a highly decisive common neighborhood, i.e., a common neighborhood where the absolute value of the difference between the number of vertices with different types is high, supports segregation and, moreover, that large common neighborhoods are more decisive. As an application, we study the expected behavior of the FSP on two common random graph models with and without geometry: (1) For random geometric graphs, we show that the existence of an edge {u,v} makes a highly decisive common neighborhood for u and v more likely. Based on this, we prove the existence of a constant c>0 such that the expected fraction of monochrome edges after the FSP is at least 1/2+c. (2) For Erdős–Rényi graphs we show that large common neighborhoods are unlikely and that the expected fraction of monochrome edges after the FSP is at most 1/2+o(1). Our results indicate that the cluster structure of the underlying graph has a significant impact on the obtained segregation strength.
KW - Agent-based model
KW - Schelling segregation
KW - Spin system
Y1 - 2022
U6 - https://doi.org/10.1016/j.comgeo.2022.101902
SN - 0925-7721
SN - 1879-081X
VL - 108
PB - Elsevier
CY - Amsterdam
ER -
TY - JOUR
A1 - Blaesius, Thomas
A1 - Friedrich, Tobias
A1 - Schirneck, Friedrich Martin
T1 - The complexity of dependency detection and discovery in relational databases
JF - Theoretical computer science
N2 - Multi-column dependencies in relational databases come associated with two different computational tasks. The detection problem is to decide whether a dependency of a certain type and size holds in a given database, the discovery problem asks to enumerate all valid dependencies of that type. We settle the complexity of both of these problems for unique column combinations (UCCs), functional dependencies (FDs), and inclusion dependencies (INDs). We show that the detection of UCCs and FDs is W[2]-complete when parameterized by the solution size. The discovery of inclusion-wise minimal UCCs is proven to be equivalent under parsimonious reductions to the transversal hypergraph problem of enumerating the minimal hitting sets of a hypergraph. The discovery of FDs is equivalent to the simultaneous enumeration of the hitting sets of multiple input hypergraphs. We further identify the detection of INDs as one of the first natural W[3]-complete problems. The discovery of maximal INDs is shown to be equivalent to enumerating the maximal satisfying assignments of antimonotone, 3-normalized Boolean formulas.
KW - data profiling
KW - enumeration complexity
KW - functional dependency
KW - inclusion
KW - dependency
KW - parameterized complexity
KW - parsimonious reduction
KW - transversal hypergraph
KW - Unique column combination
KW - W[3]-completeness
Y1 - 2021
U6 - https://doi.org/10.1016/j.tcs.2021.11.020
SN - 0304-3975
SN - 1879-2294
VL - 900
SP - 79
EP - 96
PB - Elsevier
CY - Amsterdam
ER -
TY - JOUR
A1 - Friedrich, Tobias
A1 - Krejca, Martin Stefan
A1 - Rothenberger, Ralf
A1 - Arndt, Tobias
A1 - Hafner, Danijar
A1 - Kellermeier, Thomas
A1 - Krogmann, Simon
A1 - Razmjou, Armin
T1 - Routing for on-street parking search using probabilistic data
JF - AI communications : AICOM ; the European journal on artificial intelligence
N2 - A significant percentage of urban traffic is caused by the search for parking spots. One possible approach to improve this situation is to guide drivers along routes which are likely to have free parking spots. The task of finding such a route can be modeled as a probabilistic graph problem which is NP-complete. Thus, we propose heuristic approaches for solving this problem and evaluate them experimentally. For this, we use probabilities of finding a parking spot, which are based on publicly available empirical data from TomTom International B.V. Additionally, we propose a heuristic that relies exclusively on conventional road attributes. Our experiments show that this algorithm comes close to the baseline by a factor of 1.3 in our cost measure. Last, we complement our experiments with results from a field study, comparing the success rates of our algorithms against real human drivers.
KW - Parking search
KW - probabilistic routing
KW - constrained optimization
KW - field study
Y1 - 2019
U6 - https://doi.org/10.3233/AIC-180574
SN - 0921-7126
SN - 1875-8452
VL - 32
IS - 2
SP - 113
EP - 124
PB - IOS Press
CY - Amsterdam
ER -
TY - JOUR
A1 - Friedrich, Tobias
A1 - Kötzing, Timo
A1 - Krejca, Martin Stefan
A1 - Sutton, Andrew M.
T1 - Robustness of Ant Colony Optimization to Noise
JF - Evolutionary computation
N2 - Recently, ant colony optimization (ACO) algorithms have proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses have focused on combinatorial problems such as path finding. We rigorously analyze an ACO algorithm optimizing linear pseudo- Boolean functions under additive posterior noise. We study noise distributions whose tails decay exponentially fast, including the classical case of additive Gaussian noise. Without noise, the classical (mu + 1) EA outperforms any ACO algorithm, with smaller mu being better; however, in the case of large noise, the (mu + 1) EA fails, even for high values of mu (which are known to help against small noise). In this article, we show that ACO is able to deal with arbitrarily large noise in a graceful manner; that is, as long as the evaporation factor. is small enough, dependent on the variance s2 of the noise and the dimension n of the search space, optimization will be successful. We also briefly consider the case of prior noise and prove that ACO can also efficiently optimize linear functions under this noise model.
KW - Ant colony optimization
KW - Noisy Fitness
KW - Theory
KW - Run time analysis
Y1 - 2016
U6 - https://doi.org/10.1162/EVCO_a_00178
SN - 1063-6560
SN - 1530-9304
VL - 24
SP - 237
EP - 254
PB - MIT Press
CY - Cambridge
ER -
TY - BOOK
A1 - Schwarzer, Ingo
A1 - Weiß-Saoumi, Said
A1 - Kittel, Roland
A1 - Friedrich, Tobias
A1 - Kaynak, Koraltan
A1 - Durak, Cemil
A1 - Isbarn, Andreas
A1 - Diestel, Jörg
A1 - Knittel, Jens
A1 - Franz, Marquart
A1 - Morra, Carlos
A1 - Stahnke, Susanne
A1 - Braband, Jens
A1 - Dittmann, Johannes
A1 - Griebel, Stephan
A1 - Krampf, Andreas
A1 - Link, Martin
A1 - Müller, Matthias
A1 - Radestock, Jens
A1 - Strub, Leo
A1 - Bleeke, Kai
A1 - Jehl, Leander
A1 - Kapitza, Rüdiger
A1 - Messadi, Ines
A1 - Schmidt, Stefan
A1 - Schwarz-Rüsch, Signe
A1 - Pirl, Lukas
A1 - Schmid, Robert
A1 - Friedenberger, Dirk
A1 - Beilharz, Jossekin Jakob
A1 - Boockmeyer, Arne
A1 - Polze, Andreas
A1 - Röhrig, Ralf
A1 - Schäbe, Hendrik
A1 - Thiermann, Ricky
T1 - RailChain
BT - Abschlussbericht
N2 - The RailChain project designed, implemented, and experimentally evaluated a juridical recorder that is based on a distributed consensus protocol. That juridical blockchain recorder has been realized as distributed ledger on board the advanced TrainLab (ICE-TD 605 017) of Deutsche Bahn.
For the project, a consortium consisting of DB Systel, Siemens, Siemens Mobility, the Hasso Plattner Institute for Digital Engineering, Technische Universität Braunschweig, TÜV Rheinland InterTraffic, and Spherity has been formed. These partners not only concentrated competencies in railway operation, computer science, regulation, and approval, but also combined experiences from industry, research from academia, and enthusiasm from startups.
Distributed ledger technologies (DLTs) define distributed databases and express a digital protocol for transactions between business partners without the need for a trusted intermediary. The implementation of a blockchain with real-time requirements for the local network of a railway system (e.g., interlocking or train) allows to log data in the distributed system verifiably in real-time. For this, railway-specific assumptions can be leveraged to make modifications to standard blockchains protocols.
EULYNX and OCORA (Open CCS On-board Reference Architecture) are parts of a future European reference architecture for control command and signalling (CCS, Reference CCS Architecture – RCA). Both architectural concepts outline heterogeneous IT systems with components from multiple manufacturers. Such systems introduce novel challenges for the approved and safety-relevant CCS of railways which were considered neither for road-side nor for on-board systems so far. Logging implementations, such as the common juridical recorder on vehicles, can no longer be realized as a central component of a single manufacturer. All centralized approaches are in question.
The research project RailChain is funded by the mFUND program and gives practical evidence that distributed consensus protocols are a proper means to immutably (for legal purposes) store state information of many system components from multiple manufacturers. The results of RailChain have been published, prototypically implemented, and experimentally evaluated in large-scale field tests on the advanced TrainLab. At the same time, the project showed how RailChain can be integrated into the road-side and on-board architecture given by OCORA and EULYNX.
Logged data can now be analysed sooner and also their trustworthiness is being increased. This enables, e.g., auditable predictive maintenance, because it is ensured that data is authentic and unmodified at any point in time.
N2 - Das Projekt RailChain hat einen verteilten Juridical Recorder entworfen, implementiert und experimentell evaluiert, der auf einem echtzeitfähigen verteilten Konsensprotokoll basiert. Dieser Juridical Blockchain Recorder wurde als distributed ledger an Bord des advanced TrainLabs der Deutschen Bahn (ICE-TD 605 017) umgesetzt.
Für das Projekt hat sich ein Konsortium aus DB Systel, Siemens, Siemens Mobility, dem Hasso-Plattner-Institut für Digital Engineering, der Technischen Universität Braunschweig, sowie TÜV Rheinland InterTraffic und Spherity formiert und dabei Kompetenzen aus den Bereichen Bahnbetrieb, Informatik und Zulassungswesen gebündelt. Die Partner kombinieren Erfahrungen aus der Industrie und die akademische Forschung mit der Aufbruchstimmung aus dem Start-Up-Umfeld.
Distributed-Ledger-Technologien (DLTs) definieren verteilte Datenbanken und stellen ein digitales Protokoll für Transaktionen zwischen Geschäftspartnern dar, ohne dass ein Mittelsmann beteiligt sein müsste. Die Implementierung einer Blockchain mit Echtzeitanforderungen für das lokale Netzwerk einer Eisenbahnanlage (z. B. Stellwerk oder Zug) erlaubt es, die im verteilten System entstehenden Daten nachweislich in Echtzeit zu protokollieren. Dabei können eisenbahnspezifische Randbedingungen ausgenutzt werden, um Standard-Blockchain-Protokolle anzupassen.
EULYNX und OCORA (Open CCS On-board Reference Architecture) sind Bestandteile einer zukünftigen europäischen Referenzarchitektur für das Leit- und Sicherungssystem (Reference CCS Architecture – RCA, Control Command and Signalling – CCS). Beide Architekturkonzepte skizzieren herstellerübergreifende, komponentenbasierende heterogene IT-Systeme. Solche Systeme bergen neue Herausforderungen, die bislang im Kontext der zugelassenen, sicherheitsrelevanten Leit- und Sicherungstechnik der Bahn weder strecken- noch fahrzeugseitig adressiert werden mussten. Logbuch-Implementierungen, wie der gängige Juridical Recorder auf Fahrzeugen, können nun nicht mehr als zentrale Systemkomponente eines einzelnen Herstellers umgesetzt werden. Alle zentralisierten Lösungsansätze sind in Frage gestellt.
Das mFUND-geförderte Forschungsprojekt erbringt den praktischen Nachweis, dass Zustandsinformationen über eine Vielzahl von Systemkomponenten herstellerübergreifend und gerichtsfest mittels verteilten Konsensprotokollen gespeichert werden können. Ergebnisse von RailChain wurden publiziert, prototypisch implementiert und in großen Feldtests auf dem advanced TrainLab experimentell evaluiert. Gleichzeitig wurde aufgezeigt, wie sich RailChain in den mit OCORA und EULYNX vorgegebenen fahrzeug- und streckenseitigen Architekturentwurf integrieren lässt.
Daten können dadurch zeitnaher ausgewertet werden und gleichzeitig wird ihre Vertrauenswürdigkeit erhöht. Dies ermöglicht u. a. nachvollziehbare zustandsorientierte Wartung, denn es kann jederzeit sichergestellt werden, dass die Daten authentisch sind und auch nicht verändert wurden.
T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 152
KW - Distributed-Ledger-Technologie (DLT)
KW - juridical recording
KW - Konsensprotokolle
KW - consensus protocols
KW - Digitalisierung
KW - digitalization
KW - Bahnwesen
KW - railways
KW - Blockchain
KW - asset management
KW - selbstbestimmte Identitäten
KW - self-sovereign identity
KW - dezentrale Identitäten
KW - decentral identities
KW - überprüfbare Nachweise
KW - verifiable credentials
KW - Echtzeit
KW - real-time
KW - Standardisierung
KW - standardization
KW - Verlässlichkeit
KW - dependability
KW - Fehlertoleranz
KW - fault tolerance
Y1 - 2023
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-577409
SN - 978-3-86956-550-7
SN - 1613-5652
SN - 2191-1665
IS - 152
PB - Universitätsverlag Potsdam
CY - Potsdam
ER -
TY - BOOK
A1 - Meinel, Christoph
A1 - Döllner, Jürgen Roland Friedrich
A1 - Weske, Mathias
A1 - Polze, Andreas
A1 - Hirschfeld, Robert
A1 - Naumann, Felix
A1 - Giese, Holger
A1 - Baudisch, Patrick
A1 - Friedrich, Tobias
A1 - Böttinger, Erwin
A1 - Lippert, Christoph
A1 - Dörr, Christian
A1 - Lehmann, Anja
A1 - Renard, Bernhard
A1 - Rabl, Tilmann
A1 - Uebernickel, Falk
A1 - Arnrich, Bert
A1 - Hölzle, Katharina
T1 - Proceedings of the HPI Research School on Service-oriented Systems Engineering 2020 Fall Retreat
N2 - Design and Implementation of service-oriented architectures imposes a huge number of research questions from the fields of software engineering, system analysis and modeling, adaptability, and application integration. Component orientation and web services are two approaches for design and realization of complex web-based system. Both approaches allow for dynamic application adaptation as well as integration of enterprise application.
Service-Oriented Systems Engineering represents a symbiosis of best practices in object-orientation, component-based development, distributed computing, and business process management. It provides integration of business and IT concerns.
The annual Ph.D. Retreat of the Research School provides each member the opportunity to present his/her current state of their research and to give an outline of a prospective Ph.D. thesis. Due to the interdisciplinary structure of the research school, this technical report covers a wide range of topics. These include but are not limited to: Human Computer Interaction and Computer Vision as Service; Service-oriented Geovisualization Systems; Algorithm Engineering for Service-oriented Systems; Modeling and Verification of Self-adaptive Service-oriented Systems; Tools and Methods for Software Engineering in Service-oriented Systems; Security Engineering of Service-based IT Systems; Service-oriented Information Systems; Evolutionary Transition of Enterprise Applications to Service Orientation; Operating System Abstractions for Service-oriented Computing; and Services Specification, Composition, and Enactment.
N2 - Der Entwurf und die Realisierung dienstbasierender Architekturen wirft eine Vielzahl von Forschungsfragestellungen aus den Gebieten der Softwaretechnik, der Systemmodellierung und -analyse, sowie der Adaptierbarkeit und Integration von Applikationen auf. Komponentenorientierung und WebServices sind zwei Ansätze für den effizienten Entwurf und die Realisierung komplexer Web-basierender Systeme. Sie ermöglichen die Reaktion auf wechselnde Anforderungen ebenso, wie die Integration großer komplexer Softwaresysteme.
"Service-Oriented Systems Engineering" repräsentiert die Symbiose bewährter Praktiken aus den Gebieten der Objektorientierung, der Komponentenprogrammierung, des verteilten Rechnen sowie der Geschäftsprozesse und berücksichtigt auch die Integration von Geschäftsanliegen und Informationstechnologien.
Die Klausurtagung des Forschungskollegs "Service-oriented Systems Engineering" findet einmal jährlich statt und bietet allen Kollegiaten die Möglichkeit den Stand ihrer aktuellen Forschung darzulegen. Bedingt durch die Querschnittstruktur des Kollegs deckt dieser Bericht ein weites Spektrum aktueller Forschungsthemen ab. Dazu zählen unter anderem Human Computer Interaction and Computer Vision as Service; Service-oriented Geovisualization Systems; Algorithm Engineering for Service-oriented Systems; Modeling and Verification of Self-adaptive Service-oriented Systems; Tools and Methods for Software Engineering in Service-oriented Systems; Security Engineering of Service-based IT Systems; Service-oriented Information Systems; Evolutionary Transition of Enterprise Applications to Service Orientation; Operating System Abstractions for Service-oriented Computing; sowie Services Specification, Composition, and Enactment.
T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 138
KW - Hasso Plattner Institute
KW - research school
KW - Ph.D. retreat
KW - service-oriented systems engineering
KW - Hasso-Plattner-Institut
KW - Forschungskolleg
KW - Klausurtagung
KW - Service-oriented Systems Engineering
Y1 - 2021
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-504132
SN - 978-3-86956-513-2
SN - 1613-5652
SN - 2191-1665
IS - 138
PB - Universitätsverlag Potsdam
CY - Potsdam
ER -
TY - JOUR
A1 - Roostapour, Vahid
A1 - Neumann, Aneta
A1 - Neumann, Frank
A1 - Friedrich, Tobias
T1 - Pareto optimization for subset selection with dynamic cost constraints
JF - Artificial intelligence
N2 - We consider the subset selection problem for function f with constraint bound B that changes over time. Within the area of submodular optimization, various greedy approaches are commonly used. For dynamic environments we observe that the adaptive variants of these greedy approaches are not able to maintain their approximation quality. Investigating the recently introduced POMC Pareto optimization approach, we show that this algorithm efficiently computes a phi=(alpha(f)/2)(1 - 1/e(alpha)f)-approximation, where alpha(f) is the submodularity ratio of f, for each possible constraint bound b <= B. Furthermore, we show that POMC is able to adapt its set of solutions quickly in the case that B increases. Our experimental investigations for the influence maximization in social networks show the advantage of POMC over generalized greedy algorithms. We also consider EAMC, a new evolutionary algorithm with polynomial expected time guarantee to maintain phi approximation ratio, and NSGA-II with two different population sizes as advanced multi-objective optimization algorithm, to demonstrate their challenges in optimizing the maximum coverage problem. Our empirical analysis shows that, within the same number of evaluations, POMC is able to perform as good as NSGA-II under linear constraint, while EAMC performs significantly worse than all considered algorithms in most cases.
KW - Subset selection
KW - Submodular function
KW - Multi-objective optimization
KW - Runtime analysis
Y1 - 2022
U6 - https://doi.org/10.1016/j.artint.2021.103597
SN - 0004-3702
SN - 1872-7921
VL - 302
PB - Elsevier
CY - Amsterdam
ER -
TY - GEN
A1 - Blaesius, Thomas
A1 - Eube, Jan
A1 - Feldtkeller, Thomas
A1 - Friedrich, Tobias
A1 - Krejca, Martin Stefan
A1 - Lagodzinski, Julius Albert Gregor
A1 - Rothenberger, Ralf
A1 - Severin, Julius
A1 - Sommer, Fabian
A1 - Trautmann, Justin
T1 - Memory-restricted Routing With Tiled Map Data
T2 - 2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC)
N2 - Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A*.
Y1 - 2018
SN - 978-1-5386-6650-0
U6 - https://doi.org/10.1109/SMC.2018.00567
SN - 1062-922X
SP - 3347
EP - 3354
PB - IEEE
CY - New York
ER -
TY - JOUR
A1 - Cohen, Sarel
A1 - Hershcovitch, Moshik
A1 - Taraz, Martin
A1 - Kissig, Otto
A1 - Issac, Davis
A1 - Wood, Andrew
A1 - Waddington, Daniel
A1 - Chin, Peter
A1 - Friedrich, Tobias
T1 - Improved and optimized drug repurposing for the SARS-CoV-2 pandemic
JF - PLoS one
N2 - The active global SARS-CoV-2 pandemic caused more than 426 million cases and 5.8 million deaths worldwide. The development of completely new drugs for such a novel disease is a challenging, time intensive process. Despite researchers around the world working on this task, no effective treatments have been developed yet. This emphasizes the importance of drug repurposing, where treatments are found among existing drugs that are meant for different diseases. A common approach to this is based on knowledge graphs, that condense relationships between entities like drugs, diseases and genes. Graph neural networks (GNNs) can then be used for the task at hand by predicting links in such knowledge graphs. Expanding on state-of-the-art GNN research, Doshi et al. recently developed the Dr-COVID model. We further extend their work using additional output interpretation strategies. The best aggregation strategy derives a top-100 ranking of 8,070 candidate drugs, 32 of which are currently being tested in COVID-19-related clinical trials. Moreover, we present an alternative application for the model, the generation of additional candidates based on a given pre-selection of drug candidates using collaborative filtering. In addition, we improved the implementation of the Dr-COVID model by significantly shortening the inference and pre-processing time by exploiting data-parallelism. As drug repurposing is a task that requires high computation and memory resources, we further accelerate the post-processing phase using a new emerging hardware-we propose a new approach to leverage the use of high-capacity Non-Volatile Memory for aggregate drug ranking.
Y1 - 2023
U6 - https://doi.org/10.1371/journal.pone.0266572
SN - 1932-6203
VL - 18
IS - 3
PB - PLoS
CY - San Fransisco
ER -
TY - BOOK
A1 - Kuban, Robert
A1 - Rotta, Randolf
A1 - Nolte, Jörg
A1 - Chromik, Jonas
A1 - Beilharz, Jossekin Jakob
A1 - Pirl, Lukas
A1 - Friedrich, Tobias
A1 - Lenzner, Pascal
A1 - Weyand, Christopher
A1 - Juiz, Carlos
A1 - Bermejo, Belen
A1 - Sauer, Joao
A1 - Coelh, Leandro dos Santos
A1 - Najafi, Pejman
A1 - Pünter, Wenzel
A1 - Cheng, Feng
A1 - Meinel, Christoph
A1 - Sidorova, Julia
A1 - Lundberg, Lars
A1 - Vogel, Thomas
A1 - Tran, Chinh
A1 - Moser, Irene
A1 - Grunske, Lars
A1 - Elsaid, Mohamed Esameldin Mohamed
A1 - Abbas, Hazem M.
A1 - Rula, Anisa
A1 - Sejdiu, Gezim
A1 - Maurino, Andrea
A1 - Schmidt, Christopher
A1 - Hügle, Johannes
A1 - Uflacker, Matthias
A1 - Nozza, Debora
A1 - Messina, Enza
A1 - Hoorn, André van
A1 - Frank, Markus
A1 - Schulz, Henning
A1 - Alhosseini Almodarresi Yasin, Seyed Ali
A1 - Nowicki, Marek
A1 - Muite, Benson K.
A1 - Boysan, Mehmet Can
A1 - Bianchi, Federico
A1 - Cremaschi, Marco
A1 - Moussa, Rim
A1 - Abdel-Karim, Benjamin M.
A1 - Pfeuffer, Nicolas
A1 - Hinz, Oliver
A1 - Plauth, Max
A1 - Polze, Andreas
A1 - Huo, Da
A1 - Melo, Gerard de
A1 - Mendes Soares, Fábio
A1 - Oliveira, Roberto Célio Limão de
A1 - Benson, Lawrence
A1 - Paul, Fabian
A1 - Werling, Christian
A1 - Windheuser, Fabian
A1 - Stojanovic, Dragan
A1 - Djordjevic, Igor
A1 - Stojanovic, Natalija
A1 - Stojnev Ilic, Aleksandra
A1 - Weidmann, Vera
A1 - Lowitzki, Leon
A1 - Wagner, Markus
A1 - Ifa, Abdessatar Ben
A1 - Arlos, Patrik
A1 - Megia, Ana
A1 - Vendrell, Joan
A1 - Pfitzner, Bjarne
A1 - Redondo, Alberto
A1 - Ríos Insua, David
A1 - Albert, Justin Amadeus
A1 - Zhou, Lin
A1 - Arnrich, Bert
A1 - Szabó, Ildikó
A1 - Fodor, Szabina
A1 - Ternai, Katalin
A1 - Bhowmik, Rajarshi
A1 - Campero Durand, Gabriel
A1 - Shevchenko, Pavlo
A1 - Malysheva, Milena
A1 - Prymak, Ivan
A1 - Saake, Gunter
ED - Meinel, Christoph
ED - Polze, Andreas
ED - Beins, Karsten
ED - Strotmann, Rolf
ED - Seibold, Ulrich
ED - Rödszus, Kurt
ED - Müller, Jürgen
T1 - HPI Future SOC Lab – Proceedings 2019
N2 - The “HPI Future SOC Lab” is a cooperation of the Hasso Plattner Institute (HPI) and industry partners. Its mission is to enable and promote exchange and interaction between the research community and the industry partners.
The HPI Future SOC Lab provides researchers with free of charge access to a complete infrastructure of state of the art hard and software. This infrastructure includes components, which might be too expensive for an ordinary research environment, such as servers with up to 64 cores and 2 TB main memory. The offerings address researchers particularly from but not limited to the areas of computer science and business information systems. Main areas of research include cloud computing, parallelization, and In-Memory technologies.
This technical report presents results of research projects executed in 2019. Selected projects have presented their results on April 9th and November 12th 2019 at the Future SOC Lab Day events.
N2 - Das Future SOC Lab am HPI ist eine Kooperation des Hasso-Plattner-Instituts mit verschiedenen Industriepartnern. Seine Aufgabe ist die Ermöglichung und Förderung des Austausches zwischen Forschungsgemeinschaft und Industrie.
Am Lab wird interessierten Wissenschaftlern eine Infrastruktur von neuester Hard- und Software kostenfrei für Forschungszwecke zur Verfügung gestellt. Dazu zählen teilweise noch nicht am Markt verfügbare Technologien, die im normalen Hochschulbereich in der Regel nicht zu finanzieren wären, bspw. Server mit bis zu 64 Cores und 2 TB Hauptspeicher. Diese Angebote richten sich insbesondere an Wissenschaftler in den Gebieten Informatik und Wirtschaftsinformatik. Einige der Schwerpunkte sind Cloud Computing, Parallelisierung und In-Memory Technologien.
In diesem Technischen Bericht werden die Ergebnisse der Forschungsprojekte des Jahres 2019 vorgestellt. Ausgewählte Projekte stellten ihre Ergebnisse am 09. April und 12. November 2019 im Rahmen des Future SOC Lab Tags vor.
T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 158
KW - Future SOC Lab
KW - research projects
KW - multicore architectures
KW - in-memory technology
KW - cloud computing
KW - machine learning
KW - artifical intelligence
KW - Future SOC Lab
KW - Forschungsprojekte
KW - Multicore Architekturen
KW - In-Memory Technologie
KW - Cloud Computing
KW - maschinelles Lernen
KW - künstliche Intelligenz
Y1 - 2024
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-597915
SN - 978-3-86956-564-4
SN - 1613-5652
SN - 2191-1665
IS - 158
PB - Universitätsverlag Potsdam
CY - Potsdam
ER -
TY - BOOK
A1 - Rana, Kaushik
A1 - Mohapatra, Durga Prasad
A1 - Sidorova, Julia
A1 - Lundberg, Lars
A1 - Sköld, Lars
A1 - Lopes Grim, Luís Fernando
A1 - Sampaio Gradvohl, André Leon
A1 - Cremerius, Jonas
A1 - Siegert, Simon
A1 - Weltzien, Anton von
A1 - Baldi, Annika
A1 - Klessascheck, Finn
A1 - Kalancha, Svitlana
A1 - Lichtenstein, Tom
A1 - Shaabani, Nuhad
A1 - Meinel, Christoph
A1 - Friedrich, Tobias
A1 - Lenzner, Pascal
A1 - Schumann, David
A1 - Wiese, Ingmar
A1 - Sarna, Nicole
A1 - Wiese, Lena
A1 - Tashkandi, Araek Sami
A1 - van der Walt, Estée
A1 - Eloff, Jan H. P.
A1 - Schmidt, Christopher
A1 - Hügle, Johannes
A1 - Horschig, Siegfried
A1 - Uflacker, Matthias
A1 - Najafi, Pejman
A1 - Sapegin, Andrey
A1 - Cheng, Feng
A1 - Stojanovic, Dragan
A1 - Stojnev Ilić, Aleksandra
A1 - Djordjevic, Igor
A1 - Stojanovic, Natalija
A1 - Predic, Bratislav
A1 - González-Jiménez, Mario
A1 - de Lara, Juan
A1 - Mischkewitz, Sven
A1 - Kainz, Bernhard
A1 - van Hoorn, André
A1 - Ferme, Vincenzo
A1 - Schulz, Henning
A1 - Knigge, Marlene
A1 - Hecht, Sonja
A1 - Prifti, Loina
A1 - Krcmar, Helmut
A1 - Fabian, Benjamin
A1 - Ermakova, Tatiana
A1 - Kelkel, Stefan
A1 - Baumann, Annika
A1 - Morgenstern, Laura
A1 - Plauth, Max
A1 - Eberhard, Felix
A1 - Wolff, Felix
A1 - Polze, Andreas
A1 - Cech, Tim
A1 - Danz, Noel
A1 - Noack, Nele Sina
A1 - Pirl, Lukas
A1 - Beilharz, Jossekin Jakob
A1 - De Oliveira, Roberto C. L.
A1 - Soares, Fábio Mendes
A1 - Juiz, Carlos
A1 - Bermejo, Belen
A1 - Mühle, Alexander
A1 - Grüner, Andreas
A1 - Saxena, Vageesh
A1 - Gayvoronskaya, Tatiana
A1 - Weyand, Christopher
A1 - Krause, Mirko
A1 - Frank, Markus
A1 - Bischoff, Sebastian
A1 - Behrens, Freya
A1 - Rückin, Julius
A1 - Ziegler, Adrian
A1 - Vogel, Thomas
A1 - Tran, Chinh
A1 - Moser, Irene
A1 - Grunske, Lars
A1 - Szárnyas, Gábor
A1 - Marton, József
A1 - Maginecz, János
A1 - Varró, Dániel
A1 - Antal, János Benjamin
ED - Meinel, Christoph
ED - Polze, Andreas
ED - Beins, Karsten
ED - Strotmann, Rolf
ED - Seibold, Ulrich
ED - Rödszus, Kurt
ED - Müller, Jürgen
T1 - HPI Future SOC Lab – Proceedings 2018
N2 - The “HPI Future SOC Lab” is a cooperation of the Hasso Plattner Institute (HPI) and industry partners. Its mission is to enable and promote exchange and interaction between the research community and the industry partners.
The HPI Future SOC Lab provides researchers with free of charge access to a complete infrastructure of state of the art hard and software. This infrastructure includes components, which might be too expensive for an ordinary research environment, such as servers with up to 64 cores and 2 TB main memory. The offerings address researchers particularly from but not limited to the areas of computer science and business information systems. Main areas of research include cloud computing, parallelization, and In-Memory technologies.
This technical report presents results of research projects executed in 2018. Selected projects have presented their results on April 17th and November 14th 2017 at the Future SOC Lab Day events.
N2 - Das Future SOC Lab am HPI ist eine Kooperation des Hasso-Plattner-Instituts mit verschiedenen Industriepartnern. Seine Aufgabe ist die Ermöglichung und Förderung des Austausches zwischen Forschungsgemeinschaft und Industrie.
Am Lab wird interessierten Wissenschaftler:innen eine Infrastruktur von neuester Hard- und Software kostenfrei für Forschungszwecke zur Verfügung gestellt. Dazu zählen Systeme, die im normalen Hochschulbereich in der Regel nicht zu finanzieren wären, bspw. Server mit bis zu 64 Cores und 2 TB Hauptspeicher. Diese Angebote richten sich insbesondere an Wissenschaftler:innen in den Gebieten Informatik und Wirtschaftsinformatik. Einige der Schwerpunkte sind Cloud Computing, Parallelisierung und In-Memory Technologien.
In diesem Technischen Bericht werden die Ergebnisse der Forschungsprojekte des Jahres 2018 vorgestellt. Ausgewählte Projekte stellten ihre Ergebnisse am 17. April und 14. November 2018 im Rahmen des Future SOC Lab Tags vor.
T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 151
KW - Future SOC Lab
KW - research projects
KW - multicore architectures
KW - in-memory technology
KW - cloud computing
KW - machine learning
KW - artifical intelligence
KW - Future SOC Lab
KW - Forschungsprojekte
KW - Multicore Architekturen
KW - In-Memory Technologie
KW - Cloud Computing
KW - maschinelles Lernen
KW - künstliche Intelligenz
Y1 - 2022
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-563712
SN - 978-3-86956-547-7
SN - 1613-5652
SN - 2191-1665
IS - 151
PB - Universitätsverlag Potsdam
CY - Potsdam
ER -
TY - BOOK
A1 - Zhang, Shuhao
A1 - Plauth, Max
A1 - Eberhardt, Felix
A1 - Polze, Andreas
A1 - Lehmann, Jens
A1 - Sejdiu, Gezim
A1 - Jabeen, Hajira
A1 - Servadei, Lorenzo
A1 - Möstl, Christian
A1 - Bär, Florian
A1 - Netzeband, André
A1 - Schmidt, Rainer
A1 - Knigge, Marlene
A1 - Hecht, Sonja
A1 - Prifti, Loina
A1 - Krcmar, Helmut
A1 - Sapegin, Andrey
A1 - Jaeger, David
A1 - Cheng, Feng
A1 - Meinel, Christoph
A1 - Friedrich, Tobias
A1 - Rothenberger, Ralf
A1 - Sutton, Andrew M.
A1 - Sidorova, Julia A.
A1 - Lundberg, Lars
A1 - Rosander, Oliver
A1 - Sköld, Lars
A1 - Di Varano, Igor
A1 - van der Walt, Estée
A1 - Eloff, Jan H. P.
A1 - Fabian, Benjamin
A1 - Baumann, Annika
A1 - Ermakova, Tatiana
A1 - Kelkel, Stefan
A1 - Choudhary, Yash
A1 - Cooray, Thilini
A1 - Rodríguez, Jorge
A1 - Medina-Pérez, Miguel Angel
A1 - Trejo, Luis A.
A1 - Barrera-Animas, Ari Yair
A1 - Monroy-Borja, Raúl
A1 - López-Cuevas, Armando
A1 - Ramírez-Márquez, José Emmanuel
A1 - Grohmann, Maria
A1 - Niederleithinger, Ernst
A1 - Podapati, Sasidhar
A1 - Schmidt, Christopher
A1 - Huegle, Johannes
A1 - de Oliveira, Roberto C. L.
A1 - Soares, Fábio Mendes
A1 - van Hoorn, André
A1 - Neumer, Tamas
A1 - Willnecker, Felix
A1 - Wilhelm, Mathias
A1 - Kuster, Bernhard
ED - Meinel, Christoph
ED - Polze, Andreas
ED - Beins, Karsten
ED - Strotmann, Rolf
ED - Seibold, Ulrich
ED - Rödszus, Kurt
ED - Müller, Jürgen
T1 - HPI Future SOC Lab – Proceedings 2017
T1 - HPI Future SOC Lab – Proceedings 2017
N2 - The “HPI Future SOC Lab” is a cooperation of the Hasso Plattner Institute (HPI) and industry partners. Its mission is to enable and promote exchange and interaction between the research community and the industry partners.
The HPI Future SOC Lab provides researchers with free of charge access to a complete infrastructure of state of the art hard and software. This infrastructure includes components, which might be too expensive for an ordinary research environment, such as servers with up to 64 cores and 2 TB main memory. The offerings address researchers particularly from but not limited to the areas of computer science and business information systems. Main areas of research include cloud computing, parallelization, and In-Memory technologies.
This technical report presents results of research projects executed in 2017. Selected projects have presented their results on April 25th and November 15th 2017 at the Future SOC Lab Day events.
N2 - Das Future SOC Lab am HPI ist eine Kooperation des Hasso-Plattner-Instituts mit verschiedenen Industriepartnern. Seine Aufgabe ist die Ermöglichung und Förderung des Austausches zwischen Forschungsgemeinschaft und Industrie.
Am Lab wird interessierten Wissenschaftlern eine Infrastruktur von neuester Hard- und Software kostenfrei für Forschungszwecke zur Verfügung gestellt. Dazu zählen teilweise noch nicht am Markt verfügbare Technologien, die im normalen Hochschulbereich in der Regel nicht zu finanzieren wären, bspw. Server mit bis zu 64 Cores und 2 TB Hauptspeicher. Diese Angebote richten sich insbesondere an Wissenschaftler in den Gebieten Informatik und Wirtschaftsinformatik. Einige der Schwerpunkte sind Cloud Computing, Parallelisierung und In-Memory Technologien.
In diesem Technischen Bericht werden die Ergebnisse der Forschungsprojekte des Jahres 2017 vorgestellt. Ausgewählte Projekte stellten ihre Ergebnisse am 25. April und 15. November 2017 im Rahmen der Future SOC Lab Tag Veranstaltungen vor.
T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 130
KW - Future SOC Lab
KW - research projects
KW - multicore architectures
KW - In-Memory technology
KW - cloud computing
KW - machine learning
KW - artifical intelligence
KW - Future SOC Lab
KW - Forschungsprojekte
KW - Multicore Architekturen
KW - In-Memory Technologie
KW - Cloud Computing
KW - maschinelles Lernen
KW - Künstliche Intelligenz
Y1 - 2020
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-433100
SN - 978-3-86956-475-3
SN - 1613-5652
SN - 2191-1665
IS - 130
PB - Universitätsverlag Potsdam
CY - Potsdam
ER -
TY - BOOK
A1 - Juiz, Carlos
A1 - Bermejo, Belen
A1 - Calle, Alejandro
A1 - Sidorova, Julia
A1 - Lundberg, Lars
A1 - Weidmann, Vera
A1 - Lowitzki, Leon
A1 - Mirtschin, Marvin
A1 - Hoorn, André van
A1 - Frank, Markus
A1 - Schulz, Henning
A1 - Stojanovic, Dragan
A1 - Stojanovic, Natalija
A1 - Stojnev Ilic, Aleksandra
A1 - Friedrich, Tobias
A1 - Lenzner, Pascal
A1 - Weyand, Christopher
A1 - Wagner, Markus
A1 - Plauth, Max
A1 - Polze, Andreas
A1 - Nowicki, Marek
A1 - Seth, Sugandh
A1 - Kaur Chahal, Kuljit
A1 - Singh, Gurwinder
A1 - Speth, Sandro
A1 - Janes, Andrea
A1 - Camilli, Matteo
A1 - Ziegler, Erik
A1 - Schmidberger, Marcel
A1 - Pörschke, Mats
A1 - Bartz, Christian
A1 - Lorenz, Martin
A1 - Meinel, Christoph
A1 - Beilich, Robert
A1 - Bertazioli, Dario
A1 - Carlomagno, Cristiano
A1 - Bedoni, Marzia
A1 - Messina, Vincenzina
ED - Meinel, Christoph
ED - Polze, Andreas
ED - Beins, Karsten
ED - Strotmann, Rolf
ED - Seibold, Ulrich
ED - Rödszus, Kurt
ED - Müller, Jürgen
ED - Sommer, Jürgen
T1 - HPI Future SOC Lab
BT - Proceedings 2020
T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam
N2 - The “HPI Future SOC Lab” is a cooperation of the Hasso Plattner Institute (HPI) and industry partners. Its mission is to enable and promote exchange and interaction between the research community and the industry partners.
The HPI Future SOC Lab provides researchers with free of charge access to a complete infrastructure of state of the art hard and software. This infrastructure includes components, which might be too expensive for an ordinary research environment, such as servers with up to 64 cores and 2 TB main memory. The offerings address researchers particularly from but not limited to the areas of computer science and business information systems. Main areas of research include cloud computing, parallelization, and In-Memory technologies.
This technical report presents results of research projects executed in 2020. Selected projects have presented their results on April 21st and November 10th 2020 at the Future SOC Lab Day events.
N2 - Das Future SOC Lab am HPI ist eine Kooperation des Hasso-Plattner-Instituts mit verschiedenen Industriepartnern. Seine Aufgabe ist die Ermöglichung und Förderung des Austausches zwischen Forschungsgemeinschaft und Industrie.
Am Lab wird interessierten Wissenschaftlern eine Infrastruktur von neuester Hard- und Software kostenfrei für Forschungszwecke zur Verfügung gestellt. Dazu zählen teilweise noch nicht am Markt verfügbare Technologien, die im normalen Hochschulbereich in der Regel nicht zu finanzieren wären, bspw. Server mit bis zu 64 Cores und 2 TB Hauptspeicher. Diese Angebote richten sich insbesondere an Wissenschaftler in den Gebieten Informatik und Wirtschaftsinformatik. Einige der Schwerpunkte sind Cloud Computing, Parallelisierung und In-Memory Technologien.
In diesem Technischen Bericht werden die Ergebnisse der Forschungsprojekte des Jahres 2020 vorgestellt. Ausgewählte Projekte stellten ihre Ergebnisse am 21. April und 10. November 2020 im Rahmen des Future SOC Lab Tags vor.
T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 159
KW - Future SOC Lab
KW - research projects
KW - multicore architectures
KW - in-memory technology
KW - cloud computing
KW - machine learning
KW - artifical intelligence
KW - Future SOC Lab
KW - Forschungsprojekte
KW - Multicore Architekturen
KW - In-Memory Technologie
KW - Cloud Computing
KW - maschinelles Lernen
KW - künstliche Intelligenz
Y1 - 2024
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-598014
SN - 978-3-86956-565-1
SN - 1613-5652
SN - 2191-1665
IS - 159
PB - Universitätsverlag Potsdam
CY - Potsdam
ER -
TY - JOUR
A1 - Birnick, Johann
A1 - Bläsius, Thomas
A1 - Friedrich, Tobias
A1 - Naumann, Felix
A1 - Papenbrock, Thorsten
A1 - Schirneck, Friedrich Martin
T1 - Hitting set enumeration with partial information for unique column combination discovery
JF - Proceedings of the VLDB Endowment
N2 - Unique column combinations (UCCs) are a fundamental concept in relational databases. They identify entities in the data and support various data management activities. Still, UCCs are usually not explicitly defined and need to be discovered. State-of-the-art data profiling algorithms are able to efficiently discover UCCs in moderately sized datasets, but they tend to fail on large and, in particular, on wide datasets due to run time and memory limitations.
In this paper, we introduce HPIValid, a novel UCC discovery algorithm that implements a faster and more resource-saving search strategy. HPIValid models the metadata discovery as a hitting set enumeration problem in hypergraphs. In this way, it combines efficient discovery techniques from data profiling research with the most recent theoretical insights into enumeration algorithms. Our evaluation shows that HPIValid is not only orders of magnitude faster than related work, it also has a much smaller memory footprint.
Y1 - 2020
U6 - https://doi.org/10.14778/3407790.3407824
SN - 2150-8097
VL - 13
IS - 11
SP - 2270
EP - 2283
PB - Association for Computing Machinery
CY - [New York, NY]
ER -
TY - JOUR
A1 - Chauhan, Ankit
A1 - Friedrich, Tobias
A1 - Rothenberger, Ralf
T1 - Greed is good for deterministic scale-free networks
JF - Algorithmica : an international journal in computer science
N2 - Large real-world networks typically follow a power-law degree distribution. To study such networks, numerous random graph models have been proposed. However, real-world networks are not drawn at random. Therefore, Brach et al. (27th symposium on discrete algorithms (SODA), pp 1306-1325, 2016) introduced two natural deterministic conditions: (1) a power-law upper bound on the degree distribution (PLB-U) and (2) power-law neighborhoods, that is, the degree distribution of neighbors of each vertex is also upper bounded by a power law (PLB-N). They showed that many real-world networks satisfy both properties and exploit them to design faster algorithms for a number of classical graph problems. We complement their work by showing that some well-studied random graph models exhibit both of the mentioned PLB properties. PLB-U and PLB-N hold with high probability for Chung-Lu Random Graphs and Geometric Inhomogeneous Random Graphs and almost surely for Hyperbolic Random Graphs. As a consequence, all results of Brach et al. also hold with high probability or almost surely for those random graph classes. In the second part we study three classical NP-hard optimization problems on PLB networks. It is known that on general graphs with maximum degree Delta, a greedy algorithm, which chooses nodes in the order of their degree, only achieves a Omega (ln Delta)-approximation forMinimum Vertex Cover and Minimum Dominating Set, and a Omega(Delta)-approximation forMaximum Independent Set. We prove that the PLB-U property with beta>2 suffices for the greedy approach to achieve a constant-factor approximation for all three problems. We also show that these problems are APX-hard even if PLB-U, PLB-N, and an additional power-law lower bound on the degree distribution hold. Hence, a PTAS cannot be expected unless P = NP. Furthermore, we prove that all three problems are in MAX SNP if the PLB-U property holds.
KW - random graphs
KW - deterministic properties
KW - power-law
KW - approximation
KW - APX-hardness
Y1 - 2020
U6 - https://doi.org/10.1007/s00453-020-00729-z
SN - 0178-4617
SN - 1432-0541
VL - 82
IS - 11
SP - 3338
EP - 3389
PB - Springer
CY - New York
ER -
TY - GEN
A1 - Bilo, Davide
A1 - Friedrich, Tobias
A1 - Lenzner, Pascal
A1 - Melnichenko, Anna
T1 - Geometric Network Creation Games
T2 - SPAA '19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures
N2 - Network Creation Games are a well-known approach for explaining and analyzing the structure, quality and dynamics of real-world networks like the Internet and other infrastructure networks which evolved via the interaction of selfish agents without a central authority. In these games selfish agents which correspond to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games has only considered the creation of networks with unit-weight edges. In practice, e.g. when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depends on the distance between the involved nodes and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by Fabrikant et al. [PODC'03] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state-of-the-art for the unit-weight version, where the Price of Anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight non-constant bound on the Price of Anarchy for the metric version and a slightly weaker upper bound for the non-metric case. Moreover, we analyze the existence of equilibria, the computational hardness and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of a variant of the classical Network Design Problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.
KW - Network creation games
KW - edge-weighted networks
KW - price of anarchy
KW - Nash equilibrium
KW - game dynamics
KW - computational hardness
Y1 - 2019
SN - 978-1-4503-6184-2
U6 - https://doi.org/10.1145/3323165.3323199
SP - 323
EP - 332
PB - Association for Computing Machinery
CY - New York
ER -
TY - GEN
A1 - Friedrich, Tobias
T1 - From graph theory to network science
BT - the natural emergence of hyperbolicity (Tutorial)
T2 - 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
N2 - Network science is driven by the question which properties large real-world networks have and how we can exploit them algorithmically. In the past few years, hyperbolic graphs have emerged as a very promising model for scale-free networks. The connection between hyperbolic geometry and complex networks gives insights in both directions: (1) Hyperbolic geometry forms the basis of a natural and explanatory model for real-world networks. Hyperbolic random graphs are obtained by choosing random points in the hyperbolic plane and connecting pairs of points that are geometrically close. The resulting networks share many structural properties for example with online social networks like Facebook or Twitter. They are thus well suited for algorithmic analyses in a more realistic setting. (2) Starting with a real-world network, hyperbolic geometry is well-suited for metric embeddings. The vertices of a network can be mapped to points in this geometry, such that geometric distances are similar to graph distances. Such embeddings have a variety of algorithmic applications ranging from approximations based on efficient geometric algorithms to greedy routing solely using hyperbolic coordinates for navigation decisions.
KW - Graph Theory
KW - Graph Algorithms
KW - Network Science
KW - Hyperbolic Geometry
Y1 - 2019
SN - 978-3-95977-100-9
U6 - https://doi.org/10.4230/LIPIcs.STACS.2019.5
VL - 126
PB - Schloss Dagstuhl-Leibniz-Zentrum für Informatik
CY - Dragstuhl
ER -
TY - JOUR
A1 - Quinzan, Francesco
A1 - Göbel, Andreas
A1 - Wagner, Markus
A1 - Friedrich, Tobias
T1 - Evolutionary algorithms and submodular functions
BT - benefits of heavy-tailed mutations
JF - Natural computing : an innovative journal bridging biosciences and computer sciences ; an international journal
N2 - A core operator of evolutionary algorithms (EAs) is the mutation. Recently, much attention has been devoted to the study of mutation operators with dynamic and non-uniform mutation rates. Following up on this area of work, we propose a new mutation operator and analyze its performance on the (1 + 1) Evolutionary Algorithm (EA). Our analyses show that this mutation operator competes with pre-existing ones, when used by the (1 + 1) EA on classes of problems for which results on the other mutation operators are available. We show that the (1 + 1) EA using our mutation operator finds a (1/3)-approximation ratio on any non-negative submodular function in polynomial time. We also consider the problem of maximizing a symmetric submodular function under a single matroid constraint and show that the (1 + 1) EA using our operator finds a (1/3)-approximation within polynomial time. This performance matches that of combinatorial local search algorithms specifically designed to solve these problems and outperforms them with constant probability. Finally, we evaluate the performance of the (1 + 1) EA using our operator experimentally by considering two applications: (a) the maximum directed cut problem on real-world graphs of different origins, with up to 6.6 million vertices and 56 million edges and (b) the symmetric mutual information problem using a four month period air pollution data set. In comparison with uniform mutation and a recently proposed dynamic scheme, our operator comes out on top on these instances.
KW - Evolutionary algorithms
KW - Mutation operators
KW - Submodular functions
KW - Matroids
Y1 - 2021
U6 - https://doi.org/10.1007/s11047-021-09841-7
SN - 1572-9796
VL - 20
IS - 3
SP - 561
EP - 575
PB - Springer Science + Business Media B.V.
CY - Dordrecht
ER -
TY - JOUR
A1 - Bläsius, Thomas
A1 - Friedrich, Tobias
A1 - Katzmann, Maximilian
A1 - Meyer, Ulrich
A1 - Penschuck, Manuel
A1 - Weyand, Christopher
T1 - Efficiently generating geometric inhomogeneous and hyperbolic random graphs
JF - Network Science
N2 - Hyperbolic random graphs (HRGs) and geometric inhomogeneous random graphs (GIRGs) are two similar generative network models that were designed to resemble complex real-world networks.
In particular, they have a power-law degree distribution with controllable exponent beta and high clustering that can be controlled via the temperature T.
We present the first implementation of an efficient GIRG generator running in expected linear time.
Besides varying temperatures, it also supports underlying geometries of higher dimensions. It is capable of generating graphs with ten million edges in under a second on commodity hardware. The algorithm can be adapted to HRGs.
Our resulting implementation is the fastest sequential HRG generator, despite the fact that we support non-zero temperatures. Though non-zero temperatures are crucial for many applications, most existing generators are restricted to T = 0 .
We also support parallelization, although this is not the focus of this paper.
Moreover, we note that our generators draw from the correct probability distribution, that is, they involve no approximation.
Besides the generators themselves, we also provide an efficient algorithm to determine the non-trivial dependency between the average degree of the resulting graph and the input parameters of the GIRG model.
This makes it possible to specify the desired expected average degree as input. Moreover, we investigate the differences between HRGs and GIRGs, shedding new light on the nature of the relation between the two models. Although HRGs represent, in a certain sense, a special case of the GIRG model, we find that a straightforward inclusion does not hold in practice.
However, the difference is negligible for most use cases.
KW - hyperbolic random graphs
KW - geometric inhomogeneous random graph
Y1 - 2022
U6 - https://doi.org/10.1017/nws.2022.32
SN - 2050-1242
SN - 2050-1250
VL - 10
IS - 4
SP - 361
EP - 380
PB - Cambridge Univ. Press
CY - New York
ER -
TY - JOUR
A1 - Bläsius, Thomas
A1 - Friedrich, Tobias
A1 - Lischeid, Julius
A1 - Meeks, Kitty
A1 - Schirneck, Friedrich Martin
T1 - Efficiently enumerating hitting sets of hypergraphs arising in data profiling
JF - Journal of computer and system sciences : JCSS
N2 - The transversal hypergraph problem asks to enumerate the minimal hitting sets of a hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP'95] gave an algorithm running in output-polynomial time, but whose space requirement also scales with the output. We improve this to polynomial delay and space. Central to our approach is the extension problem, deciding for a set X of vertices whether it is contained in any minimal hitting set. We show that this is one of the first natural problems to be W[3]-complete. We give an algorithm for the extension problem running in time O(m(vertical bar X vertical bar+1) n) and prove a SETH-lower bound showing that this is close to optimal. We apply our enumeration method to the discovery problem of minimal unique column combinations from data profiling. Our empirical evaluation suggests that the algorithm outperforms its worst-case guarantees on hypergraphs stemming from real-world databases.
KW - Data profiling
KW - Enumeration algorithm
KW - Minimal hitting set
KW - Transversal hypergraph
KW - Unique column combination
KW - W[3]-Completeness
Y1 - 2022
U6 - https://doi.org/10.1016/j.jcss.2021.10.002
SN - 0022-0000
SN - 1090-2724
VL - 124
SP - 192
EP - 213
PB - Elsevier
CY - San Diego
ER -
TY - JOUR
A1 - Bläsius, Thomas
A1 - Freiberger, Cedric
A1 - Friedrich, Tobias
A1 - Katzmann, Maximilian
A1 - Montenegro-Retana, Felix
A1 - Thieffry, Marianne
T1 - Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry
JF - ACM Transactions on Algorithms
N2 - A standard approach to accelerating shortest path algorithms on networks is the bidirectional search, which explores the graph from the start and the destination, simultaneously. In practice this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry.
To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is (O) over tilde (n(2-1/alpha) + n(1/(2 alpha)) + delta(max)) with high probability, where alpha is an element of (1/2, 1) controls the power-law exponent of the degree distribution, and dmax is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.
KW - Random graphs
KW - hyperbolic geometry
KW - scale-free networks
KW - bidirectional shortest path
Y1 - 2022
U6 - https://doi.org/10.1145/3516483
SN - 1549-6325
SN - 1549-6333
VL - 18
IS - 2
SP - 1
EP - 32
PB - Association for Computing Machinery
CY - New York
ER -
TY - JOUR
A1 - Shi, Feng
A1 - Schirneck, Friedrich Martin
A1 - Friedrich, Tobias
A1 - Kötzing, Timo
A1 - Neumann, Frank
T1 - Correction to: Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints
JF - Algorithmica : an international journal in computer science
Y1 - 2018
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-605295
SN - 0178-4617
SN - 1432-0541
VL - 82
IS - 10
SP - 3117
EP - 3123
PB - Springer
CY - New York
ER -
TY - JOUR
A1 - Hacker, Philipp
A1 - Naumann, Felix
A1 - Friedrich, Tobias
A1 - Grundmann, Stefan
A1 - Lehmann, Anja
A1 - Zech, Herbert
T1 - AI compliance - challenges of bridging data science and law
JF - Journal of Data and Information Quality (JDIQ)
N2 - This vision article outlines the main building blocks of what we term AI Compliance, an effort to bridge two complementary research areas: computer science and the law.
Such research has the goal to model, measure, and affect the quality of AI artifacts, such as data, models, and applications, to then facilitate adherence to legal standards.
KW - AI Act
KW - compliance
KW - liability
KW - privacy
KW - transparency
KW - information quality
Y1 - 2022
U6 - https://doi.org/10.1145/3531532
SN - 1936-1955
SN - 1936-1963
VL - 14
IS - 3
PB - Association for Computing Machinery
CY - New York
ER -
TY - RPRT
A1 - Döllner, Jürgen Roland Friedrich
A1 - Friedrich, Tobias
A1 - Arnrich, Bert
A1 - Hirschfeld, Robert
A1 - Lippert, Christoph
A1 - Meinel, Christoph
T1 - Abschlussbericht KI-Labor ITSE
T1 - Final report "AI Lab ITSE"
BT - KI-Labor für Methodik, Technik und Ausbildung in der IT-Systemtechnik
N2 - Der Abschlussbericht beschreibt Aufgaben und Ergebnisse des KI-Labors "ITSE". Gegenstand des KI-Labors bildeten Methodik, Technik und Ausbildung in der IT-Systemtechnik zur Analyse,
Planung und Konstruktion KI-basierter, komplexer IT-Systeme.
N2 - Final Report on the "AI Lab ITSE" dedicated to Methodology, Technology and Education of AI in IT-Systems Engineering.
KW - Abschlussbericht
KW - KI-Labor
KW - final report
KW - AI Lab
Y1 - 2022
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-578604
ER -