Campus Event Calendar
Event Entry
New for: D1, D2
What and Who
Ein generisches Verfahren zum schnellen Aufbau von Indexstrukturen
Professor Dr. Bernhard Seeger
Universität Marburg
Informatik-Kolloquium
AG 1, AG 2
AG Audience
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 21 November 97
15:00
-- Not specified --
45 - FB14
001
Saarbrücken
Abstract
In diesem Vortrag betrachten wir das Problem, zu einer gegebenen Menge
von Datensätzen eine neue externe Indexstruktur aufzubauen. Dabei gehen
wir davon aus, daß aufgrund des hohen Datenvolumens ein kompletter
Aufbau im Hauptspeicher nicht möglich ist. Diese Problemstellung tritt
insbesondere in großen Datenbanken auf. Es wird ein neues Verfahren zum
Aufbau von Indexstrukturen vorgestellt, das im Unterschied zu anderen
Verfahren auf eine Klasse von Strukturen anwendbar ist. In dieser Klasse
befinden sich klassische Indexstrukturen wie der B+-Baum, aber auch
mehrdimensionale und räumliche Indexstrukturen wie der R-Baum. Das
generische Verfahren basiert nicht auf externen Sortierverfahren (wie z.
B. Verfahren zum Aufbau von B+-Bäumen), sondern partitioniert die Daten
mittels der Routinen, die in der aufzubauenden Indexstruktur bereits
vollständig implementiert sind. Für Indexstrukturen, die über eine
effiziente Routine zum Einfügen eines Datensatzes verfügen, kann gezeigt
werden, daß die Laufzeit des Verfahrens im worst-case asymptotisch
von Datensätzen eine neue externe Indexstruktur aufzubauen. Dabei gehen
wir davon aus, daß aufgrund des hohen Datenvolumens ein kompletter
Aufbau im Hauptspeicher nicht möglich ist. Diese Problemstellung tritt
insbesondere in großen Datenbanken auf. Es wird ein neues Verfahren zum
Aufbau von Indexstrukturen vorgestellt, das im Unterschied zu anderen
Verfahren auf eine Klasse von Strukturen anwendbar ist. In dieser Klasse
befinden sich klassische Indexstrukturen wie der B+-Baum, aber auch
mehrdimensionale und räumliche Indexstrukturen wie der R-Baum. Das
generische Verfahren basiert nicht auf externen Sortierverfahren (wie z.
B. Verfahren zum Aufbau von B+-Bäumen), sondern partitioniert die Daten
mittels der Routinen, die in der aufzubauenden Indexstruktur bereits
vollständig implementiert sind. Für Indexstrukturen, die über eine
effiziente Routine zum Einfügen eines Datensatzes verfügen, kann gezeigt
werden, daß die Laufzeit des Verfahrens im worst-case asymptotisch
optimal ist. Experimente mit einer Implementierung unseres Verfahrens
geben auch erste Hinweise auf die durchschnittliche Leistungsfähigkeit.
Contact
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Interessenten sind zum Vortrag herzlich eingeladen.
Die Dozenten des Fachbereichs Informatik
Die Kolloquiumsankündigungen können auch unter http://www.cs.uni-sb.de/kolloquien/ gelesen werden.
Die Dozenten des Fachbereichs Informatik
Die Kolloquiumsankündigungen können auch unter http://www.cs.uni-sb.de/kolloquien/ gelesen werden.
Uwe Brahm, 04/12/2007 12:32 -- Created document.