Institut für Informatik III
Universität Bonn

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

 Proseminar Indexstrukturen für Datenbanken

(Wintersemester 2005/2006)

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

Ansprechpartner

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

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

• Rainer Herter; Raum A 202;
  Email: herter(at)cs.uni-bonn.de

Informationen zum Proseminar

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:

3-tägiges Blockseminar

Zeit: 20. – 22. Februar 2006 (2. Woche der vorlesungsfreien Zeit)

Raum: wird noch bekannt gegeben!

Termine:

Abgabe der Gliederung spätestens 16. Dezember 2005

Abgabe der Ausarbeitung spätestens 23. Januar 2006 per Mail

Überarbeitete Ausarbeitung und Folienentwürfe spätestens 13. Februar 2006 per mail

Diese Fristen sind unbedingt einzuhalten!

Themen und Zeitplan:

Externe Sortierverfahren

Thomas Kudla

Ausarbeitung: Externe Sortierverfahren

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

Dynamische Hashverfahren

Hakim Baadda

Ausarbeitung: Dynamische Hashverfahren

Literatur:

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

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

B-Bäume und ihre Erweiterungen

Daniela Ritter

Ausarbeitung: B-Bäume und ihre Erweiterungen

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

Yimiao Wan

Ausarbeitung: Invertierte Listen

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.
  

Quad-Trees

Jens Sengenberger

Ausarbeitung: Quad-Trees

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

Redouane Jadi

Ausarbeitung: Universal B-Tree

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

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

Ausgefallene Themen:

Externe Hashverfahren I: Erweiterbares Hashing

Victor Anoumedem Takile
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.
  

PAT-Trees / PAT-Arrays

Ina Hessenmüller
fällt aus

Literatur:

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

Index Fabric

Ebru Urungu
fällt aus

Literatur:

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

C-Tree

Bayram Ak
fällt aus

Literatur:

• [ZoLiCh04]
  Qinghua Zou, Shaorong Liu, Wesley W. Chu: Ctree: A Compact Tree for Indexing XML Data, 2004

• [ZoLiCh04]
  Qinghua Zou, Shaorong Liu, Wesley W. Chu: Ctree: A Compact Two-level Bidirectional Tree for Indexing XML Data
  

R*-Bäume und ihre Erweiterungen

Mandana Ghassemzadeh
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.

Suche nach räumlich benachbarten Objekten

Kyriakos Papadopoulos
fällt aus

Literatur:

• Henrich94

• Hjaltason95

• Roussopoulos95

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

Letzter Stand: 17.02.2006 17:09 Uhr, Rainer Herter herter(at)cs.uni-bonn.de