Dijkstra, Floyd and Warshall meet Kleene

Around 1960, Dijkstra, Floyd and Warshall published papers on algorithms for solving single-source and all-sources shortest path problems, respectively. These algorithms, nowadays named after their inventors, are well known and well established. This paper sheds an algebraic light on these algorithms. We combine the shortest path problems with Kleene algebra, also known as Conway’s regular algebra. This view yields a purely algebraic version of Dijkstra’s shortest path algorithm and the one by Floyd/Warshall. Moreover, the algebraic abstraction yields applications of these algorithms to structures different from graphs and pinpoints the mathematical requirements on the underlying cost algebra that ensure their correctness.     

HybMig: A Hybrid Approach to Dynamic Plan Migration for Continuous Queries

In data stream environments, the initial plan of a long-running query may gradually become inefficient due to changes of the data characteristics. In this case, the query optimizer generates a more efficient plan based on the current statistics. The online transition from the old to the new plan is called dynamic plan migration. In addition to correctness, an effective technique for dynamic plan migration should achieve the following objectives: 1) minimize the memory and CPU overhead of the migration, 2) reduce the duration of the transition, and 3) maintain a steady output rate. The only known solutions for this problem are the moving states (MS) and parallel track (PT) strategies, which have some serious shortcomings related to the above objectives. Motivated by these shortcomings, we first propose HybMig, which combines the merits of MS and PT and outperforms both in every aspect. As a second step, we extend PT, MS, and HybMig to the general problem of migration, where both the new and the old plans are treated as black boxes     

On‐the‐fly generation and rendering of infinite cities on the GPU

In this paper, we present a new approach for shape‐grammar‐based generation and rendering of huge cities in real‐time on the graphics processing unit (GPU). Traditional approaches rely on evaluating a shape grammar and storing the geometry produced as a preprocessing step. During rendering, the pregenerated data is then streamed to the GPU. By interweaving generation and rendering, we overcome the problems and limitations of streaming pregenerated data. Using our methods of visibility pruning and adaptive level of detail, we are able to dynamically generate only the geometry needed to render the current view in real‐time directly on the GPU. We also present a robust and efficient way to dynamically update a scene's derivation tree and geometry, enabling us to exploit frame‐to‐frame coherence. Our combined generation and rendering is significantly faster than all previous work. For detailed scenes, we are capable of generating geometry more rapidly than even just copying pregenerated data from main memory, enabling us to render cities with thousands of buildings at up to 100 frames per second, even with the camera moving at supersonic speed.     

The physiological mirror—a system for unconscious control of a virtual environment through physiological activity

This paper introduces a system for real-time physiological measurement, analysis, and metaphorical visualization within a virtual environment (VE). Our goal is to develop a method that allows humans to unconsciously relate to parts of an environment more strongly than to others, purely induced by their own physiological responses to the virtual reality (VR) displays. In particular, we exploit heart rate, respiration, and galvanic skin response in order to control the behavior of virtual characters in the VE. Such unconscious processes may become a useful tool for storytelling or assist guiding participants through a sequence of tasks in order to make the application more interesting, e.g., in rehabilitation. We claim that anchoring of subjective bodily states to a virtual reality (VR) can enhance a person’s sense of realism of the VR and ultimately create a stronger relationship between humans and the VR.     

Robust Cardiac Function Assessment in 4D PC‐MRI Data of the Aorta and Pulmonary Artery

Four‐dimensional phase‐contrast magnetic resonance imaging (4D PC‐MRI) allows the non‐invasive acquisition of time‐resolved, 3D blood flow information. Stroke volumes (SVs) and regurgitation fractions (RFs) are two of the main measures to assess the cardiac function and severity of valvular pathologies. The flow rates in forward and backward direction through a plane above the aortic or pulmonary valve are required for their quantification. Unfortunately, the calculations are highly sensitive towards the plane's angulation since orthogonally passing flow is considered. This often leads to physiologically implausible results. In this work, a robust quantification method is introduced to overcome this problem. Collaborating radiologists and cardiologists were carefully observed while estimating SVs and RFs in various healthy volunteer and patient 4D PC‐MRI data sets with conventional quantification methods, that is, using a single plane above the valve that is freely movable along the centerline. By default it is aligned perpendicular to the vessel's centerline, but free angulation (rotation) is possible. This facilitated the automation of their approach which, in turn, allows to derive statistical information about the plane angulation sensitivity. Moreover, the experts expect a continuous decrease of the blood flow volume along the vessel course. Conventional methods are often unable to produce this behaviour. Thus, we present a procedure to fit a monotonous function that ensures such physiologically plausible results. In addition, this technique was adapted for the usage in branching vessels such as the pulmonary artery. The performed informal evaluation shows the capability of our method to support diagnosis; a parameter evaluation confirms the robustness. Vortex flow was identified as one of the main causes for quantification uncertainties.     

On the relationship between models and ontologies

Software and Systems Modeling -     

Visuelle Analyse medizinischer Daten

In der Medizin werden gro?e Mengen an Daten generiert, die sich auf diagnostische Prozeduren, Behandlungsentscheidungen und Ergebnisse der Behandlung beziehen. Medizinische Bilddaten, z. B. Computertomografie (CT) und Kernspintomografiedaten (MRT), werden h?ufig akquiriert. Diese Daten müssen effizient analysiert werden, um klinische Entscheidungen ad?quat zu unterstützen. Insbesondere müssen Bildanalysetechniken, wie die Segmentierung und Quantifizierung anatomischer Strukturen und die visuelle Exploration der Daten, integriert werden. Neben den Anforderungen der individuellen Behandlung ergeben sich weitere Herausforderungen für die Datenauswertung aus den Bedürfnissen der klinischen Forschung, der ?ffentlichen Gesundheitsvorsorge und der Epidemiologie. Die Rolle des Benutzers ist hier die eines Forschers, der Daten untersucht und dabei z. B. potenzielle Korrelationen zwischen Risikofaktoren und der Entstehung von Erkrankungen analysiert. Die visuelle Exploration, bei der oft mehrere koordinierte Ansichten genutzt werden, und statistische Analysen müssen dazu geeignet integriert werden. Oft sind dabei die r?umliche (geografische) Verteilung der Patienten und die zeitliche Entwicklung von Erkrankungsf?llen wesentlich. Daher müssen die medizinischen Daten in ihrem r?umlichen und zeitlichen Bezug repr?sentiert werden, sodass eine enge Verbindung zwischen geografischen Informationssystemen und der Datenvisualisierung entsteht.