Institut für Informatik III
Universität Bonn

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

 Proseminar Indexstrukturen für Datenbanken

(Sommersemester 2005)

      INDEX:   Ansprechpartner   Informationen   Termine   Themen und Zeitplan   Links und online-Literatur

Ansprechpartner

• Dr. Thomas Bode; Raum A 202;
  Tel. 0228/73-4527
  Email: tb(at)cs.uni-bonn.de
  Sprechstunde: Nach Vereinbarung!

• Michael Schaefers; Raum A202;
  Email: schaefe3(at)cs.uni-bonn.de

Informationen zum Praktikum

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.

Vortragsmodus: Einzelvortrag mit vorhergehender schriftlicher Ausarbeitung

Zeit und Ort:

Blockseminar in der Woche nach Pfingsten (18.-20. Mai 2005)

Beginn: genaueres wird noch bekannt gegeben

Termine:

Abgabe der Gliederung spätestens 18. März

Abgabe der Ausarbeitung spätestens 20. April per Mail

Überarbeitete Ausarbeitung und Folienentwürfe spätestens 10. Mai per mail

Diese Fristen sind unbedingt einzuhalten!

Themen und Zeitplan:

Externe Sortierverfahren

Jiliang Zhang
fällt aus

Literatur:

• [Wood93] Kap. 12.5
  Derick Wood: Data Structures, Algorithms, and Performance. Addison-Wesley, 1993.

• [RamGeh00] Kap. 11
  Raghu Ramakrishnan, Johannes Gehrke: Database Management, 2nd Edition. Systems.McGraw-Hill 2000

Externe Hashverfahren: Erweiterbares Hashing, Lineares Hashing

Zhaohan Chen
fällt aus

Literatur:

• [Larson83]
  Per-Åke Larson: Dynamische Hashverfahren. Informatik Spektrum, pages 7-19, Februar 1983.

• [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.

• [Litwin80]
  Witold Litwin: Linear Hashing:  A New Tool for File and Table Addressing. In [VLDB80], pages 212-223, 1980.

• [Larson80]
  Per-Åke Larson: Linear Hashing with Partial Expansions. In [VLDB80], pages 224-232, 1980.

B-Bäume und ihre Erweiterungen

Yimiao Wan
fällt aus

Literatur:

• [Bayer77]
  Rudolf Bayer, Karl Unterauer: Prefix B-Trees. TODS 2(1): 11-26 (1977)

• [Comer79]
  Douglas Comer: The Ubiquitous B-Tree. ACM Computing Surveys, 11:2., pages 121-137, June 1979.

• [RamGeh00] Kap. 9
  Raghu Ramakrishnan, Johannes Gehrke: Database Management, 2nd Edition. Systems.McGraw-Hill 2000

Invertierte Listen

Nikolay Kunev

Literatur:

• [FraBae92] Kap. 3
  William B. Frakes; Ricardo Baeza-Yates (eds.): Information Retrieval: Data Structures & Algorithms. Prentice Hall, 1992.

• evtl. [WiMoBe94] Kap. 3.2, 5.0 - 5.3
  Ian H. Witten; Alistair Moffat; Timothy C. Bell: Managing Gigabytes: Compressing and Indexing Documents and Images. Van Nostrand Reinhold, 1994.

PAT-Trees / PAT-Arrays

Burak Sucu
fällt aus

Literatur:

• [FraBae92] Kap. 5
  William B. Frakes; Ricardo Baeza-Yates (eds.): Information Retrieval: Data Structures & Algorithms. Prentice Hall, 1992.

Index Fabric

Meng Li

Literatur:

• [CoSFHS01]
  Brian F. Cooper, Neal Sample, Michael J. Franklin, Gisli R. Hjaltason, Moshe Shadmon: A Fast Index for Semistructured Data. VLDB 2001:

Quad-Trees

fällt aus

Literatur:

• [Samet90] Kap. 1.2, 1.3, 2.3, 2.6, 3.5
  Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1990.

Universal B-Tree

fällt aus

Literatur:

• [Bayer96]
  Rudolf Bayer: The Universal B-Tree for multidimensional Indexing. Technical Report TUM-I9637, November 1996.

• [Bayer97]
  Rudolf Bayer: The Universal B-Tree for Multidimensional Indexing: general Concepts. WWCA 1997: 198-209

• [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

R*-Bäume und ihre Erweiterungen

fällt aus

Literatur:

• [Guttma84]
  Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. In [SIGMOD84], pages 47-57, 1984.

• [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.

Links

• Musterlayout für Powerpoint-Folien

• Computer Science Bibliography DBLP (Uni Trier)

• SIGMOD Record Web Edition

• Zugriff auf Online Publikationen über LibGate der Informatik

• ACM Digital Library

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

Letzter Stand: 12.05.2005 11:46 Uhr, Michael Schaefers schaefe3(at)cs.uni-bonn.de