http://dl.gi.de/handle/20.500.12116/4400 2026-07-21T14:05:37Z http://dl.gi.de/handle/20.500.12116/4508 Hochdimensionale Indexierung: Formale Grundsätze und neue Ansätze Balko, Sören Wagner, Dorothea Multimediale Dokumentenkollektionen finden in vielen IT-Bereichen zunehmende Verbreitung. Die Handhabung großer Datenbestände erfordert effiziente Suchoperationen, die es erlauben, Medienobjekte in akzeptablen Zeiten aufzufinden. Darunter fallen auch inhaltsbasierte Anfragen. Häufig werden charakteristische Ei- genschaften auf mehrdimensionale Merkmalsvektoren abgebildet, deren Distanz als ein Maß für die (Un-) Ähnlichkeit der repräsentierten Medienobjekte aufgefasst wird. Im Datenbankenkontext bilden geeignete Indexstrukturen und Suchalgorithmen die elementare Voraussetzung für eine effiziente Anfragebearbeitung. In diesem Beitrag stellen wir Ergebnisse aus [Bal04] dar und beschäftigen uns mit (1) den formalen Grundlagen hochdimensionaler Indexierung, (2) der Einführung eines adaptiven Indexierungsschemas, (3) Fragen des Index-Tunings auf der Grundlage eines analytischen Kostenmodells und (4) dem experimentellen Vergleich konkurrierender Indexierungsvorschläge. Im Vorgriff auf die folgende Darstellung dieser Beiträge ist es gelungen, eine neue Indexierungsmethode zu entwickeln, die bei der An- fragebearbeitung deutliche Kostenvorteile gegenüber bestehenden Ansätzen erzielt. 2005-01-01T00:00:00Z http://dl.gi.de/handle/20.500.12116/4506 Über die Analyse randomisierter Suchheuristiken und den Entwurf spezialisierter Algorithmen im Bereich der kombinatorischen Optimierung Witt, Carsten Wagner, Dorothea Dieser Beitrag ist eine Zusammenfassung der gleichnamigen Dissertation. Der Schwerpunkt der Arbeit liegt auf der theoretischen Analyse randomisierter Suchheuristiken wie evolutionärer Algorithmen, insbesondere in Bezug auf ihre Laufzeit bei der Lösung kombinatorischer Optimierungsprobleme. Neben einfachen randomisierten Suchheuristiken, die zu jedem Zeitpunkt nur einen Suchpunkt betrachten, werden auch evolutionäre Algorithmen mit größeren Populationen untersucht. Dabei werden jeweils neue und allgemeine Methoden zur Analyse randomisierter Suchheuristiken entwickelt. Abschließend wird ein spezialisierter Algorithmus für ein aktuelles kombinatorisches Optimierungsproblem vorgestellt. 2005-01-01T00:00:00Z http://dl.gi.de/handle/20.500.12116/4507 Radiale Level-Planarität und -Einbettung in Linearzeit Bachmeier, Christian Wagner, Dorothea Ein Graph mit einer geordneten k-Partitionierung seiner Knoten ist radial level-planar, wenn es eine strikte Auswärtszeichnung auf k konzentrische Kreise ohne Kreuzungen gibt. Radiale Level-Planarität ist eine Erweiterung von Level-Planarität, bei der die Knoten auf k horizontalen Linien und die Kanten strikt nach unten ohne Kreuzungen gezeichnet werden. Kennzeichnend für die Erweiterung sind Ringe, d. h. nicht level-planare zweifache Zusammenhangskomponenten. Unsere Hauptergebnisse sind Linearzeitalgorithmen zum Test auf radiale Level- Planarität und zur Berechnung einer Einbettung. Wir führen die Datenstruktur PQR- Baum ein, bei der die neuen R-Knoten und die dazugehörigen Templates für die korrekte Behandlung von Ringen sorgen. Unsere Algorithmen sind daher eine Erweiterung von hoch entwickelten Level-Planaritätsund -Einbettungs-Algorithmen auf Ba- sis von PQ-Bäumen. 2005-01-01T00:00:00Z http://dl.gi.de/handle/20.500.12116/4512 Automatenbasierte Entscheidungsverfahren für Teilsysteme der Arithmetik Klaedtke, Felix Wagner, Dorothea Vor ungefähr vierzig Jahren wurde entdeckt, dass Automaten ein nützliches mathematisches Werkzeug sind, um die Entscheidbarkeit bestimmter Teilsysteme der Arithmetik zu verstehen. Heutzutage werden Automaten auch als Werkzeug eingesetzt, um Entscheidungsverfahren für eben solche logischen Theorien umzusetzen. Meine Dissertation behandelt Fragestellungen aus eben diesem Bereich zwischen Automatentheorie und Logik. Ziel dieses Artikels ist es, Einblicke in diesen Themenbereich zu geben und die Beiträge meiner Dissertation zu beschreiben. 2005-01-01T00:00:00Z