Not logged in.
Quick Search - Contribution
Contribution Details
| Type | Bachelor's Thesis |
| Scope | Discipline-based scholarship |
| Title | Optimized disk oriented tree structures for RDF indexing: the B+Hash Tree |
| Organization Unit | |
| Authors |
|
| Supervisors |
|
| Institution | University of Zurich |
| Faculty | Faculty of Economics, Business Administration and Information Technology |
| Date | 2010 |
| Abstract Text | The increasing growth of the Semantic Web has substantially enlarged the amount of data available in RDF (Resource Description Framework) format. One proposed solution is to map RDF data to relational databases. The lack of a common schema, however, makes this mapping inefficient. RDF-native solutions often use B+Trees, which are potentially becoming a bottleneck, as the single key-space approach of the Semantic Web may even make their O(log(n)) worst case performance too costly. Alternatives, such as hash-based approaches, suffer from insufficient update and scan performance. In this thesis a novel type of index structure called B+HASH TREE is being proposed, which combines the strengths of traditional B-Trees with the speedy constant-time lookup of a hash-based structure. The main research idea is to enhance the B+Tree with a Hash Map to enable constant retrieval time instead of the common logarithmic one of the B+Tree. The result is a scalable, updatable, and lookup-optimized, on-disk index-structure that is especially suitable for the large key-spaces of RDF datasets. The approach is evaluated against existing RDF indexing schemes using two commonly used datasets and show that a B+HASH TREE is at least twice as fast as its competitors – an advantage that this thesis shows should grow as dataset sizes increase. |
| Zusammenfassung | Das steigende Wachstum von SemantikWeb hat die verfügbare Menge an Ressource Description Framework (kurz RDF) Daten erheblich gesteigert. Es wird häufig vorgeschlagen RDF Daten in relationale Datenbanken zu speichern. Da aber RDF kein allgemeines Schema besitzt, ist das Speichern solcher Daten in relationale Datenbanken besonders ineffizient. Andere native RDF Lösungen greifen zur Indexierung von solcher Daten häufig auf B+Bäume zurück, welche aber zukünftig eventuell nicht mehr skalieren werden, da der enorme Wertebereich von SemantikWeb möglicherweise sogar eine O(log(n)) Performance zu kostspielig macht. Alternative Lösungen, welche zur Indexierung Hash-basierte Datenstrukturen benützen, leiden oft an der mangelhaften Performance beim Hinzufügen neuer Datensätze oder bei der Suche nach geordneten Daten. In dieser Arbeit wird eine neuartige Indexstruktur vorgestellt, die sich B+HASH BAUM nennt. Der B+HASH BAUM kombiniert die Stärke von traditionellen B-Bäumen mit der schnellen und konstanten Suchzeit von Hash-basierte Datenstrukturen. Die Hauptidee dabei ist den B+Baum mit einer Hashtabelle zu erweitern, um eine konstante, anstelle der üblichen logarithmischen Suchzeit des B+Baumes zu erreichen. Das Resultat ist eine skalierende, aktualisierungs-, und such-optimierte, festplattenorientierte Indexstruktur, welche sich vor allem für grosse Wertebereichen von RDF Datensätze eignet. Der B+HASH BAUM wurde in der Evaluation mit zwei typischen Datensätzen gegen über bereits bestehenden RDF Index-Schemata evaluiert. Das Ergebnis der Evaluation zeigt, dass der B+HASH BAUM mindestens zweimal so schnell ist wie seine Konkurrenten – ein Vorteil, der diese Arbeit zeigen wird, mit der Grösse der Datensätze zunehmen wird. |
| Export |
BibTeX
|