Sie sind hier

Hashing für URIs zur Komprimierung von RDF Graphen

Beschreibung

RDF, das Datenmodell das im Semantic Web zum Einsatz kommt, basiert auf Aussagen die über Resourcen gemacht werden. Jede Aussage ist ein Tripel bestehend aus einem Subjekt, Prädikat und Objekt. Alle drei Teile des Tripels sind dabei URIs. Dadurch werden RDF Graphen jedoch sehr speicherintensiv. Ein üblicher Weg die Größe von RDF Graphen zu reduzieren ist dabei die URIs durch Zahlen zu ersetzen und sich zu merken welche Zahl für welche URI steht. Dies erlaubt es Dateigrößen für serialisierte Graphen gering zu halten oder auch mit größeren Graphen im Hauptspeicher zu arbeiten. Jedoch ist dies nur ein gangbarer Weg, wenn die Ersetzung von URIs durch Zahlen von Zahlen durch URIs effizient geschehen kann.  

Eine Möglichkeit solche Ersetzungen effizient durchzuführen ist es die URIs zu hashen. Dabei entsteht allerdings die Frage welche Hash-Funktionen am besten (bzgl. Kollisionen) für URIs geeignet sind. Weiterhin ist die Frage ob die Struktur von URIs, die sich z.B. in einen Host und einen Pfad trennen lassen, ausnutzen lässt um das Hashing zu Verbessern. So könnte zum Beispiel ein Multi-Level-Hashing Verfahren, bei dem nacheinander Hash-Funktionen nacheinander auf die URI bzw. auf Teile der URI der vorteilhafteste Weg sein.

 

Aufgabenstellung

 Ziel der Arbeit ist es das Hashing von URIs zu untersuchen. Dabei sollen bestehende Hash-Funktionen für URIs evaluiert werden. Weiterhin gilt es Ansätze wie das Multi-Level Hashing zu evaluieren und zu untersuchen in welchen Teilen die Struktur von URIs ausgenutzt werden können um entweder Kollisionen zu reduzieren oder andere Vorteile zu erreichen. Die Ergebnisse dieser Untersuchungen sollen abschließend in Koldfish als Webservice der URIs in Zahlen sowie Zahlen zurück in URIs transformiert integriert werden. 

 

Literatur und Lehrveranstaltungsempfehlungen

  • T. Akinwale, F. T. Ibharalu: The Usefulness of Multilevel Hash Tables with Multiple Hash Functions in Large Databases. CoRR abs/0905.4201 (2009)
  • Hamid R. Bazoobandi, Steven de Rooij, Jacopo Urbani, Annette ten Teije, Frank van Harmelen, Henri E. Bal: A Compact In-Memory Dictionary for RDF Data. ESWC 2015: 205-220

 

Benötigte Kenntnisse:

  • Java
Studienart: 
Bachelor
Ausschreibungsdatum: 
2016