Institut für Informatik III
Universität Bonn

Datenbanken * Informationssysteme * Softwaretechnologie * Computergrafik * Mustererkennung * Bildverarbeitung * Künstliche Intelligenz * Robotik 

 Proseminar Indexstrukturen für Datenbanken 
(Wintersemester 2002/2003)

      INDEX:   Ansprechpartner   Informationen  Themen   Termine   Literatur   Links

Ansprechpartner

Informationen zum Seminar

Beschreibung: Aufgrund ihrer vielen Vorteile sind moderne Datenbanksysteme ein wichtiges Werkzeug bei der Realisierung komplexer Anwendungssysteme. Eine wesentliche Eigenschaft dieser Systeme ist ihre Fähigkeit auch auf sehr großen Datenbeständen Suchoperationen effizient auszuführen. Grundlage solcher Anfrageoperationen sind hierzu speziell entwickelte Datenstrukturen die sogenannten Indexstrukturen. Dabei kann natürlich nicht länger davon ausgegangen werden, daß sich sämtliche relevanten Daten im Hauptspeicher befinden. Somit müssen die bei einer Such- oder Sortieroperation anfallenden Sekundärspeicherzugriffe explizit berücksichtigt bzw. minimiert werden.

Zeit und Ort: Montags 15 - 17 Uhr c.t., Seminarraum A121

Beginn: 14.10.2002

Vortragsmodus: Einzelvortrag mit vorhergehender schriftlicher Ausarbeitung

Vortragsthemen und Zeitplan

Bitte beachten Sie die angegebenen Fristen!

Termine:

Termin für die Gliederung: ca. 6 Wochen vor dem Vortragstermin

Abgabe der Ausarbeitung spätestens 3 besser 4 Wochen vor dem Vortragtermin

Überarbeitete Ausarbeitung, Folienentwürfe spätestens 1 Woche vor dem Vortragstermin

Diese Fristen sind unbedingt einzuhalten!

Literatur

[Bayer96] Rudolf Bayer: The Universal B-Tree for multidimensional Indexing.
Technical Report TUM-I9637,November 1996.
[Bayer77] Rudolf Bayer, Karl Unterauer: Prefix B-Trees. TODS 2(1): 11-26 (1977)
[Bayer97] Rudolf Bayer: The Universal B-Tree for Multidimensional Indexing: general Concepts. WWCA 1997: 198-209
[BeKeKr96] Stefan Berchtold; Daniel A. Keim; Hans-Peter Kriegel: The X-tree : An Index Structure for High-Dimensional Data. In [VLDB96], pages 28-39, 1996.
[BeKrSS90] Norbert Beckmann; Hans-Peter Kriegel; Ralf Schneider; Bernhard Seeger: The R*-Tree:  An Efficient and Robust Access Method for Points and Rectangles. In [SIGMOD90], pages 322-331, 1990.
[Comer79] Douglas Comer: The Ubiquitous B-Tree. ACM Computing Surveys, 11:2., pages 121-137, June 1979.
[FaNiPS79] Ronald Fagin; Jürg Nievergelt; Nicholas Pippenger; H. Raymond Strong: Extendible Hashing -  A Fast Access Method for Dynamic Files. ACM Transactions on Database Systems (TODS), 4:3., pages 315-344, September 1979.
[FraBae92] William B. Frakes; Ricardo Baeza-Yates (eds.): Information Retrieval: Data Structures & Algorithms. Prentice Hall, 1992.
[GaeGun96] Volker Gaede; Oliver Günther: Multidimensional Access Methods. http://www.wiwi.hu-berlin.de/institute/iwi/info/research/iss/papers/survey.ps.Z.
[Guttma84] Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. In [SIGMOD84], pages 47-57, 1984.
[Henr90] A. Henrich: Der LSD-Baum: eine mehrdimensionale Zugriffsstruktur und ihre Einsatzmöglichkeiten in Datenbanksystemen. Dissertation. Fachbereich Mathematik und Informatik der Fernuniversität Hagen, Oktober 1990.
[HeSiWi89] Andreas Henrich; Hans-Werner Six; Peter Widmayer: The LSD tree: spatial access to multidimensional point and non point objects. In [VLDB89], 1989.
[Larson80] Per-Åke Larson: Linear Hashing with Partial Expansions. In [VLDB80], pages 224-232, 1980.
[Larson83] Per-Åke Larson: Dynamische Hashverfahren. Informatik Spektrum,, pages 7-19, Februar 1983.
[Litwin80] Witold Litwin: Linear Hashing:  A New Tool for File and Table Addressing. In [VLDB80], pages 212-223, 1980.
[McCrei77] Edward M. McCreight: Pagination of B*-Trees with Variable-Length Records. COMMUNICATIONS OF THE ACM (CACM), 20:9., pages 670-674, September 1977.
[NiHiSe84] J. Nievergelt; H. Hinterberger; K. C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Transactions on Database Systems, 9:1., pages 38-71 1984.
[RaMaFZ00] Frank Ramsak, Volker Markl, Robert Fenk, Martin Zirkel, Klaus Elhardt, Rudolf Bayer: Integrating the UB-Tree into a Database System Kernel. VLDB 2000: 263-272
[RamGeh00] Raghu Ramakrishnan, Johannes Gehrke: Database Management, 2nd Edition. Systems.McGraw-Hill 2000
[Samet90] Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1990.
[SeeKri90] Bernhard Seeger; Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. In [VLDB90], pages 590-601, 1990.
[SIGMOD84] Beatrice Yormark (ed.): SIGMOD'84, Proceedings of Annual Meeting, Boston, Massachusetts, June 18-21, 1984. ACM Press, 1984.
[SIGMOD90] Hector Garcia-Moline; H. V. Jagadish (eds.): Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990. ACM Press, 1990.
[VLDB80] Sixth International Conference on Very Large Data Bases, October 1-3, 1980, Montreal, Quebec, Canada, Proceedings. 1980.
[VLDB89] Proc. of the 15th International Conference on Very Large Data Bases. VLDB Endowment, 1989.
[VLDB90] Dennis McLeod; Ron Sacks-Davis; Hans-Jörg Schek (eds.): 16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane Queensland, Australia, Proceedings. Morgan Kaufmann, 1990.
[VLDB96] T. M. Vijayaraman (ed.): VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India. Morgan Kaufmann,, September 1996.
[WiMoBe94]  Ian H. Witten; Alistair Moffat; Timothy C. Bell: Managing Gigabytes: Compressing and Indexing Documents and Images. Van Nostrand Reinhold, 1994.
[Wood93]  Derick Wood: Data Structures, Alorithms, and Performance. Addison-Wesley, 1993.

Links

[Uni-Bonn][Informatik] [III] [Lehre] [Seitenanfang] 

Thomas Bode  (tb@informatik.uni-bonn.de)