Skip to Main Content U.S. Department of Energy
Center for Adaptive Supercomputing - Multithreaded Architectures

Billion Triple Challenge 2010

High Performance Semantic Factoring of Giga-Scale Semantic Graph Databases

Abstract:

As semantic graph database technology grows to address components ranging from extant large triple stores to SPARQL endpoints over SQL-structured relational databases, it will become increasingly important to be able to bring high performance computational resources to bear on their analysis, interpretation, and visualization, especially with respect to their innate semantic structure. Our research group built a novel high performance hybrid system comprising computational capability for semantic graph database processing utilizing the large multithreaded architecture of the Cray XMT platform, conventional clusters, and large data stores. We present the results of our exploration for the analysis of the Billion Triple dataset with respect to its semantic factors, including basic properties, connected components, namespace interaction, and typed paths.


You may download our submission paper.


BTC2010 Base Statistics

We acquired BTC10 and verified it as an RDF graph with 3.2B <s, p, o, q> quads, which we projected to 1.4B unique <s, p, o> triples, ignoring the quad field (useful for provenance and other operations but not for analyzing the main content). We identified duplicates by hashing the triples, now of integers, into a shared hash table, in 10 min. 37 sec. The entire process of converting the data from string to integers, removing the quad field, and deduplicating, compressed BTC10 from 624 GBs to 32 GBs.

The basic statistics we extracted from the 1.4B triples include:


Connected Components

The Live Demo is currently not available. Check back soon ...

  • There are 208,300 components, one of which there is a giant component covering 278,400 vertices, or 99.8% of the total.

  • The Cray XMT computing Connected Components on the 1.4B-edge graph scales well as seen in the log-log plot of the time versus processors:

    Chart of scalability on the Cray XMT


Namespace Architecture

  • View Namespace details.

  • To understand the relationships between the sources which generated the BTC dataset, we explore a summary metric for data linking among namespaces.

  • We call triples "linked" when two or more of the subject, predicate, or object map to different fully-qualified domain names.

  • Using our Cray XMT, we extracted domain names from each entity and computed a census of both the domains and linked triples. With this data, we crafted an interactive tool which visually presents the relationships between these namespaces.

  • Summary census information:


Typed Path Structures

  • View n-grams details.

  • We computed bigrams (paths of 2-edges/3-nodes) and trigrams (paths of 3 edges/4-nodes).

  • We note the prominence of low-frequency predicates in both the bigrams and trigrams. For example, consider the most frequent bigram <dgtwc:isPartOf, dgtwc:partial_data>, with a frequency of 35.8%. The constituent predicates have individual frequencies of only 0.0038% and 0.027% respectively.

CASS

Research and Development

Resources