Klassische Anfragesysteme wie Datenbanken können nur präzise Anfragen verarbeiten. Leider wissen viele Benutzer nicht genau, was sie eigentlich suchen möchten. Sogenannte “Skyline Queries” erweitern das Anfragespektrum mit sog. weichen Bedingungen, die von den zurückgegebenen Objekten möglichst gut erfüllt werden sollten. Das wohl meist bekannte Beispiel für diese Anfrageart ist die Hotelsuche am Badestrand: Urlaubsreisende möchten ein Hotel buchen, das möglichst nahe am Strand und möglichst günstig ist. Im Normalfall sind beide Attribute “Strandnähe” und “kostengünstig” entgegengesetzt. Klassische Systeme würden im schlimmsten Fall entweder kein Ergebnis oder den ganzen Datensatz ausgeben. Man kann sich erdenken, dass sich besonders bei mehr-dimensionalen, anti-korrelierten Anfragen Skyline Queries als praktisch erweisen.

Diese Arbeit befasst sich mit der Bewertung verschiedener, paralleler, Skyline-Algorithmen Neben theoretischen Grundlagen und einer Beschreibung und Analyse der bekannten Algorithmen PSkyline, SkylineBreaker und Parallel BBS wird ein Framework für die Tests der Algorithmen implementiert Anschließend werden die Algorithmen mit Hilfe des Frameworks und mit diversen synthetischen und realen Datensätzen getestet Vergleichsparameter sind dabei die Laufzeit und der Speicherbedarf. Nach der Testanalyse werden im letzten Schritt Optimierungsmöglichkeiten vorgestellt, welche an den zuvor entdeckten Schwächen ansetzen und versuchen diese Schwächen auszubessern.

Literatur: PSkyline, SkylineBreaker, Parallel BBS Sky-Quadtree.

Bachelorarbeit

Sven Wiemann (2016).

Dominik Köppl und Johannes Fischer.