Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-2065
Main Title: Efficient Query Processing in DHT-based RDF Stores
Translated Title: Effiziente Anfragebearbeitung in DHT-basierten RDF-Speichern
Author(s): Battré, Dominic
Advisor(s): Kao, Odej
Granting Institution: Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Die Informationsflut der modernen Informationsgesellschaft macht es zunehmend schwieriger, relevante Informationen zu finden, welche die Menschen bei ihrer Arbeit unterstützen. Daher wird bestrebt, Daten eine wohldefinierte semantische Bedeutung zu geben, um so eine bessere Zusammenarbeit von Computern und Menschen zu ermöglichen. Die vorherrschende Repräsentierung von semantischen Daten ist das Resource Description Framework (RDF). RDF beschreibt Informationen als Mengen von Tripeln oder äquivalent als gerichtete Graphen. Es bietet die Grundlage, um Ontologien zu definieren, Objekte und Konzepte zu annotieren, Informationen zu integrieren und implizites Wissen abzuleiten. Anwendung findet es in den Bereichen Semantic Web, Semantic Desktop, Grid Computing, E-Business, soziale Netzwerke, Naturwissenschaften und vielen mehr. Diese Dissertation beschreibt ein Indizierungsschema für RDF Tripel auf der Basis einer verteilten Hashtabelle (DHT), einem strukturierten Peer-to-Peer Overlay-Netzwerk, um Skalierbarkeit und Verlässlichkeit zu verbessern. Die Skalierbarkeit wird im Vergleich zu konventionellen zentralen Tripel-Speichern verbessert indem die Peers der DHT die Speicher- und Anfragelast untereinander teilen. Verlässlichkeit wird durch Replikation und fehlertolerante Routingmechanismen erreicht. Die Kernfrage dieser Dissertation ist, wie Anfragen effizient bearbeitet werden können, wobei berücksichtigt werden muss, dass die dafür relevanten Daten im Netzwerk verteilt liegen. Die Dissertation beschreibt und vergleicht dazu neue Strategien, um den Aufwand für die Übermittlung entfernt liegender Daten abzuschätzen und zu reduzieren. Des Weiteren beschreibt sie Caching-Mechanismen, die danach streben, Zwischenergebnisse vorhergehender Anfragen wieder zu verwenden. Abschließend werden Verfahren diskutiert, um die Anfrage- und Speicherlast der Knoten im Netzwerk zu balancieren. Der Erfolg der diskutierten Verfahren wird anhand von Benchmarks mit dem Lehigh University Benchmark demonstriert.
The growth of information in modern society makes it more and more difficult to find relevant information that supports people at their tasks. Therefore, we strive to give information a well-defined meaning for better enabling computers and people to work in cooperation. The prevalent representation for semantic information is the Resource Description Format (RDF). RDF describes information as sets of triples or equivalently as directed graphs. It provides the foundation for defining ontologies, annotating objects and concepts, information integration, and knowledge inference. Its applications are found in the areas of Semantic Web, Semantic Desktop, Grid computing, e-Business, social networks, natural sciences, and many others. This thesis presents an indexing schema for RDF triples that is based on a distributed hash table (DHT), a structured peer-to-peer overlay network, in order to improve scalability and reliability. Scalability is improved in comparison to centralized triple stores as the peers participating in the DHT share the storage and the query load. Reliability is achieved by replication and fault tolerant routing mechanisms. The core question addressed by this thesis is how queries can be processed efficiently given the fact that data relevant for the query is spread within the network. The thesis presents and compares novel strategies to estimate the effort of retrieving remote data and mechanisms to reduce the amount of data that needs to be transferred. It presents a caching mechanism that strives to reuse intermediate results of previous queries. Finally, it discusses strategies to balance the query and storage load of peers. The success of the strategies is demonstrated by benchmarks with the Lehigh University Benchmark.
URI: urn:nbn:de:kobv:83-opus-21188
http://depositonce.tu-berlin.de/handle/11303/2362
http://dx.doi.org/10.14279/depositonce-2065
Exam Date: 18-Dec-2008
Issue Date: 14-Jan-2009
Date Available: 14-Jan-2009
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): Abfrageverarbeitung
Datenbanksystem
Peer-to-Peer-Netz
RDF
Semantic Web
Database Systems
Distributed Hash Table
Peer to Peer Network
Query Processing
RDF
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Telekommunikationssysteme » Publications

Files in This Item:
File Description SizeFormat 
Dokument_20.pdf3.26 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.