Not logged in.

Quick Search - Contribution

Contribution Details

Type Bachelor's Thesis
Scope Discipline-based scholarship
Title SPARQL Query Approximation With Bloom Filters
Organization Unit
Authors
  • Stefanie Ziltener
Supervisors
  • Tobias Grubenmann
Language
  • English
Institution University of Zurich
Faculty Faculty of Business, Economics and Informatics
Date 2016
Abstract Text The topic of this thesis is SPARQL query approximation on RDF data. In standard database contexts, using approaches for approximating query results is common. An example of a motivation for using query approximation instead of accurate execution is that resources in the form of computing power, disk space, money, and database access can be restricted. Approximating the query results can serve as a decision basis for or against further processing of a querying strategy. The thesis analyses an approach to transfer one of three presented methods for query approximation to the Semantic Web context. The chosen algorithm uses Bloom filters to represent datasets of query conditions and additionally to join the sub results for the result approximation. The algorithm was implemented in Java code and compared to the actual query execution on the aspects of runtime and relative error of the results. The evaluation has shown that the approach is not yet sufficiently elaborated for overall positive results. With the limitations and optimization ideas that are presented, a conclusion is drawn with an outlook to future work.
Zusammenfassung Das Thema dieser Arbeit ist die Abschätzung der Resultate von SPARQL-Query Abfragen auf RDF Daten. In Standard-Datenbankumgebungen wird 'Approximate Query Processing' oft benutzt, um die Resultate zu schützen. Ein Beispiel, wo sich die Alternative zur exakten Ausführung des Queries lohnen kann ist, wenn Ressourcen eingeschränkt sind - wie die Rechenkapazität, Speicherplatz, Zugriff zur Datenbank oder Geld. Die Annäherung des Resultats kann als Entscheidungsgrundlage für weitere Überlegungen zu einer solchen Informationsabfrage-Strategie dienen. In der Arbeit wird eine Methode aus drei vorgestellten Vorgehen ausgewählt, um die Abschätzung in den gewünschten Semantic Web Kontext zu transferieren. Der gewählte Algorithmus benutzt Bloom Filter, um Zwischenresultate darzustellen und sie dann für das Schlussresultat miteinander zu vereinen. Die Implementierung des Algorithmus wurde in Java geschrieben und dann in Experimenten mit Betrachtung der Laufzeit und des relativen Abschätzungsfehlers ausgewertet. Die Analyse der Daten zeigt, dass die Methode noch nicht genügend optimiert ist, um generell positive Resultate zu liefern. Schlussendlich wird ein Fazit gezogen, das Limitierungen und Verbesserungsideen des Abschätzungsprozesses präsentiert und einen Ausblick auf zukünftige Arbeit zeigt.
PDF File Download
Export BibTeX