The CS department's Talk Series
Have you ever wondered what happens behind all these doors in our department?
Are you curious what is happening around you?
What are all these people busy with?
What research is emerging and which results are actually being produced in the CS department?
The CS department's Talk Series is a forum to researchers from different groups. It offers a great opportunity to learn about cutting-edge research, to talk to members of other research groups and to interconnect your research.
We especially want to invite all PhD students and research staff to the meetings, but interested master students are very welcome.
If you want to participate by giving a talk yourself, please contact us at firstname.lastname@example.org!
Schedule for Summer Term 2017
Monday, 08.05.2011, 13:30 in 48-680
Manuel Hoffmann (DBIS): Scaling Out Continuous Multi-Way Theta-Joins
Join computation is one of the core challenges of query processing. A join connects tuples of two or more relations if they match a given predicate. This way interesting insights are possible, e.g., by connecting customer and product data one can see the people of which area are interested in which products from an online bookstore. As the data to be processed increases in volume, and the view on the data changes from relatively static relations in a database, to continuously arriving tuples in a stream, the computation needs to be distributed amongst multiple machines in order to be able to produce the desired result. This talk is about scaling-out join computation in a distributed data stream system (namely Apache Storm). In order to do so, a logical query plan is developed, and that logical plan is used to construct a topology, which is the core abstraction used in Storm. Finally this topology is deployed on a cluster where the query is processed.
Schedule of Winter Term 2016/17
Friday, 25.11.2016, 15:30 in 42-110
Ori Lahav (MPI-SWS): A Promising Semantics for Relaxed-Memory Concurrency
Despite many years of research, it has proven very difficult to develop a memory model for concurrent programming languages that adequately balances the conflicting desiderata of programmers, compilers, and hardware. In this talk, we present the first relaxed memory model that (1) accounts for a broad spectrum of features from the C++11 concurrency model, (2) is implementable, in the sense that it provably validates many standard compiler optimizations and reorderings, as well as standard compilation schemes to x86-TSO and Power, (3) justifies simple invariant-based reasoning, thus demonstrating the absence of bad ``out-of-thin-air'' behaviors, (4) supports ``DRF'' guarantees, ensuring that programmers who use sufficient synchronization need not understand the full complexities of relaxed-memory semantics, and (5) defines the semantics of racy programs without relying on undefined behaviors, which is a prerequisite for applicability to type-safe languages like Java. The key novel idea behind our model is the notion of promises: a thread may promise to execute a write in the future, thus enabling other threads to read from that write out of order. Crucially, to prevent out-of-thin-air behaviors, a promise step requires a thread-local certification that it will be possible to execute the promised write even in the absence of the promise. To establish confidence in our model, we have formalized most of our key results in Coq. Joint work with Jeehoon Kang, Chung-Kil Hur, Viktor Vafeiadis, and Derek Dreyer.
Friday, 09.12.2016, 15:30 in 42-110
Sergiy Bogomolov (Australian National University): Cyber-Physical Systems: Challenges and Opportunities
Cyber-physical systems (CPS) are networks of physical and digital components and present a next generation of large-scale highly-interconnected networked embedded systems. On the one hand, CPS open enormous opportunities as they form the core of emerging smart devices and services which are going to revolutionize many traditional industries such as transportation and traffic management, power generation and delivery, as well as manufacturing. On the other hand, highly autonomous systems pose special engineering challenges as any unexpected behaviour might lead to large financial losses or even human deaths. In this talk, we address this challenge and propose automatic techniques to analyze CPS. For this purpose, we use the concept of hybrid automata which has proven to be particularly useful to model CPS. We give an overview of techniques to ensure efficient analysis of hybrid automata. In particular, we present support-function based representation of region state space and discuss ways to refine it. Finally, we present PhD program in Computer Science at the Australian National University. In particular, we discuss (1) academic life in Australia, (2) present PhD scholarships provided by the University and discuss application process towards these scholarships, and (3) talk about differences between German and Australian academic systems.
Friday, 13.01.2017, 15:30 in 42-110
Hammad Tanveer Butt (AG Stricker): Deep Learning: Beyond vision
Deep learning is everywhere, talk of the town these days. Aided by the power of new GPUs, training deep neural networks has come of an age. And now with Internet of Things (IoT), we stand at the brink of another information explosion. All this big data will need deep learning in future. And not all of this data will come in form of images or video streams. The deep Convolutional Neural Network (CNN) has made significant impact in the domain of computer vision. And we are learning to see advantage of Long Short Term Memory (LSTM), a recurrent neural network (RNN) architecture in predicting sequences and natural language processing (NLP). But the deep learning wave will no longer stop here. Apart from classification and pattern recognition tasks, we also often need to learn function approximation and regression to deal with data in the real world. In the first part of this talk, I shall highlight how we can understand the implications of using shallow versus deep architecture for function approximation. For understanding the regression ability of deep networks, it is very important that we can analyze these networks in conceptual terms beyond their traditional pattern classifier role. I shall point out why the need for a recurrent neural network (RNN) arises in first place, when dealing with real world signals and sequences. Then I would mention some emerging applications of deep neural networks, before focusing on the topic of sensor fusion and regression using these networks. In second part, I would start with some interesting applications of neural network based regression on which I have worked in past, including a robot navigation and obstacle avoidance problem and helicopter rotor dynamic balancing solution obtained using feedforward neural networks. Then I will explain the current focus of my PhD research i.e. using deep learning for inertial sensors fusion and human motion and gait analysis from acceleration and rate gyro data of Inertial Measurement Units (IMUs). This research would also imply human pose estimation and activity recognition using IMUs and augments the cutting edge research going on in computer vision, augmented & virtual reality.
Kripasindhu Sarkar (AG Stricker): Object recognition using 3D data
Object detection and recognition in images is the fundamental problem of Computer Vision. Given an image, the end focus of Computer Vision has always been to interpret the image in some level - be it segmentation, classification or recognition of a particular instance of a real object. Even though modern digital computers have outperformed humans in the domain of numeric computation and serialized flows, human can effortlessly solve complex perceptual problems - Eg. recognizing an object, identifying someone by face etc. - which are significantly difficult for a computer to perform. Can we improve our detection system when we have a massive amount of 3D data (from 3D scanners and from the field of Computer Graphics) available to us? The first half of the talk gives an overview of the object recognition techniques in Computer Vision and its progress from the past to the present methods involving Deep Convolution Neural Networks. The second half focuses on the current work in the thesis which utilizes 3D data for vision. The 3D geometry is investigated by the means of a 3D representational unit - local patches - its graphical application in terms of hole filling, and its global extension involving a layered representation for complex shapes for object detection and and reconstruction.
Friday, 27.01.2017, 15:30 in 42-110
Tewodrows Amberbir Habtegebrial (AG Stricker): Novel View Synthesis with Deep Neural Nets
Novel View Synthesis is a well established problem in computer vision. It is defined as rendering a scene from a desired view point given other view(s) of the scene. Novel view synthesis belongs to the so called image based rendering methods which render views by using images as rendering primitives. Traditionally, this problem has been solved with Plane Sweep Stereo. Recently, neural network based approaches were also proposed. In this talk I will present state-of-the-art approaches and our recent work which combines ideas from traditional computer vision with neural networks. Our proposed approach is capable of rendering high quality images using only few input views.
Vitor Fortes Rey (AG Lukowicz): Opportunistic Activity Recognition
Current activity recognition systems mostly work with static, pre-trained sensor configuration. As a consequence they are not able to leverage new sensors appearing in their environment (e.g. the user buying a new wearable devices). In this work we present a method inspired that can add new sensors to an existing system in an unsupervised manner, taking advantage of the information provided by new unknown sensor sources.
Friday, 10.02.2017, 15:30 in 42-110
Sujay Muramalla (AG Zweig/AG Kuhn): Cognitive Aspects of Teaching Algorithms
Studies in the area of health informatics and health literacy have shown that diagnostic test information, when represented in natural frequencies rather conditional probabilities can facilitate judgement on positive predictive values (PPV). The natural frequency representation was also shown to be working effectively well with old and young adults and those with low numeracy skills. Representations such as natural frequencies and percentages conceal the hidden algorithms behind the tasks framed. In the current study, we identified the problem of task framing in the past studies and aim to perform eye tracking experiments with different task framing strategies and selection of effective cognitive strategies for the tasks framed. By deriving eye tracking measures, we further aim to find correlations between working memory capacity, numeracy and language fluency skills for task reading and strategy selection between experts and novices among non-native university students with mathematics related fields of studies.
Shoya Ishimaru (AG Dengel): Cognitive Activity Recognition for Augmenting the Human Mind
Recognition of human activities and the contexts is the first step to develop a system which improves our daily lives. While physical activities (e.g., walking, sleeping) can be recognized by body-mounted motion sensors, recognizing cognitive activities (e.g., reading, writing) is still a challenging task because body movements during the activities are limited and it is difficult to apply the same approach. Additional sensors are required to recognize them. I'm currently utilizing eye tracking to solve the problem because the relationship between cognitive activities and eye movements is well explored in cognitive science and psychology. In this presentation, I will present some cognitive activity recognition approaches and applications (e.g., intelligent textbook, reading activity tracker) which enhance our cognitive abilities.
Schedule of Winter Term 2015/16
Tuesday, 10.11.2015, 11:00 in 48-680
Deepthi Akkoorath (AG Softech): Transactions on Mergeable Objects
Destructible updates on shared objects require careful handling of concurrent accesses in multi-threaded programs. Paradigms such as Transactional Memory support the programmer in correctly synchronizing access to mutable shared data by serializing the transactional reads and writes. But under high contention, serializable transactions incur frequent aborts and limit parallelism. This can lead to a severe performance degradation. We propose mergeable transactions which provide a consistency semantics that allows for more scalability even under contention. Instead of aborting and re-executing, object versions from conflicting updates on shared objects are merged using data-type specific semantics. The evaluation of our prototype implementation in Haskell shows that mergeable transactions outperform serializable transactions even under low contention while providing a structured and type-safe interface.
Marsha Minchenko: Investigating the Missing Moore Graph
Moore Graphs are regular graphs with diameter d and girth 2d + 1. Some well known examples are the Petersen graph and the Hoffman-Singleton graph. It is not known if the 57-regular Moore graph for d = 2 exists. We look at how our equations -- that relate the eigenvalues of a regular graph to the counts of subgraphs -- can be used to investigate the missing Moore graph (H57). With the aid of some basic counting arguments, these equations give further insights into the structure of the H57 such as the numbers of various small subgraphs. We will also explore the problem of counting subgraphs in Moore graphs where d = 2 and give some of our results. This is joint work with Ian Wanless (Monash University, Australia).
Tuesday, 24.11.2015, 11:00 in 48-680
Sebastian Muskalla: Games on Grammars
A context-free grammar together with a partition of the non-terminals defines a graph. One can play games with perfect information on such graphs. The main part of the talk will be dedicated to solving the regular inclusion game. Since context-free grammars can be used to describe the behavior of recursive programs, this corresponds to synthesizing a recursive program that admits a given regular specification. We will see that, surprisingly, the alternating behavior of the game can be captured by formulas which grow in a monotonous manner. These formulas can be used to determine whether a player can win from a given position and to generate winning strategies.
Peter Chini (AG Concurrency Theory): Higher-order pushdown systems of bounded treewidth
Classical pushdown systems are able to manipulate a level-1 stack: they can push and pop elements. With this model, one can represent recursive functions. Higher order pushdown systems (HOPDS) are a natural generalization of the classical model: they manipulate level n-stacks and they can represent higher-order functions. In the talk, we will interpret computations of HOPDSs as graphs and give an idea why these graphs have bounded treewidth in the case of order 2. To this end, we shortly introduce cops & robber games and construct a winning strategy for them. Finally, using a Theorem of Courcelle, we are able to decide MSO-formulas over such graphs.
Tuesday, 08.12.2015, 11:00 in 48-680
Adnan Ul-Hasan: Generic Text Recognition using Long Short-Term Memory Networks
The task of printed Optical Character Recognition (OCR), though considered “solved” by many, still poses several challenges. The complex grapheme structure of many scripts, such as Devanagari and Urdu Nastaleeq, greatly lowers the performance of state-of-the-art OCR systems. Moreover, the digitization of historical and multilingual documents still require much probing. Lack of benchmark datasets further complicates the development of reliable OCR systems. This thesis aims to find the answers to some of these challenges using contemporary machine learning technologies. The absence of any sophisticated script-specific features and post-processing language-modeling enable the same architecture to be used for a variety of scripts. The first major contribution of this thesis is to demonstrate the usability of LSTM networks for monolingual documents. The LSTM networks yield very good OCR results on various modern scripts including modern English, Urdu Nastaleeq and Devanagari. To address the challenge of OCR of historical documents, this thesis focuses on Old German Fraktur script, medieval Latin script of the 15th century, and Polytonic Greek script. LSTM-based systems outperform the contemporary OCR systems on all of these scripts. Another major contribution of this thesis is the development of a novel multilingual OCR system. A unified framework for dealing with different types of multilingual documents has been proposed. In this design, the LSTM networks recognize multiple languages and scripts simultaneously without the need to identify different scripts. Along with the application of LSTM-based text recognizer for various scripts, benchmark datasets have also been proposed to advance the OCR research further.
Houssam Abdoullah (AG Softech): Programming with more consistency guarantees over eventually consistent data stores
Many distributed systems use replicated data to improve the availability of the system. However, keeping the replicated data in a consistent state over all replicas requires synchronizations, which affect the availability. Thus, practitioners resorted to weaker consistency models to improve the availability. Many applications that require some integrity constraints are either implemented over strong consistent data store (thus losing the availability) or implemented using ad-hoc solutions to keep these constraints over weak consistent data store. These applications are the target of our research. The goal is to provide more consistency guarantees when programming over weak consistency models while optimizing the synchronization overhead. These guarantees can be specified as application invariants that have to be preserved during the execution.
Tuesday, 12.01.2016, 15:30 (!! different time !!) in 48-680
Mareike Bockholt (AG GTNA): Measures for the Similarity of Paths in Complex Networks
In various research fields, methods from complex network analysis have been applied in order to analyze complex systems. There are network representations for which the idea of traversing the network arises naturally, consider for example travels in a transportation or road network, packets being routed through the Internet, or humans navigating through a problem's state space. Although the concept of paths in networks is intuitive, to our knowledge, there has not been any approach to compare paths by similarity in order to cluster more similar paths in groups. In my talk, I will present the approach of my Master thesis in which I attempted an analysis of path similarity and distance measures and a first approach of clustering real path data by similarity. Aiming at deriving appropriate path similarity and distance measures, I identified characteristic features of paths a similarity measure can be based on, as well as general properties a similarity measure for paths should fulfill. Guided by the identified features, several similarity and distance measures for paths in networks are proposed and the proposed measures are analyzed for their properties. Furthermore, I used path data collected on a web-based learning tool where the paths represent the navigation of humans through the problem state of a game while solving the game. The similarity value for each of the proposed measures was computed for each pair of paths and the paths are clustered by their similarity using an hierarchical clustering approach.
Vasil Tenev (Fraunhofer IESE): Deployment Optimization for Software Variants in Embedded Systems
This work introduces a framework for finding an optimal deployment of software variants to given hardware architecture. Here the family of software variants is described by a feature model. A tool was developed that always returns a deployment for the entire family, as long as all variants are individually deployable. It provides a transparent layer for guiding the underlying evolution process for the individual deployments, which allows the user to integrate her or his domain specific knowledge and assure better results. Despite the exponential number of variants within one family our tests showed that the expected amortized time behaves with quadratic growth in the number of features.
Tuesday, 09.02.2016, 11:00 in 48-680
Evica Milcheveski: The Sweet Spot between Inverted Indices and Metric-Space Indexing for Top-K-List Similarity Search
In this talk we are going to introduce the problem of processing similarity queries over a set of top-k rankings where the query ranking and the similarity threshold are provided at query time. We explain a setup that allows the application of metric index structures such as M- or BK-trees and, alternatively, enables the use of traditional inverted indices for retrieving rankings that overlap (in items) with the query. Although both techniques are reasonable, they come with individual drawbacks for our specific problem. We will present a hybrid indexing strategy, which blends inverted indices and metric space indexing, resulting in a structure that resembles both indexing methods with tunable emphasis on one or the other. Furthermore, we would discuss how to find the sweet spot, by using an assumption-lean but highly accurate cost model through theoretical analysis. The performance of the proposed algorithms, hybrid variants, and competitors is evaluated using real-world benchmark data.
Susanne Braun: Engineering Mobile Data Synchronisation
In practice mobile clients have to deal with various limitations like bad connectivity, limited bandwidth or short battery run times. To hide those limitations from the user apps often make use of local databases in order to save network roundtrips and energy and to be offline usable. Data is synchronized at irregular intervals with the backend database. Hence the user is operating most of the time on a stale snapshot of the data. Additionally enterprise apps usually require concurrent modifications of business critical data. If those are performed on stale snapshots, concurrency anomalies are inevitable. The latter need not, but can lead to severe errors and inconsistent data. At present there is no targeted approach that can be used to determine the set of anomalies that are critical for a particular application. In any case the application must detect those and perform appropriate recovery and conflict resolution steps. These steps might require user interaction, but intuitive UX concepts for conflict resolution and recovery on mobile devices do not exist. The software architect must find a technical solution for conflict detection, resolution and recovery that supports all use cases and workloads of the app, currently by try-and-error. Thus the work of requirements engineers, UX engineers and software architects is highly interdependent and must be closely aligned. Otherwise chances are high that the overall usability of the app is bad. Scientifically the problem was in the past mainly relevant in database systems research. But database research mainly concentrates on finding technical solutions and neglects in particular the usability aspects. From the software engineering point of view there is no targeted engineering approach that aligns the work of requirements engineers, UX engineers and software architects and that leads to the design of effective solutions for mobile data synchronization. The Idea of the PhD is to develop a user story centered engineering approach for the design of mobile data synchronization that aligns the work of requirements engineers, UX engineers and software architects.
Tuesday, 16.02.2016, 11:00 in 48-680
Sebastian Müller: Ensuring Functional Safety for Cooperating Vehicles with Dynamic Safety Contracts
In the automotive domain we have seen a significant paradigm shift for functional safety from federated to integrated E/E architectures. Future scenarios of collaborating autonomous vehicles like platooning will make it necessary to address safety across the classical boundaries of single automotive systems. Therefore, extending the vehicle safety architecture to an open and adaptive one, implies that there is a need for a runtime assessment of safety. To ensure that the current operational situation based on cooperative functionalities is safe, we propose a safety evaluation with dynamic safety contracts. The approach is based on a continuous monitoring, sharing and calculation of safety related quality characteristics of systems at runtime.
Schedule of Summer Term 2015
Tuesday, 21.07.2015, 11:00 in 48-680
Bernd Krolla (DFKI): Heterogenous Reconstruction Approaches for Object and Scene Representation
Performing 3D reconstruction of objects and scenes using digital images as input is a challenging task. To achieve this goal, advanced reconstruction algorithms have to be applied to the images, which need to be capable of recovering camera poses as a precondition to subsequently perform the actual reconstruction process. During the talk, we detail the setup of perspective and spherical Structure from Motion pipelines including the discussion of reliabilities and accuracies of such algorithms. We furthermore present a set of acquired datasets, which serve as benchmark for the evaluation of various heterogeneous reconstruction algorithms. Apart from such Structure from Motion based reconstruction approaches, we finally present Light Field imaging algorithms for 3D reconstruction, which rely on smartphones and spherical cameras.
Max Sagebaum (AG Scientific Computing): Algorithmic Differentiation of an Industrial Turbomachinery Code
We discuss the application of Algorithmic Differentiation (AD) to an industrial turbomachinery code for shape optimization. AD is a method to generate discrete adjoint solvers in a semi-automated fashion. In an industrial framework, the differentiation process needs to be carefully designed to meet certain requirements on computer resources, coding standards and maintenance. Once a first adjoint solver is built in a semi-automated fashion, new developed code parts should be capable to be differentiated automatically and easy to be augmented to the adjoint solver.
Tuesday, 07.07.2015, 11:00 in 48-680
Emanuele D'Osualdo (AG Concurrency Theory): A type system to prove depth-boundedness of concurrent systems
In this talk I will outline my work on verification of concurrent systems. The kind of systems we studied consist of an unbounded collection of dynamically created processes communicating using message passing. Processes have unique identities which are used as addresses for the messages. Process identities can be communicated between processes so the communication network evolves dynamically. To study the problem of algorithmically verifying models where process identities are accurately represented we turn to the depth-bounded pi-calculus introduced by Roland Meyer, which enjoys decidability of some verification problems. The main obstacle in using depth-bounded terms as a target abstract model, is that depth-boundedness of arbitrary pi-terms is undecidable. We introduce a novel type system for the pi-calculus that can prove depth-boundedness statically. The constructions are based on the novel notion of T-compatibility, which imposes a hierarchy between process identities.
Raphael Reitzig (AG Algorithms and Complexity): A Simple and Fast Apportionment Algorithm
Cheng and Eppstein (ISAAC, 2014) describe a linear-time algorithm for computing highest-average allocations in proportional apportionment scenarios, for instance assigning seats to parties in parliament so that the distribution of seats resembles the vote tally as well as possible. We propose another linear-time algorithm that consists of only one call to a rank selection algorithm after elementary preprocessing. Our algorithm is conceptually simpler and faster in practice than the one by Cheng and Eppstein.
Tuesday, 23.06.2015, 11:00 in 48-680
Dennis Christmann(AG VS): ACTP - A Deterministic Binary Countdown Protocol for Wireless Multi-hop Networks
In wireless networks, a usual approach to provide a desired degree of quality-of-service is to apply TDMA-based protocols, where the time is subdivided into time slots that are assigned to nodes exclusively. However, if messages are sent sporadically or even aperiodically, only pessimistic message schedules can be determined with TDMA, resulting in an overbooking and waste of network resources. In the talk, a communication protocol from a protocol family different from TDMA is presented, which forms the basis for quality-of-service in wireless multi-hop networks by performing deterministic and value-based medium arbitration with fixed delay. The protocol is referred to as Arbitrating and Cooperative Transfer Protocol (ACTP) and an instance of a so-called binary countdown protocol, which are very famous in wired networks due to the Controller Area Network (CAN) protocol and enable the collision-resistant transmission of bit sequences. Besides outlining the protocol's mode of operation, details on the implementation and experimental evaluations on wireless sensors nodes are provided.
Johannes Schildgen (AG HIS): NotaQL is not a query language! It's for data Transformations of Wide-Column Stores
It is simple to query a relational database because all columns of the tables are known and the language SQL is easily applicable. In NoSQL, there usually is no fixed schema and no query language. We present NotaQL, a data-transformation language for wide-column stores. NotaQL is easy to use and powerful. Many MapReduce algorithms like filtering, grouping, aggregation and even breadth-first-search, PageRank and other graph and text algorithms can be expressed in two or three short lines of code.
Tuesday, 26.05.2015, 11:00 in 48-680
Sude Tavassoli (AG Prof. Zweig): Identification of influential nodes in temporal multi-networks
In complex network studies, centrality indices are mainly used to quantify the importance of nodes in order to identify the major structural center or the most influential individual in a group. Chat-log data is a rich source for exploring the dynamics associated with the interactions of individual group members. Since the data contains a time stamp for each submitted statement, it can be represented as a temporal multi-network. In the deduced network, the activity of a member can be assessed using different centrality measures. However, the data per se contains more information that is not representable in any network representation (neither temporal nor the aggregated one). In this talk, I will present how the activity centrality of nodes in multi-networks can be analyzed, given additional features and opposing criteria using a fuzzy operator.
Tuesday, 12.05.2015, 11:00 in 48-680
Malte Brunnlieb (AG Softech): Architecture Implementation Patterns for Incremental Code Generation
Reference Architectures have been established in many domains of software engineering enabling reuse of expert knowledge of design, guidelines and much more. Nevertheless, reference architectures might also lead to additional boilerplate code and often occurring implementation needs. This work addresses the need of re-usability and generation needs on the code level in a pattern-based style. Therefore, patterns will be enriched by solution implementation details to enable generation of pattern solutions. To gain from the modularized structure of patterns already occurring in architecture descriptions, we introduce incremental generation blurring the line between architecture and code. The resulting AIM pattern representation enables seamless generation on the basis of strict code conventions.
Tuesday, 28.04.2015, 11:00 in 48-680
Damian Borth (AG Dengel): Large-scale Visual Sentiment Ontology and Detectors Using Adjective Noun Pairs
We address the challenge of sentiment analysis from visual content. We propose a novel approach based on understanding of the visual concepts that are strongly related to sentiments. Our key contribution is two-fold: first, we present a method built upon psychological theories and web mining to automatically construct a large-scale Visual Sentiment Ontology (VSO) consisting of more than 3,000 Adjective Noun Pairs (ANP). Second, we propose SentiBank, a novel visual concept detector library that can be used to detect the presence of 1,200 ANPs in an image. Experiments on detecting sentiment of image tweets demonstrate improvement in sentiment detection accuracy by an absolute gain up to 13%, when combined with text- based approaches. Additionally, this talk will present recent ANP detection improvements gained by the usage of deep convolutional neural networks (CNNs).
Georgel Calin (AG Concurrency Theory): Lazy TSO Reachability
A new algorithm for state reachability in programs running under Total Store Order (TSO) will be presented. At its heart lays an iterative refinement of the program of interest. On top of standard (SC) reachability checks, the refinement uses oracle queries to introduce the TSO semantics lazily and only where needed. Our algorithm yields an iterative under-approximation that is sound and complete for bug hunting, i.e., a semi-decision procedure halting for positive cases of reachability.
Schedule of Winter Term 2014/15
Tuesday, 18.11.2014, 11:00 in 48-680
Michael Arndt (AG Robotics Research): "Safe and cost-efficient Robot Navigation in Smart Environments"
The world surrounding us is becoming increasingly "smart" and aware, due to the amount of sensors we keep embedding into it. Michael will provide an overview about how robotics can make clever use of this data to realize safer and also more cost-efficient mobile robots.
Jörn Hees (AG Knowledge-based Systems): "Learning Human Association Patterns from the Web of Data"
Today, machines can solve incredibly complex tasks using semantically enriched data. Nevertheless, they don't think like humans. In his research Jörn focuses on the human association process and teaches machines to learn patterns for associations from the Linked Data Graph.
Tuesday, 02.12.2014, 11:30 in 48-680 (half an hour later this time!)
Daniel Berger (AG disco): "Content Delivery and Denial of Service on the Internet"
How is that favorite website of yours delivered to your browser? Today's Internet achieves fast delivery times through a distributed caching network, which keeps popular content in close proximity to web users. This talk introduces two elementary questions on the placement of these caches and on their role in protecting against denial of service attacks.
Prof. Roland Meyer (AG Concurrency Theory): "Robustness against Relaxed Memory Models"
For performance reasons, modern multiprocessors implement relaxed memory consistency models that admit out-of-program-order and non-store atomic executions.
While data race-free programs are not sensitive to these relaxations, they pose a serious problem to the development of the underlying concurrency libraries.
Library routines that work correctly under Sequential Consistency (SC) show undesirable effects when run under a relaxed memory model.
These routines are not robust against the relaxations that the processor supports.
To enforce robustness, the programmer has to add safety net instructions to the code that control the hardware --- a task that has proven to be difficult, even for experts.
We recently developed algorithms that check and, if necessary, enforce robustness against prominent relaxed memory models like TSO implemented in x86 processors and Power implemented in IBM architectures. Given a program, our algorithms decide whether the actual behavior on the processor coincides with the SC semantics. If this is not the case, they synthesize safety net instructions that enforce robustness. When built into a compiler, our algorithms thus hide the relaxed memory model from the programmer and provide the illusion of Sequential Consistency.
In this talk, we motivate the robustness problem and explain how to reduce it to a standard SC reachability query.
Tuesday 16.12.2014, 11:30 in 48-680
Peter Treiber (AG Network Analysis and Graph Theory): "Deriving topological data from temporal adjacency data"
More and more people own and use modern smartphones. The development of such mobile phones improves. The embedded sensors get better, more sensors are embedded. These sensors can be used to gather more and more data. The analysis of such data is therefore a growing field. Not only in computer science, which developes new techniques for such research, but also in different sciences, for instance in sociolgy, such analyses are used to gain new insights. Often used data is GPS-data, which allows a relatively good localisation. Indoors however, GPS-data is quite inaccurate. It might even be the case, that no signals can be recieved from GPS-satellites. Therefore, bluetooth data is also used. Such data builds temporal adjacency data. Can one use such data to derive in a building with unknown topology this topology? To this end, I present the matrix-exchange-algorithm. For a special case the correctness is prooven. Afterwards, the algorithm is applied on further cases and the results are analysed.
Tuesday 13.01.2015, 11:00 in 48-680
Matthias Schaefer (AG disco): "Fasten Your Seatbelts: Security in Next Generation Air Traffic Communication
Technologies used to provide situational awareness to air traffic controllers and pilots date back to World War II. They are outdated and do not meet the current needs of the ever increasing traffic density in terms of accuracy and performance. Therefore, aviation authorities all over the world were forced to do a major upgrade until 2020. Right now, they are implementing this so called next generation air transportation system (NextGen). However, the communication standards that will be used in NextGen have major security issues. A modern attacker can easily manipulate the recognized air picture of pilots, collision avoidance systems, and air traffic controllers with low-cost commmercial off-the-shelf hardware. Decisions based on this manipulated view can heave severe, even life threatening consequences. In this talk, Matthias presents the findings of his security analysis. In addition, he also discusses the challenges of defeating these attacks and possible solutions.
Ilham Kurnia (AG Sofware technology): "Modeling Actor Systems Using Dynamic I/O Automata"
The actor model is an object-based framework that provides the basic elements for designing and implementing open distributed systems. The primitive elements of systems in this model are actors, where interaction can happen through asynchronous message passing and the creation of new actors. To allow reasoning of the functional behavior at many different levels of abstraction, there needs to be a representation of groups of actors. In this talk, I introduce an adaptation of Dynamic I/O Automata -- an extension of I/O Automata that captures dynamic creation of automata -- as the representation. It is suitable for bridging verification techniques tailored for actor systems at the implementation and the system levels.
Tuesday 27.01.2015, 11:00 in 48-680
Steffen Bondorf (AG disco): "Worst-Case Performance Analysis with Network Calculus"
Network calculus can derive worst-case bounds on performance metrics in communication networks. That is, the end-to-end delay experienced by a flow as well as the buffer requirement of the crossed servers. This knowledge proved to be useful for different purposes where determinism is key, e.g., in the certification of the AFDX (Avionics Full-Duplex Switched Ethernet) backbone of aircraft. In his talk, Steffen will present the foundations of worst-case performance analysis with network calculus and depict his recent work in the field.
Tuesday 10.02.2015, 11:00 in 48-680
Hadil Abukwaik (AG Software Engineering: Processes and Measurement): "A Proactive Support for Conceptual Interoperability in Software Systems"
Successfully integrating a software system with another existing one requires, beyond technical mismatches, identifying and resolving conceptual mismatches that might result in worthless integration and costly rework. Often, not all relevant architectural information about the system to integrate with is publicly available, as it is hidden in internal architectural documents and not exposed in the public API documentation. Thus, we propose a framework of conceptual interoperability information which a system’s architect can use to semi-automatically extract interoperability-relevant parts from his architecture and lower-level design documentation and publish it in a standardized and formalized way. The goal is to keep the additional effort for providing the interoperability-relevant information as low as possible and to encourage architects to provide it proactively.
Yong Hu (AG Heterogenous Information Systems): "Incremental recomputation in column-oriented NoSQL database systems"
Column-oriented NoSQL databases (CoNoSQLDBs) manage tremendous data in a distributed way. The data which belong to the same column are stored contiguously on disk. Frequently, data analysis against the CoNoSQLDB tables will be periodically repeated and the states of source tables vary over time. In this talk, I will introduce and explain how to incrementally recompute the data analysis results with respect to the change data in the context of CoNoSQLDBs.
Tuesday 24.02.2015, 11:00 in 48-680
Sheraz Ahmed (Pattern Recognition Group): "Information segmentation in document images"
A document image contains different types of information. This includes text (handwritten/machine printed), graphics, signatures, stamps, etc. To automatically analyze document images, it is therefore necessary to first segment different types of information so that they can be used only when they are required. In Sheraz' research, the goal is to develop different methods capable of segmenting different types of information from document images. The core of the proposed methods lies in the use of part-based features for information segmentation. The proposed methods are tested on different types of documents including technical drawings, administrative documents, and camera captured documents, where they outperformed state-of-the-art methods.
Tim Biedert (Computational Topology Group): "Topology-Controlled Layered Depth Imaging"
Due to the modern architectural trade-offs in large-scale parallel computer clusters, numerical data by high-fidelity simulation models can be produced at tremendous computational throughput, but cannot be persistently stored in its entirety to the slow I/O subsystem. In his talk, Tim will present his recent work on combining topologically-guided in-situ data simplification and image-based storage to tackle this problem while preserving a significant amount of flexibility in analysis and exploration.
Tuesday 10.03.2015, 11:00 in 48-680
Annette Bieniusa (softech): Scalable consistency in distributed systems
Replicating modifiable data is a challenge in large-scale distributed systems, as it suffers from a fundamental tension between availability and data consistency. Eventual consistency sidesteps the problem of availability under network partitioning, but remains ad-hoc, error-prone, and difficult to apply for programmers. In her talk, Annette will introduce a new approach to shared, mutable and replicated data: conflict-free replicated data types (CRDTs). Complying to simple properties, namely commutativity of concurrent updates or inflations of object states in a semi-lattice, CRDTs provably converge without requiring synchronization operations.
Christopher Kramer (AG VS): Automatic Topology Discovery of Wireless Networks for the Smart Factory
Todays "smart factories" embed an increasing number of sensors in the production line. Wireless communication systems enable more such sensors and make their deployment easier and cheaper. To use such networks efficiently while meeting the high reliability requirements, topology information is needed. This talk presents a protocol that automatically detects the networks communication, interference and sensing topology.
Tuesday 24.03.2015, 11:00 in 48-680
Sebastian Wild (AG Nebel): Dual-Pivot Quicksort
One might think that computer science's solutions to its most basic problems ought to be settled by now; something elementary as sorting should be 'done' ... but this is not quite true: within the last decade, *all* sorting algorithms in the Java runtime library have been entirely rewritten! I will introduce to you the new dual-pivot Quicksort that is nowadays used to sort arrays of primitive types in Java. I will present some analytical facts about this algorithm that offer a possible (and, I think, plausible!) explanation why (a) dual-pivot Quicksort is faster than the previously used (classic) Quicksort and (b) why this basic improvement was not already found much earlier. In passing, I will sketch the intuition behind some of my favorite mathematical tools for the analysis of algorithms (while avoiding technical details).
Wolfgang Schlauch (AG Zweig): Different Flavors of Randomness
Nowadays, almost everybody is connected to any kind of online social network. Social Network Analysis tries to find important people, bottlenecks, or groups by applying algorithms and measures to a network. Similar approaches can be found in other fields that are concerned with data representable as a graph or network. In this talk some of the (common) pitfalls of network analytic methods are presented.