- Bachelorarbeit -

Beschreibung:

Der Branch-and-Bound Ranked Search Algorithmus (BRS) ist eine Methode zur Beantwortung von Top-k-Anfragen auf Datenmengen mithilfe von multivariaten Bewertungsfunktionen. Dabei ist die Standardvariante von BRS nur dann effizient, wenn die Bewertungsfunktion monoton ist. Ziel dieser Arbeit ist die Analyse von zwei Erweiterungen des BRS-Algorithmus, die die Top-K Elemente für bestimmte Klassen nicht-monotoner Funktionen effizient bestimmen können. Diese Erweiterungen ermöglichen das Finden der Elemente mit den k maximalen Bewertungen bei Nutzung von quasi-konvexen Funktionen und der Elemente mit den k minimalen Bewertungen bei Nutzung von parabolischen Polynombewertungsfunktionen. Beide Funktionsklassen weisen praktische Eigenschaften bezüglich ihrer Extrema auf, mit denen der BRS-Algorithmus ähnlich dem monotonen Fall den Suchraum effizient begrenzen kann. Die Möglichkeit, Top-K-Anfragen mit nicht-monotonen Bewertungsfunktionen ausführen zu können, ist für eine Vielzahl von praktischen Anwendungen relevant. In dieser Arbeit werde Ich die Korrektheit und Zeitkomplexität beider Methoden in der Praxis verifizieren.

Anforderungen/Kenntnisse:
Datenbank-Indizes, R-Bäume, Datenanalyse mit Python, Anfragebeantwortung, Top-K-Anfragen

Bearbeitung:
Simon Buchholz

Ergebnis:
Die Ausarbeitung kann im Institut für Informationssysteme angefordert werden.

Betreuung:

Prof. Dr. rer. nat. Ralf Möller
Institut für Informationssysteme
Ratzeburger Allee 160 ( Gebäude 64 - 2. OG)
23562 Lübeck
Telefon: 0451 / 3101 5700