TY - JOUR
A1 - Steinrötter, Björn
T1 - Das Konzept einer datenaltruistischen Organisation
JF - Datenschutz und Datensicherheit
N2 - Dass Technologien wie Machine Learning-Anwendungen oder Big bzw. Smart Data- Verfahren unbedingt Daten in ausreichender Menge und Güte benötigen, erscheint inzwischen als Binsenweisheit. Vor diesem Hintergrund hat insbesondere der EU-Gesetzgeber für sich zuletzt ein neues Betätigungsfeld entdeckt, indem er versucht, auf unterschiedlichen Wegen Anreize zum Datenteilen zu schaffen, um Innovation zu kreieren. Hierzu zählt auch eine geradezu wohltönend mit ,,Datenaltruismus‘‘ verschlagwortete Konstellation. Der Beitrag stellt die diesbezüglichen Regulierungserwägungen auf supranationaler Ebene dar und nimmt eine erste Analyse vor.
KW - coding and information theory
KW - computer science
KW - general
KW - cryptology
KW - data structures and information theory
Y1 - 2021
U6 - https://doi.org/10.1007/s11623-021-1539-6
SN - 1862-2607
SN - 1614-0702
VL - 45
IS - 12
SP - 794
EP - 798
PB - Springer
CY - Berlin
ER -
TY - JOUR
A1 - Schindler, Daniel
A1 - Moldenhawer, Ted
A1 - Stange, Maike
A1 - Lepro, Valentino
A1 - Beta, Carsten
A1 - Holschneider, Matthias
A1 - Huisinga, Wilhelm
T1 - Analysis of protrusion dynamics in amoeboid cell motility by means of regularized contour flows
JF - PLoS Computational Biology : a new community journal
N2 - Amoeboid cell motility is essential for a wide range of biological processes including wound healing, embryonic morphogenesis, and cancer metastasis. It relies on complex dynamical patterns of cell shape changes that pose long-standing challenges to mathematical modeling and raise a need for automated and reproducible approaches to extract quantitative morphological features from image sequences. Here, we introduce a theoretical framework and a computational method for obtaining smooth representations of the spatiotemporal contour dynamics from stacks of segmented microscopy images. Based on a Gaussian process regression we propose a one-parameter family of regularized contour flows that allows us to continuously track reference points (virtual markers) between successive cell contours. We use this approach to define a coordinate system on the moving cell boundary and to represent different local geometric quantities in this frame of reference. In particular, we introduce the local marker dispersion as a measure to identify localized membrane expansions and provide a fully automated way to extract the properties of such expansions, including their area and growth time. The methods are available as an open-source software package called AmoePy, a Python-based toolbox for analyzing amoeboid cell motility (based on time-lapse microscopy data), including a graphical user interface and detailed documentation. Due to the mathematical rigor of our framework, we envision it to be of use for the development of novel cell motility models. We mainly use experimental data of the social amoeba Dictyostelium discoideum to illustrate and validate our approach.
Author summary Amoeboid motion is a crawling-like cell migration that plays an important key role in multiple biological processes such as wound healing and cancer metastasis. This type of cell motility results from expanding and simultaneously contracting parts of the cell membrane. From fluorescence images, we obtain a sequence of points, representing the cell membrane, for each time step. By using regression analysis on these sequences, we derive smooth representations, so-called contours, of the membrane. Since the number of measurements is discrete and often limited, the question is raised of how to link consecutive contours with each other. In this work, we present a novel mathematical framework in which these links are described by regularized flows allowing a certain degree of concentration or stretching of neighboring reference points on the same contour. This stretching rate, the so-called local dispersion, is used to identify expansions and contractions of the cell membrane providing a fully automated way of extracting properties of these cell shape changes. We applied our methods to time-lapse microscopy data of the social amoeba Dictyostelium discoideum.
Y1 - 2021
U6 - https://doi.org/10.1371/journal.pcbi.1009268
SN - 1553-734X
SN - 1553-7358
VL - 17
IS - 8
PB - PLoS
CY - San Fransisco
ER -
TY - JOUR
A1 - Tavakoli, Hamad
A1 - Alirezazadeh, Pendar
A1 - Hedayatipour, Ava
A1 - Nasib, A. H. Banijamali
A1 - Landwehr, Niels
T1 - Leaf image-based classification of some common bean cultivars using discriminative convolutional neural networks
JF - Computers and electronics in agriculture : COMPAG online ; an international journal
N2 - In recent years, many efforts have been made to apply image processing techniques for plant leaf identification. However, categorizing leaf images at the cultivar/variety level, because of the very low inter-class variability, is still a challenging task. In this research, we propose an automatic discriminative method based on convolutional neural networks (CNNs) for classifying 12 different cultivars of common beans that belong to three various species. We show that employing advanced loss functions, such as Additive Angular Margin Loss and Large Margin Cosine Loss, instead of the standard softmax loss function for the classification can yield better discrimination between classes and thereby mitigate the problem of low inter-class variability. The method was evaluated by classifying species (level I), cultivars from the same species (level II), and cultivars from different species (level III), based on images from the leaf foreside and backside. The results indicate that the performance of the classification algorithm on the leaf backside image dataset is superior. The maximum mean classification accuracies of 95.86, 91.37 and 86.87% were obtained at the levels I, II and III, respectively. The proposed method outperforms the previous relevant works and provides a reliable approach for plant cultivars identification.
KW - Bean
KW - Plant identification
KW - Digital image analysis
KW - VGG16
KW - Loss
KW - functions
Y1 - 2021
U6 - https://doi.org/10.1016/j.compag.2020.105935
SN - 0168-1699
SN - 1872-7107
VL - 181
PB - Elsevier
CY - Amsterdam [u.a.]
ER -
TY - JOUR
A1 - Pfitzner, Bjarne
A1 - Steckhan, Nico
A1 - Arnrich, Bert
T1 - Federated learning in a medical context
BT - a systematic literature review
JF - ACM transactions on internet technology : TOIT / Association for Computing
N2 - Data privacy is a very important issue. Especially in fields like medicine, it is paramount to abide by the existing privacy regulations to preserve patients' anonymity. However, data is required for research and training machine learning models that could help gain insight into complex correlations or personalised treatments that may otherwise stay undiscovered. Those models generally scale with the amount of data available, but the current situation often prohibits building large databases across sites. So it would be beneficial to be able to combine similar or related data from different sites all over the world while still preserving data privacy. Federated learning has been proposed as a solution for this, because it relies on the sharing of machine learning models, instead of the raw data itself. That means private data never leaves the site or device it was collected on. Federated learning is an emerging research area, and many domains have been identified for the application of those methods. This systematic literature review provides an extensive look at the concept of and research into federated learning and its applicability for confidential healthcare datasets.
KW - Federated learning
Y1 - 2021
U6 - https://doi.org/10.1145/3412357
SN - 1533-5399
SN - 1557-6051
VL - 21
IS - 2
SP - 1
EP - 31
PB - Association for Computing Machinery
CY - New York
ER -
TY - JOUR
A1 - Bonnet, Philippe
A1 - Dong, Xin Luna
A1 - Naumann, Felix
A1 - Tözün, Pınar
T1 - VLDB 2021
BT - Designing a hybrid conference
JF - SIGMOD record
N2 - The 47th International Conference on Very Large Databases (VLDB'21) was held on August 16-20, 2021 as a hybrid conference. It attracted 180 in-person attendees in Copenhagen and 840 remote attendees. In this paper, we describe our key decisions as general chairs and program committee chairs and share the lessons we learned.
Y1 - 2021
U6 - https://doi.org/10.1145/3516431.3516447
SN - 0163-5808
SN - 1943-5835
VL - 50
IS - 4
SP - 50
EP - 53
PB - Association for Computing Machinery
CY - New York
ER -
TY - JOUR
A1 - Cabalar, Pedro
A1 - Fandiño, Jorge
A1 - Fariñas del Cerro, Luis
T1 - Splitting epistemic logic programs
JF - Theory and practice of logic programming / publ. for the Association for Logic Programming
N2 - Epistemic logic programs constitute an extension of the stable model semantics to deal with new constructs called subjective literals. Informally speaking, a subjective literal allows checking whether some objective literal is true in all or some stable models. As it can be imagined, the associated semantics has proved to be non-trivial, since the truth of subjective literals may interfere with the set of stable models it is supposed to query. As a consequence, no clear agreement has been reached and different semantic proposals have been made in the literature. Unfortunately, comparison among these proposals has been limited to a study of their effect on individual examples, rather than identifying general properties to be checked. In this paper, we propose an extension of the well-known splitting property for logic programs to the epistemic case. We formally define when an arbitrary semantics satisfies the epistemic splitting property and examine some of the consequences that can be derived from that, including its relation to conformant planning and to epistemic constraints. Interestingly, we prove (through counterexamples) that most of the existing approaches fail to fulfill the epistemic splitting property, except the original semantics proposed by Gelfond 1991 and a recent proposal by the authors, called Founded Autoepistemic Equilibrium Logic.
KW - knowledge representation and nonmonotonic reasoning
KW - logic programming methodology and applications
KW - theory
Y1 - 2021
U6 - https://doi.org/10.1017/S1471068420000058
SN - 1471-0684
SN - 1475-3081
VL - 21
IS - 3
SP - 296
EP - 316
PB - Cambridge Univ. Press
CY - Cambridge [u.a.]
ER -
TY - JOUR
A1 - Göbel, Andreas
A1 - Lagodzinski, Julius Albert Gregor
A1 - Seidel, Karen
T1 - Counting homomorphisms to trees modulo a prime
JF - ACM transactions on computation theory : TOCT / Association for Computing Machinery
N2 - Many important graph-theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular independent sets and colourings. In this article, we study the complexity of #(p) HOMSTOH, the problem of counting graph homomorphisms from an input graph to a graph H modulo a prime number p. Dyer and Greenhill proved a dichotomy stating that the tractability of non-modular counting graph homomorphisms depends on the structure of the target graph. Many intractable cases in non-modular counting become tractable in modular counting due to the common phenomenon of cancellation. In subsequent studies on counting modulo 2, however, the influence of the structure of H on the tractability was shown to persist, which yields similar dichotomies.
Our main result states that for every tree H and every prime p the problem #pHOMSTOH is either polynomial time computable or #P-p-complete. This relates to the conjecture of Faben and Jerrum stating that this dichotomy holds for every graph H when counting modulo 2. In contrast to previous results on modular counting, the tractable cases of #pHOMSTOH are essentially the same for all values of the modulo when H is a tree. To prove this result, we study the structural properties of a homomorphism. As an important interim result, our study yields a dichotomy for the problem of counting weighted independent sets in a bipartite graph modulo some prime p. These results are the first suggesting that such dichotomies hold not only for the modulo 2 case but also for the modular counting functions of all primes p.
KW - Graph homomorphisms
KW - modular counting
KW - complexity dichotomy
Y1 - 2021
U6 - https://doi.org/10.1145/3460958
SN - 1942-3454
SN - 1942-3462
VL - 13
IS - 3
SP - 1
EP - 33
PB - Association for Computing Machinery
CY - New York
ER -
TY - JOUR
A1 - Nguyen, Dong Hai Phuong
A1 - Georgie, Yasmin Kim
A1 - Kayhan, Ezgi
A1 - Eppe, Manfred
A1 - Hafner, Verena Vanessa
A1 - Wermter, Stefan
T1 - Sensorimotor representation learning for an "active self" in robots
BT - a model survey
JF - Künstliche Intelligenz : KI ; Forschung, Entwicklung, Erfahrungen ; Organ des Fachbereichs 1 Künstliche Intelligenz der Gesellschaft für Informatik e.V., GI / Fachbereich 1 der Gesellschaft für Informatik e.V
N2 - Safe human-robot interactions require robots to be able to learn how to behave appropriately in spaces populated by people and thus to cope with the challenges posed by our dynamic and unstructured environment, rather than being provided a rigid set of rules for operations. In humans, these capabilities are thought to be related to our ability to perceive our body in space, sensing the location of our limbs during movement, being aware of other objects and agents, and controlling our body parts to interact with them intentionally. Toward the next generation of robots with bio-inspired capacities, in this paper, we first review the developmental processes of underlying mechanisms of these abilities: The sensory representations of body schema, peripersonal space, and the active self in humans. Second, we provide a survey of robotics models of these sensory representations and robotics models of the self; and we compare these models with the human counterparts. Finally, we analyze what is missing from these robotics models and propose a theoretical computational framework, which aims to allow the emergence of the sense of self in artificial agents by developing sensory representations through self-exploration.
KW - Developmental robotics
KW - Body schema
KW - Peripersonal space
KW - Agency
KW - Robot learning
Y1 - 2021
U6 - https://doi.org/10.1007/s13218-021-00703-z
SN - 0933-1875
SN - 1610-1987
VL - 35
IS - 1
SP - 9
EP - 35
PB - Springer
CY - Berlin
ER -
TY - JOUR
A1 - Omranian, Sara
A1 - Angeleska, Angela
A1 - Nikoloski, Zoran
T1 - PC2P
BT - parameter-free network-based prediction of protein complexes
JF - Bioinformatics
N2 - Motivation:
Prediction of protein complexes from protein-protein interaction (PPI) networks is an important problem in systems biology, as they control different cellular functions. The existing solutions employ algorithms for network community detection that identify dense subgraphs in PPI networks. However, gold standards in yeast and human indicate that protein complexes can also induce sparse subgraphs, introducing further challenges in protein complex prediction.
Results:
To address this issue, we formalize protein complexes as biclique spanned subgraphs, which include both sparse and dense subgraphs. We then cast the problem of protein complex prediction as a network partitioning into biclique spanned subgraphs with removal of minimum number of edges, called coherent partition. Since finding a coherent partition is a computationally intractable problem, we devise a parameter-free greedy approximation algorithm, termed Protein Complexes from Coherent Partition (PC2P), based on key properties of biclique spanned subgraphs. Through comparison with nine contenders, we demonstrate that PC2P: (i) successfully identifies modular structure in networks, as a prerequisite for protein complex prediction, (ii) outperforms the existing solutions with respect to a composite score of five performance measures on 75% and 100% of the analyzed PPI networks and gold standards in yeast and human, respectively, and (iii,iv) does not compromise GO semantic similarity and enrichment score of the predicted protein complexes. Therefore, our study demonstrates that clustering of networks in terms of biclique spanned subgraphs is a promising framework for detection of complexes in PPI networks.
Y1 - 2021
U6 - https://doi.org/10.1093/bioinformatics/btaa1089
SN - 1367-4811
VL - 37
IS - 1
SP - 73
EP - 81
PB - Oxford Univ. Press
CY - Oxford
ER -
TY - JOUR
A1 - Trautmann, Justin
A1 - Zhou, Lin
A1 - Brahms, Clemens Markus
A1 - Tunca, Can
A1 - Ersoy, Cem
A1 - Granacher, Urs
A1 - Arnrich, Bert
T1 - TRIPOD
BT - A treadmill walking dataset with IMU, pressure-distribution and photoelectric data for gait analysis
JF - Data : open access ʻData in scienceʼ journal
N2 - Inertial measurement units (IMUs) enable easy to operate and low-cost data recording for gait analysis. When combined with treadmill walking, a large number of steps can be collected in a controlled environment without the need of a dedicated gait analysis laboratory. In order to evaluate existing and novel IMU-based gait analysis algorithms for treadmill walking, a reference dataset that includes IMU data as well as reliable ground truth measurements for multiple participants and walking speeds is needed. This article provides a reference dataset consisting of 15 healthy young adults who walked on a treadmill at three different speeds. Data were acquired using seven IMUs placed on the lower body, two different reference systems (Zebris FDMT-HQ and OptoGait), and two RGB cameras. Additionally, in order to validate an existing IMU-based gait analysis algorithm using the dataset, an adaptable modular data analysis pipeline was built. Our results show agreement between the pressure-sensitive Zebris and the photoelectric OptoGait system (r = 0.99), demonstrating the quality of our reference data. As a use case, the performance of an algorithm originally designed for overground walking was tested on treadmill data using the data pipeline. The accuracy of stride length and stride time estimations was comparable to that reported in other studies with overground data, indicating that the algorithm is equally applicable to treadmill data. The Python source code of the data pipeline is publicly available, and the dataset will be provided by the authors upon request, enabling future evaluations of IMU gait analysis algorithms without the need of recording new data.
KW - inertial measurement unit
KW - gait analysis algorithm
KW - OptoGait
KW - Zebris
KW - data pipeline
KW - public dataset
Y1 - 2021
U6 - https://doi.org/10.3390/data6090095
SN - 2306-5729
VL - 6
IS - 9
PB - MDPI
CY - Basel
ER -
TY - JOUR
A1 - De Freitas, Jessica K.
A1 - Johnson, Kipp W.
A1 - Golden, Eddye
A1 - Nadkarni, Girish N.
A1 - Dudley, Joel T.
A1 - Böttinger, Erwin
A1 - Glicksberg, Benjamin S.
A1 - Miotto, Riccardo
T1 - Phe2vec
BT - Automated disease phenotyping based on unsupervised embeddings from electronic health records
JF - Patterns
N2 - Robust phenotyping of patients from electronic health records (EHRs) at scale is a challenge in clinical informatics. Here, we introduce Phe2vec, an automated framework for disease phenotyping from EHRs based on unsupervised learning and assess its effectiveness against standard rule-based algorithms from Phenotype KnowledgeBase (PheKB). Phe2vec is based on pre-computing embeddings of medical concepts and patients' clinical history. Disease phenotypes are then derived from a seed concept and its neighbors in the embedding space. Patients are linked to a disease if their embedded representation is close to the disease phenotype. Comparing Phe2vec and PheKB cohorts head-to-head using chart review, Phe2vec performed on par or better in nine out of ten diseases. Differently from other approaches, it can scale to any condition and was validated against widely adopted expert-based standards. Phe2vec aims to optimize clinical informatics research by augmenting current frameworks to characterize patients by condition and derive reliable disease cohorts.
Y1 - 2021
U6 - https://doi.org/10.1016/j.patter.2021.100337
SN - 2666-3899
VL - 2
IS - 9
PB - Elsevier
CY - Amsterdam
ER -
TY - JOUR
A1 - Freitas da Cruz, Harry
A1 - Pfahringer, Boris
A1 - Martensen, Tom
A1 - Schneider, Frederic
A1 - Meyer, Alexander
A1 - Böttinger, Erwin
A1 - Schapranow, Matthieu-Patrick
T1 - Using interpretability approaches to update "black-box" clinical prediction models
BT - an external validation study in nephrology
JF - Artificial intelligence in medicine : AIM
N2 - Despite advances in machine learning-based clinical prediction models, only few of such models are actually deployed in clinical contexts. Among other reasons, this is due to a lack of validation studies. In this paper, we present and discuss the validation results of a machine learning model for the prediction of acute kidney injury in cardiac surgery patients initially developed on the MIMIC-III dataset when applied to an external cohort of an American research hospital. To help account for the performance differences observed, we utilized interpretability methods based on feature importance, which allowed experts to scrutinize model behavior both at the global and local level, making it possible to gain further insights into why it did not behave as expected on the validation cohort. The knowledge gleaned upon derivation can be potentially useful to assist model update during validation for more generalizable and simpler models. We argue that interpretability methods should be considered by practitioners as a further tool to help explain performance differences and inform model update in validation studies.
KW - Clinical predictive modeling
KW - Nephrology
KW - Validation
KW - Interpretability
KW - methods
Y1 - 2021
U6 - https://doi.org/10.1016/j.artmed.2020.101982
SN - 0933-3657
SN - 1873-2860
VL - 111
PB - Elsevier
CY - Amsterdam
ER -
TY - JOUR
A1 - Borchert, Florian
A1 - Mock, Andreas
A1 - Tomczak, Aurelie
A1 - Hügel, Jonas
A1 - Alkarkoukly, Samer
A1 - Knurr, Alexander
A1 - Volckmar, Anna-Lena
A1 - Stenzinger, Albrecht
A1 - Schirmacher, Peter
A1 - Debus, Jürgen
A1 - Jäger, Dirk
A1 - Longerich, Thomas
A1 - Fröhling, Stefan
A1 - Eils, Roland
A1 - Bougatf, Nina
A1 - Sax, Ulrich
A1 - Schapranow, Matthieu-Patrick
T1 - Knowledge bases and software support for variant interpretation in precision oncology
JF - Briefings in bioinformatics
N2 - Precision oncology is a rapidly evolving interdisciplinary medical specialty. Comprehensive cancer panels are becoming increasingly available at pathology departments worldwide, creating the urgent need for scalable cancer variant annotation and molecularly informed treatment recommendations. A wealth of mainly academia-driven knowledge bases calls for software tools supporting the multi-step diagnostic process. We derive a comprehensive list of knowledge bases relevant for variant interpretation by a review of existing literature followed by a survey among medical experts from university hospitals in Germany. In addition, we review cancer variant interpretation tools, which integrate multiple knowledge bases. We categorize the knowledge bases along the diagnostic process in precision oncology and analyze programmatic access options as well as the integration of knowledge bases into software tools. The most commonly used knowledge bases provide good programmatic access options and have been integrated into a range of software tools. For the wider set of knowledge bases, access options vary across different parts of the diagnostic process. Programmatic access is limited for information regarding clinical classifications of variants and for therapy recommendations. The main issue for databases used for biological classification of pathogenic variants and pathway context information is the lack of standardized interfaces. There is no single cancer variant interpretation tool that integrates all identified knowledge bases. Specialized tools are available and need to be further developed for different steps in the diagnostic process.
KW - HiGHmed
KW - personalized medicine
KW - molecular tumor board
KW - data integration
KW - cancer therapy
Y1 - 2021
U6 - https://doi.org/10.1093/bib/bbab134
SN - 1467-5463
SN - 1477-4054
VL - 22
IS - 6
PB - Oxford Univ. Press
CY - Oxford
ER -
TY - CHAP
A1 - Gundlach, Jana
A1 - Abramova, Olga
T1 - Newsfeed clutter as an inhibitor of sensemaking
T2 - AMCIS Proceedings 2021
N2 - As a central functionality of SNSs, the newsfeed is responsible for the way, how content is presented. This paper investigates the implications of current content presentation on Facebook, which has appeared to be a matter of users’ criticism. Leaning on the communication theory, we conceptualize clutter on a newsfeed as noise that hinders the receiver’s adequate message decoding (i.e., sensemaking). We further operationalize newsfeed clutter via perceived disorder, information overload, and system feature overload. Our participants browsed their Facebook newsfeed for at least 5 minutes. The follow-up survey results provide partial support for our hypotheses, with only perceived disorder significantly associated with lower sensemaking. These findings shed new light on user experience and underpin the importance of SNSs as communication systems, adding to the existent literature on the dark sides of social media.
Y1 - 2021
UR - https://aisel.aisnet.org/amcis2021/virtual_communities/virtual_communities/3/
SN - 978-1-7336325-8-4
PB - AIS
CY - Atlanta
ER -
TY - CHAP
A1 - Brinkmann, Maik
T1 - Relevance of public administrations
BT - visualization of shifting power relations in blockchain-based public service delivery
T2 - Proceedings of the 54th Hawaii International Conference on System Sciences 2021
N2 - Power relations within the area of blockchain governance are complex by definition and a comprehensive analysis that links technological and institutional elements is missing to date. The research that is presented with this article focuses on the visualization of the shifting power relations with the introduction of blockchain. For this purpose, the analysis leverages an adjusted version of the multi-stakeholder influence mapping tool. The analysis considers the various stakeholders within the multi-layered blockchain technology stack and compares three fundamental blockchain scenarios, including public and private blockchain settings. The findings show that public administrations face indeed less power with the introduction of blockchain, while new stakeholders come into play who wield influence rather uncontrolled. Nonetheless, public administrations are not powerless overall and remain influential stakeholders. This paper concludes that blockchain governance is not as democratic as blockchain enthusiasts tend to argue and derives corresponding opportunities for further research.
KW - Emerging Topics in Digital Government
KW - blockchain
KW - influence mapping
KW - power relations
KW - stakeholder analysis
KW - visualization
Y1 - 2021
SN - 978-0-9981331-4-0
U6 - https://doi.org/10.24251/HICSS.2021.285
PB - University of Hawaiʻi at Mānoa
CY - Honolulu, HI
ER -
TY - THES
A1 - Hecher, Markus
T1 - Advanced tools and methods for treewidth-based problem solving
N2 - In the last decades, there was a notable progress in solving the well-known Boolean satisfiability (Sat) problem, which can be witnessed by powerful Sat solvers. One of the reasons why these solvers are so fast are structural properties of instances that are utilized by the solver’s interna. This thesis deals with the well-studied structural property treewidth, which measures the closeness of an instance to being a tree. In fact, there are many problems parameterized by treewidth that are solvable in polynomial time in the instance size when parameterized by treewidth.
In this work, we study advanced treewidth-based methods and tools for problems in knowledge representation and reasoning (KR). Thereby, we provide means to establish precise runtime results (upper bounds) for canonical problems relevant to KR. Then, we present a new type of problem reduction, which we call decomposition-guided (DG) that
allows us to precisely monitor the treewidth when reducing from one problem to another problem. This new reduction type will be the basis for a long-open lower bound result for quantified Boolean formulas and allows us to design a new methodology for establishing runtime lower bounds for problems parameterized by treewidth.
Finally, despite these lower bounds, we provide an efficient implementation of algorithms that adhere to treewidth. Our approach finds suitable abstractions of instances, which are subsequently refined in a recursive fashion, and it uses Sat solvers for solving subproblems. It turns out that our resulting solver is quite competitive for two canonical counting problems related to Sat.
N2 - In den letzten Jahrzehnten konnte ein beachtlicher Fortschritt im Bereich der Aussagenlogik verzeichnet werden. Dieser äußerte sich dadurch, dass für das wichtigste Problem in diesem Bereich, genannt „Sat“, welches sich mit der Fragestellung befasst, ob eine gegebene aussagenlogische Formel erfüllbar ist oder nicht, überwältigend schnelle Computerprogramme („Solver“) entwickelt werden konnten. Interessanterweise liefern diese Solver eine beeindruckende Leistung, weil sie oft selbst Probleminstanzen mit mehreren Millionen von Variablen spielend leicht lösen können. Auf der anderen Seite jedoch glaubt man in der Wissenschaft weitgehend an die Exponentialzeithypothese (ETH), welche besagt, dass man im schlimmsten Fall für das Lösen einer Instanz in diesem Bereich exponentielle Laufzeit in der Anzahl der Variablen benötigt. Dieser vermeintliche Widerspruch ist noch immer nicht vollständig geklärt, denn wahrscheinlich gibt es viele ineinandergreifende Gründe für die Schnelligkeit aktueller Sat Solver. Einer dieser Gründe befasst sich weitgehend mit strukturellen Eigenschaften von Probleminstanzen, die wohl indirekt und intern von diesen Solvern ausgenützt werden.
Diese Dissertation beschäftigt sich mit solchen strukturellen Eigenschaften, nämlich mit der sogenannten Baumweite. Die Baumweite ist sehr gut erforscht und versucht zu messen, wie groß der Abstand von Probleminstanzen zu Bäumen ist (Baumnähe). Allerdings ist dieser Parameter sehr generisch und bei Weitem nicht auf Problemstellungen der Aussagenlogik beschränkt. Tatsächlich gibt es viele weitere Probleme, die parametrisiert mit Baumweite in polynomieller Zeit gelöst werden können. Interessanterweise gibt es auch viele Probleme in der Wissensrepräsentation (KR), von denen man davon ausgeht, dass sie härter sind als das Problem Sat, die bei beschränkter Baumweite in polynomieller Zeit gelöst werden können. Ein prominentes Beispiel solcher Probleme ist das Problem QSat, welches sich für die Gültigkeit einer gegebenen quantifizierten, aussagenlogischen Formel (QBF), das sind aussagenlogische Formeln, wo gewisse Variablen existenziell bzw. universell quantifiziert werden können, befasst. Bemerkenswerterweise wird allerdings auch im Zusammenhang mit Baumweite, ähnlich zu Methoden der klassischen Komplexitätstheorie, die tatsächliche Komplexität (Härte) solcher Problemen quantifiziert, wo man die exakte Laufzeitabhängigkeit beim Problemlösen in der Baumweite (Stufe der Exponentialität) beschreibt.
Diese Arbeit befasst sich mit fortgeschrittenen, Baumweite-basierenden Methoden und Werkzeugen für Probleme der Wissensrepräsentation und künstlichen Intelligenz (AI). Dabei präsentieren wir Methoden, um präzise Laufzeitresultate (obere Schranken) für prominente Fragmente der Antwortmengenprogrammierung (ASP), welche ein kanonisches Paradigma zum Lösen von Problemen der Wissensrepräsentation darstellt, zu erhalten. Unsere Resultate basieren auf dem Konzept der dynamischen Programmierung, die angeleitet durch eine sogenannte Baumzerlegung und ähnlich dem Prinzip „Teile-und-herrsche“ funktioniert. Solch eine Baumzerlegung ist eine konkrete, strukturelle Zerlegung einer Probleminstanz, die sich stark an der Baumweite orientiert.
Des Weiteren präsentieren wir einen neuen Typ von Problemreduktion, den wir als „decomposition-guided (DG)“, also „zerlegungsangeleitet“, bezeichnen. Dieser Reduktionstyp erlaubt es, Baumweiteerhöhungen und -verringerungen während einer Problemreduktion von einem bestimmten Problem zu einem anderen Problem präzise zu untersuchen und zu kontrollieren. Zusätzlich ist dieser neue Reduktionstyp die Basis, um ein lange offen gebliebenes Resultat betreffend quantifizierter, aussagenlogischer Formeln zu zeigen. Tatsächlich sind wir damit in der Lage, präzise untere Schranken, unter der Annahme der Exponentialzeithypothese, für das Problem QSat bei beschränkter Baumweite zu zeigen. Genauer gesagt können wir mit diesem Konzept der DG Reduktionen zeigen, dass das Problem QSat, beschränkt auf Quantifizierungsrang ` und parametrisiert mit Baumweite k, im Allgemeinen nicht besser als in einer Laufzeit, die `-fach exponentiell in der Baumweite und polynomiell in der Instanzgröße ist1, lösen. Dieses Resultat hebt auf nicht-inkrementelle Weise ein bekanntes Ergebnis für Quantifizierungsrang 2 auf beliebige Quantifizierungsränge, allerdings impliziert es auch sehr viele weitere Konsequenzen.
Das Resultat über die untere Schranke des Problems QSat erlaubt es, eine neue Methodologie zum Zeigen unterer Schranken einer Vielzahl von Problemen der Wissensrepräsentation und künstlichen Intelligenz, zu etablieren. In weiterer Konsequenz können wir damit auch zeigen, dass die oberen Schranken sowie die DG Reduktionen dieser Arbeit unter der Hypothese ETH „eng“ sind, d.h., sie können wahrscheinlich nicht mehr signifikant verbessert werden. Die Ergebnisse betreffend der unteren Schranken für QSat und die dazugehörige Methodologie konstituieren in gewisser Weise eine Hierarchie von über Baumweite parametrisierte Laufzeitklassen. Diese Laufzeitklassen können verwendet werden, um die Härte von Problemen für das Ausnützen von Baumweite zu quantifizieren und diese entsprechend ihrer Laufzeitabhängigkeit bezüglich Baumweite zu kategorisieren.
Schlussendlich und trotz der genannten Resultate betreffend unterer Schranken sind wir im Stande, eine effiziente Implementierung von Algorithmen basierend auf dynamischer Programmierung, die entlang einer Baumzerlegung angeleitet wird, zur Verfügung zu stellen. Dabei funktioniert unser Ansatz dahingehend, indem er probiert, passende Abstraktionen von Instanzen zu finden, die dann im Endeffekt sukzessive und auf rekursive Art und Weise verfeinert und verbessert werden. Inspiriert durch die enorme Effizienz und Effektivität der Sat Solver, ist unsere Implementierung ein hybrider Ansatz, weil sie den starken Gebrauch von Sat Solvern zum Lösen diverser Subprobleme, die während der dynamischen Programmierung auftreten, pflegt. Dabei stellt sich heraus, dass der resultierende Solver unserer Implementierung im Bezug auf Effizienz beim Lösen von zwei kanonischen, Sat-verwandten Zählproblemen mit bestehenden Solvern locker mithalten kann. Tatsächlich sind wir im Stande, Instanzen, wo die oberen Schranken von Baumweite 260 übersteigen, zu lösen. Diese überraschende Beobachtung zeigt daher, dass Baumweite ein wichtiger Parameter sein könnte, der wohl in modernen Designs von Solvern berücksichtigt werden sollte.
KW - Treewidth
KW - Dynamic Programming
KW - Knowledge Representation and Reasoning
KW - Artificial Intelligence
KW - Computational Complexity
KW - Parameterized Complexity
KW - Answer Set Programming
KW - Exponential Time Hypothesis
KW - Lower Bounds
KW - Algorithms
KW - Algorithmen
KW - Antwortmengenprogrammierung
KW - Künstliche Intelligenz
KW - Komplexitätstheorie
KW - Dynamische Programmierung
KW - Exponentialzeit Hypothese
KW - Wissensrepräsentation und Schlussfolgerung
KW - Untere Schranken
KW - Parametrisierte Komplexität
KW - Baumweite
Y1 - 2021
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-512519
ER -
TY - JOUR
A1 - Schneider, Johannes
A1 - Wenig, Phillip
A1 - Papenbrock, Thorsten
T1 - Distributed detection of sequential anomalies in univariate time series
JF - The VLDB journal : the international journal on very large data bases
N2 - The automated detection of sequential anomalies in time series is an essential task for many applications, such as the monitoring of technical systems, fraud detection in high-frequency trading, or the early detection of disease symptoms. All these applications require the detection to find all sequential anomalies possibly fast on potentially very large time series. In other words, the detection needs to be effective, efficient and scalable w.r.t. the input size. Series2Graph is an effective solution based on graph embeddings that are robust against re-occurring anomalies and can discover sequential anomalies of arbitrary length and works without training data. Yet, Series2Graph is no t scalable due to its single-threaded approach; it cannot, in particular, process arbitrarily large sequences due to the memory constraints of a single machine. In this paper, we propose our distributed anomaly detection system, short DADS, which is an efficient and scalable adaptation of Series2Graph. Based on the actor programming model, DADS distributes the input time sequence, intermediate state and the computation to all processors of a cluster in a way that minimizes communication costs and synchronization barriers. Our evaluation shows that DADS is orders of magnitude faster than S2G, scales almost linearly with the number of processors in the cluster and can process much larger input sequences due to its scale-out property.
KW - Distributed programming
KW - Sequential anomaly
KW - Actor model
KW - Data mining
KW - Time series
Y1 - 2021
U6 - https://doi.org/10.1007/s00778-021-00657-6
SN - 1066-8888
SN - 0949-877X
VL - 30
IS - 4
SP - 579
EP - 602
PB - Springer
CY - Berlin
ER -
TY - JOUR
A1 - Fandiño, Jorge
A1 - Laferriere, Francois
A1 - Romero, Javier
A1 - Schaub, Torsten
A1 - Son, Tran Cao
T1 - Planning with incomplete information in quantified answer set programming
JF - Theory and practice of logic programming
N2 - We present a general approach to planning with incomplete information in Answer Set Programming (ASP). More precisely, we consider the problems of conformant and conditional planning with sensing actions and assumptions. We represent planning problems using a simple formalism where logic programs describe the transition function between states, the initial states and the goal states. For solving planning problems, we use Quantified Answer Set Programming (QASP), an extension of ASP with existential and universal quantifiers over atoms that is analogous to Quantified Boolean Formulas (QBFs). We define the language of quantified logic programs and use it to represent the solutions different variants of conformant and conditional planning. On the practical side, we present a translation-based QASP solver that converts quantified logic programs into QBFs and then executes a QBF solver, and we evaluate experimentally the approach on conformant and conditional planning benchmarks.
KW - answer set programming
KW - planning
KW - quantified logics
Y1 - 2021
U6 - https://doi.org/10.1017/S1471068421000259
SN - 1471-0684
SN - 1475-3081
VL - 21
IS - 5
SP - 663
EP - 679
PB - Cambridge University Press
CY - Cambridge
ER -
TY - CHAP
A1 - Dehnert, Maik
A1 - Gleiß, Alexander
A1 - Reiss, Frederick
T1 - What makes a data-driven business model?
BT - a consolidated taxonomy
T2 - ECIS Proceedings 2021
N2 - The usage of data to improve or create business models has become vital for companies in the 21st century. However, to extract value from data it is important to understand the business model. Taxonomies for data-driven business models (DDBM) aim to provide guidance for the development and ideation of new business models relying on data. In IS research, however, different taxonomies have emerged in recent years, partly redundant, partly contradictory. Thus, there is a need to synthesize the common ground of these taxonomies within IS research. Based on 26 IS-related taxonomies and 30 cases, we derive and define 14 generic building blocks of DDBM to develop a consolidated taxonomy that represents the current state-of-the-art. Thus, we integrate existing research on DDBM and provide avenues for further exploration of data-induced potentials for business models as well as for the development and analysis of general or industry-specific DDBM.
Y1 - 2021
UR - https://aisel.aisnet.org/ecis2021_rp/139
SN - 978-1-7336325-6-0
PB - AIS
CY - Atlanta
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 -