We present an in-memory, cross-platform, parallel reasoner for RDFS and RDFSPlus . Inferray uses carefully optimized hash-based join and sorting algorithms to perform parallel materialization. Designed to take advantage of the architecture of modern CPUs, Inferray exhibits a very good uses of cache and memory bandwidth. It o ers state-of-theart performance on RDFS materialization, outperforms its counterparts on RDFSPlus and can be connected with Jena. Reasons to see the poster: i) Presentation of the system, how to use it; ii) Discussion about implementation, source code walkthrough.
Research in reasoner design and implementation roots to the advent of the
Semantic Web technologies [
Forward-chaining reasoning can be performed either by iterative rules
application, as done in Inferray, or by using the RETE algorithm [
RDF file
Import
Inferray imports data either from les on the hard drive or to interact with
the widely used Jena. After importation, the inference process is separated into
di erent steps, depicted in Figure 1, the highlights are presented as follows:
Transitivy Closure To perform e cient transitivity closure, Inferray performs
this task prior to the iterative rules application. This innovative approach,
relies on a temporary data layout (before vertical partitioning) that allows
the use of the state-of-the-art algorithm from Nuutila[
Dictionary Encoding & Vertical Partitioning Inferray uses a tricky
dictionary encoding to compact the range of the IDs, while allowing an e cient
data layout. Instead of starting numeration at 0 and increasing the value
with incoming RDF resources, Inferray uses a dense numbering scheme that
allows both vertical partitioning and the use of e cient sorting algorithms.
The s p o triples are then splitted to be vertical partioned, using the
standard partition on the predicate p [
Sorting algorithms E ciently sorting is the cornerstone of high-performance sort-merge-join algorithms. Based on the dense numbering scheme, Inferray uses an adaptative sorting approach including a new counting sort algorithm for sorting pairs of integers. When outside the application domain of the counting sort, a custom MSD-Radix algorithm for sorting pairs kicks in. Our sorting experiments report througputs from 20 to 70 millions pairs per second, results that are at least on par with state-of-the-art algorithms. Parallel sort-merge-joins Using array based layout, sort-merge-joins are performed e ciently due to a maximization of memory cache usage. In the rst step, joins are perform on parallel, on a per-rule basis. Results of the joins is the materialisation of inferred triples, that may contains duplicates already present in the main triple store. The inferred triples are sorted and then merged in linear time into the main store, again in parallel manner. This e cient handling of duplicates largely contribute to the e ciency of Inferray.
Post processing The post-processing step handles corner cases such as rules having only one condition, this is for instance common in RDFS reasoning. 100000 10000 1000 100 10 1
Inferray OWLIM RDFox LUBM 1M LUBM 5M LUBM 10M LUBM 25M LUBM 50M LUBM 75M LUBM 100M Wikipedia Yago Taxo Wordnet
Fig. 2. RDFSPlus Inference time in milliseconds, log scale.
Performance
Experiments were conducted on a Intel Xeon E3 1246v3 processor with 8MB of
L3 cache. Our system is equipped with 32GB of main memory; a 256Go PCI
Express SSD. The system runs a 64-bit Linux 3.13.0 kernel with Oracle's JDK
7u67. We compared Inferray against RDFox and OWLIM-SE. To perform our
experiments, we developed a dedicated benchmark suite [
In this paper, we presented Inferray, a high-performance reasoner based on parallel sort-merge-join. We believe that the presented system is of the utmost practical interest for the community. Its performance enable large scale processing of ontologies and its compatibility with the widely used Jena ensures its adoption by the end users.