Search

The widespread use of digital sensor systems causes a tremendous demand for high-quality time series analysis tools. In this domain the majority of data mining algorithms relies on established distance measures like Dynamic Time Warping (DTW) or Euclidean distance (ED). However, the notion of similarity induced by ED and DTW may lead to unsatisfactory clusterings. In order to address this shortcoming we introduce the Gliding Elastic Match (GEM) algorithm. It determines an optimal local similarity measure of a query time series Q and a subject time series S. The measure is invariant under both local deformation on the measurement-axis and scaling in the time domain. GEM is compared to ED and (un)constrained DTW in terms of matching quality for several datasets and outperforms the competitors in most cases. In order to accelerate the application of GEM to large-scale datasets, we further present an efficient CUDA parallelization.

The alignment of noisy and uniformly scaled time series is an important but difficult task. Given two time series, one of which is a uniformly stretched subsequence of the other, we want to determine the stretching factor and the offset of the second time series within the first one. We adapted and enhanced different methods to address this problem: classical FFT-based approaches to determine the offset combined with a naive search for the stretching factor or its direct computation in the frequency domain, bounded dynamic time warping and a new approach called shotgun analysis, which is inspired by sequencing and reassembling of genomes in bioinformatics. We thoroughly examined the strengths and weaknesses of the different methods on synthetic and real data sets. The FFT-based approaches are very accurate on high quality data, the shotgun approach is especially suitable for data with outliers. Dynamic time warping is a candidate for non-linear stretching or compression. We successfully applied the presented methods to identify steel coils via their thickness profiles.

Graph grammars, especially when enriched with attributes, can be used as a powerful software engineering technique. The main idea behind this approach is: A problem domain is modelled by a graph, the representation graph, whose nodes correspond to the objects of the domain and whose edges to the relations between the objects, respectively. Typical operations which normally change the structure of the representation graph, like introducing new objects at a certain state of the problem description, or modifying relations between objects, are expressed by graph productions. Quantitative informations are handled by the attributes attached to the nodes of the representation graph. So, the implementation aspects are reduced to a very general and flexible data structure, namely graphs.

This paper presents a formalization of the notion graphic. A graphic is considered to consist of an ordinary graph describing the overall structure and a set of attributes describing the shape, placement, etc. of the nodes and edges of the underlying graph. The formal handling of graphics is done by attributing the rules of graph grammars and by passing the attributes up and down the derivation tree of the graphic.

Ziel von PRISMA (Picture Retrieval and Information System for Modern Arts) ist es, auf verschiedenen Rechnem und heterogenen Inform ationssystemen verteilte, komplex strukturierte Multimediadaten and Metainformationen unter einer einheitlichen, anwenderfreundlichen Benutzeroberflache mit Hilfe einer verteilten objektorientierten Datenbank zu verwalten. Zur Realisierung dieses Konzeptes werden Schnittstellen und Protokolle entwickelt, die z.B. die Kommunikation zwischen einem WWW-Server und der von PRISMA verwendeten objektorientierten Datenbank ermoglichen. Durch den Einsatz von WWW-Browsern als Bedienoberflache des Systems wird eine weitgehende Plattformunabhadngigkeit erreicht. Die Datenabfrage and die Datenmanipulation werden uber Formulare in Form von HTML-Seiten realisiert. Ebenso werden Rechercheergebnisse in dynamisch generierte HTML-Seiten verpackt. Eine den individuellen Wunschen der Benutzer gemase Darstellung der Anfrageergebnisse und die vom verwendeten Datenbanksystem unabhangige Reprasentation der Datenbankobjekte ist ein zentraler Forschungsgegenstand des PRISMAProjektes. Weitere PRISMA-Module sind ein Analyse- and Strukturierungswerkzeug fur HTML-Seiten, Bowie ein graphenbasiertes Tool zur Modellierung von individuellen Benutzerschnittstellen. Die Entwicklungen fanden im Rahmen einer kunsttheoretischen Untersuchung uber den Kubismus statt.

Dieses Kapitel behandelt verschiedene Anwendungen, die Zeugnis geben sollen, das man mit der Graphtechnologie und NAGGImp auch Probleme angehen kann, die den Schwierigkeitsgrad des Fibonacci-Diagramm-Beispiels wesentlich ubersteigen.

This paper reports on an ongoing work which started in 1981 and is aiming at developing a general, computer-aided method which would help to considerably reduce the time necessary to develop a syntax-directed editor for any given diagram technique.

Zu Beginn der Arbeiten uber programmierte attributierte Graphgrammatiken wurden zwei Fernziele festgelegt.

In diesem Kapitel wird erlautert, warum der Softwareent-wicklungsprozes als eine Folge von Modell-Transformationen gesehen werden kann. In der Istanalyse wird mit der Erarbeitung des ersten Modells eines zu automatisierenden Systems begonnen. Dieses Modell wird immer weiter umgeformt, verfeinert, prazisiert, bis es schlieslich als ablauffahiges Programm vorliegt.

Marktanalysen erweisen, das kommerzielle Textverarbeitungssysteme viele Funktionen besitzen, die in einer Kanzlei nicht gebrauoht werden (etwa Formatsteuerungen), aber unbefriedigend beim Umgang mit Textbausteinen sind. Diese Arbeit will zeigen, wie einfache Grundkenntnisse aus der Berechenbarkeitstheorie und auch SIMULA-Klassen wertvolle Anregungen fur die Gestaltung eines klaren Konzepts fur die Textbausteinverarbeitung geben konnen, das in gewissem Sinn universell ist: Es mus erlauben, das Textbausteine andere sequentiell, iterativ sowie selektiv — und dies beliebig geschachtelt — aufrufen durfen. Auserdem mus die Ausfuhrung arithmetischer Operationen mit den in den Textbausteinen auftretenden Variablen moglich sein. In der Arbeit wird auch noch kurz auf die Implementierung eingegangen.

Die Vorstellung der theoretischen Grundlagen fur die Manipulation von Graphen begann mit „Graphgrammatiken“. Dann folgte deren „Attributierung“ und schlieslich die „Programmierung“. Wie die Abschnitte dieses Kapitels zeigen werden, spiegelt die Reihenfolge auch die Vorgehensweise beim praktischen Einsatz von programmierten attributierten Graphgrammatiken wider.