Suche

Implementierung und Evaluation von QuickCombine unter Einsatz von Oracle


Ausgangslage

Die Verwendung von Top-k Algorithmen wie Quick Combine, Stream Combine oder SR-Combine, welche am Lehrstuhl entwickelt wurden, spielen beim schnellen Retrieval von Ergebnissen bei Datenbankanfragen eine immer wichtigere Rolle.

Im Rahmen dieser Arbeit sollen diese 3 Algorithmen in Java reimplementiert werden. Dazu sollen Datenbankfunktionen wie Sorted Access (unter Ausnutzung eines Index) und Random Access benutzt werden. Zusätzlich sollen die Daten aus Streams der gleichen, oder aber auch von verteilten Datenbanksystemen entgegengenommen werden können. Nach Erfolgreicher Implementierung der Algorithmen soll die Integration in den PSQL-Parser erfolgen, um eine Schnittstelle für Top-k Algorithmen zu schaffen. Testcases und die Prüfung auf Korrektheit sind selbstverständlich Bestandteil dieser Arbeit. Eine ausführliche Evaluation von QuickCombine (u.a. im Vergleich zum Algorithmus von Fagin) ist obligatorisch. Die ausführliche Dokumentation sowie Abgabe von funktionierendem Code gehören ebenfalls dazu.

Aufgaben

  • Implementierung der Top-k Algorithmen
  • Verwendung von Sorted und Random Access
  • Tuning von Quickcombine unter Einsatz von Oracle (Indizes, etc.)
  • Integration der Algorithmen in PSQL und Anpassung des PSQL-Parsers
  • Evaluation von Quickcombine im Vergleich zum Algorithmus von Fagin (Performance, Anzahl verarbeiteter Objekte, etc.)

Voraussetzungen

  • Sehr gute Java-Programmierkenntnisse
  • Vorlesung DB1
  • Vorlesung Suchmaschinen

Sonstiges

  • Quellcode der Implementierung muss lauffähig in unserem CVS System verwaltet und auf CD inkl. Bachelorarbeit (PDF) abgeliefert werden
  • Software wird vor Abgabe begutachtet

Ansprechpartner

Markus Endres