Ph.D. Theses

Toward Webscale, Rule-based Inference on the Semantic Web via Data Parallelism

By Jesse Weaver
Advisor: James Hendler
February 4, 2013

This thesis considers the problem of scaling rule-based inference to large quantities of RDF data found on the Semantic Web. The general approach is one of data parallelism, that is, dividing data among processors such that the collective results of each processor's individual inference is the same as though inference was performed sequentially. In this way, theoretically speaking, more processors can be added to accommodate more data.

The problem is first considered from the perspective of the operational semantics of inference with production rules. The question is asked, under what conditions is embarrassingly parallel inference guaranteed to be correct? Sufficient conditions are determined and proven at both a fine-grained level close to the basic operational semantics and a more coarse-grained level that applies directly to rules. The conditions are placed on the relationship between rules and distribution schemes, that is, the way in which data is assigned to processors.

Then, a special class of distribution scheme is considered called replication schemes. Replication schemes require that individual data either be replicated to all processors or placed arbitrarily on some processor(s). The aforementioned conditions are then reformulated to consider replication schemes which reveals that testing the conditions for replication schemes is reducible to satisfiability (SAT), and not only SAT but 2SAT. An augmented version of this reduction which is a reduction to 3SAT also accounts for the possibility to eliminate some rules in order to improve parallelization. These reductions along with a proposed methodology for restricting rules are used to derive restricted versions of the RDFS and OWL2RL rules that are amenable to parallel inference.

Finally, an evaluation is performed that tests these theoretical findings for a restricted version of RDFS inference on two large, well-known datasets: LUBM and BTC2012. The LUBM dataset represents and optimistic case, meaning that if performance is poor with LUBM, then it will likely be poor on many datasets. On the other hand, the BTC2012 dataset represents a pessimistic case, meaning that if performance is good with BTC2012, then it is likely that performance will be good with other datasets. While the usual scalability metrics are used (speedup, efficiency, etc.), the Karp-Flatt metric reveals that inference is almost entirely parallel.

Return to main PhD Theses page