Toward Webscale, Rule-Based Inference on the Semantic Web Via Data Parallelism
Abstract
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 schemes 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 restricted versions of RDFS and OWL2RL inference on two large, well-known datasets exceeding a billion triples: LUBM10K and BTC2012.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 2013
- Accession Number
- ADA581228
Entities
People
- Jesse Weaver
Organizations
- Rensselaer Polytechnic Institute