Universität Bielefeld - Technische Fakultät - AG Genominformatik

Seminar -Raumbasierte Indexstrukturen

Vorlesung im Wintersemester 2003/2004

Dienstag, 10:15-12:00 Uhr , E01-108 (bis zum 4.11.2003)

Die Vortragsreihen werden im Block abgehalten:

Samstag, 10.01.2004, 9:15-18:00 Uhr ; Raum V4-106
Samstag, 17.01.2004, 9:15-18:00 Uhr ; Raum V4-106

Klaus-Bernd Schürmann, Jens Stoye

Inhalt:

Es gibt wesentliche Unterschiede zwischen traditionellen Datenbanken und Datenbanken, die mehrdimensionale Objekte speichern, wie Multimedia- und Geographische Datenbanken. Diese Unterschiede spiegeln sich auch in den Datenbank-Anfragen wieder. Bei einer häufigen Multimedia-Datenbankanfrage geht es um das Finden einer Menge der Datenbankobjekte, die mit einem vorgegebenen Objekt möglichst gut übereinstimmen. Zum Beispiel wenn die Objekte Bilder sind, sucht man die Menge der Bilder, die zu dem Anfrage-Bild am ähnlichsten sind.
Andererseits sucht man in geographischen Datenbanken nach Objekten, die in einem bestimmten Bereich liegen, z.B. alle Kneipen in meinem Stadtbezirk. Um die Bearbeitung der Anfragen effizienter zu machen, werden raumbasiert Indexstrukturen wie Gridfiles, KD-Bäume und R-Bäume eingesetzt. Im Mittelpunkt des Interesses stehen bei dem Thema: mehrdimensionale Daten, sowie Datenstrukturen und Algorithmen zur Auswertung von Anfragen auf mehrdimensionalen Daten.

Themen:

Einführung:

Vortragstechnik

Wissenschaftliches Schreiben

Einführung Graphentheoretischer Grundlagen und Datenstrukturen, Baumrepresentation

Martin Aigner; Diskrete Mathematik ; Vieweg 1996, Kapitel 4+5.
T. H. Cormen, C. E. Leiserson, R. L. Rivest; Introduction to Algorithms ; MIT Press 1990.

Indizierung von Daten eines eindimensionalen Zahlenraumes

B-Baum. B*-Baum, Hashindex (mit Bezug auf Nearest-Neighbour und Range-Queries)

T. H. Cormen, C. E. Leiserson, R. L. Rivest; Introduction to Algorithms ; MIT Press 1990.

Einführung Multimediadaten

Banu Özden, Rajeev Rastogi, Avi Silberschatz ; Multimedia Support for Databases ; ACM 1997
C. Faloutsos, K.-I. Lin; A Fast Algorithm for Indexing, Data-Mining and Vizualization of Traditional and Multimedia Datasets ; ACM SIGMOD 1995, p. 163-174

Indizierung von Daten reeller mehrdimensionaler Räume

Grid-Files, Partitioned-Hashing
KD-Bäume und Quad-Trees

A. Moore; A Tutorial on KD-Trees ; University of Cambridge Computer Laboratory, Technical Report No. 209.
Hanan Samet; The Quadtree and Related Hierarchical Data Structure ; ACM Computing Surveys, Vol. 16, No. 2

R-Bäume, R+-Bäume und R*-Bäume

A. Guttman: " R-trees: A Dynamic Index Structure for Spatial Searching ". Proceedings of SIGMOD, 1984.
T. Sellis, N. Roussopoulos, C. Faloutsos: " The R+-tree: A Dynamic Index for Multi-dimensional Objects ". Proceedings of VLDB, 1987.
N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger: " The R*-tree: An Efficient and Robust Access Method for Points and Rectangles ". Proceedings of SIGMOD, 1990

Indizierung von Daten eines metrischen Raums

X-Trees

S. Berchtold, D.A. Keim, H.-P. Kriegel; The X-Tree: An Index Structure for High-Dimensional Data ; Proc. of the 22rd VLDB Conference, p. 28-39; 1996.

M-Tree

P.Ciaccia, M. Patella, P. Zezula; M-Tree: An Efficient Access Method for Similarity Search in Metric Spaces ; Proc. of the 23rd VLDB Conference, p. 426-435; 1997.

Vantage-Point-Trees

T. Bozkaya, M. Ozsoyoglu; Indexing Large Metric Spaces for Similarity Search Queries ; ACM Transactions on Database Systems, Vol. 24, No. 3, p. 361-404; 1999.

Spatial Approximation

G. Navarro; Searching in metric spaces by spatial approximation; VLDB Journal Vol. 11(1), p. 28-46; 2002.

Anfragen in Multimediadatenbanken

Ronald Fagin; Fuzzy Queries in Multimedia Database Systems ; ACM 1998.