Not logged in.

Quick Search - Contribution

Contribution Details

Type Conference or Workshop Paper
Scope Discipline-based scholarship
Published in Proceedings Yes
Title B+Hash Tree: optimizing query execution times for on-disk semantic web data structures
Organization Unit
Authors
  • Minh Khoa Nguyen
  • Cosmin Basca
  • Abraham Bernstein
Editors
  • A Fokoue
  • Yi Guo
  • T Liebig
Presentation Type paper
Item Subtype Original Work
Refereed Yes
Status Published in final form
Language
  • English
Page Range 96 - 111
Event Title Proceedings Of The 6th International Workshop On Scalable Semantic Web Knowledge Base Systems (SSWS2010)
Event Type workshop
Event Location Shanghai, China
Event Start Date November 8 - 2010
Event End Date November 8 - 2010
Abstract Text The increasing growth of the Semantic Web has substantially enlarged the amount of data available in RDF format. One proposed solution is to map RDF data to relational databases (RDBs). The lack of a common schema, however, makes this mapping inefficient. Some RDF-native solutions 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 paper we propose a novel type of index structure called a B+Hash Tree, which combines the strengths of traditional B-Trees with the speedy constant-time lookup of a hash-based structure. Our 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. We evaluate the approach 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 we show should grow as dataset sizes increase.
Other Identification Number 1459
PDF File Download from ZORA
Export BibTeX
EP3 XML (ZORA)