Efficient processing of large RDF streams using memory management algorithms

Abstract

As more RDF streaming applications are being developed, there is a growing need for an efficient mechanism for storing and performing inference over these streams. In this poster, we present a tool that stores these streams in a unified model by combining memory and disk based mechanisms. We explore various memory management algorithms and disk-persistence strategies to optimize query performance. Our unified model produces an optimized query execution and inference performance for RDF streams that benefit from the advantages of using both, memory and disk.

Introduction

1 http://jena.sourceforge.net/contrib/contributions.html,http://cs.utdallas.edu/semanticweb 2 http://lucene.apache.org/java/docs/index.html If the triple is an ABox triple we also store or update for every subject of each incoming triple, it’s degree, a timestamp of when it was last accessed and a pointer to the triples belonging to it, in a memory buffer. The TBox triples are first read into memory without maintaining any statistics for them in the buffer. This helps to distinguish TBox triples from ABox triples. Since no statistics are maintained these TBox triples are never written to disk. When the writeThreshold is reached the buffer management subsystem returns a sorted buffer based on the selected memory management algorithm such as FIFO, LIFO, LRU, MRU and RANDOM. We also adapted social network centrality measures such as degree centrality (DC ) and clustering coefficient (CC ) [ 4 ] into memory management algorithms. The writeThreshold is defined as, writeT hreshold = initT hreshold totalM em. The equation takes initThreshold as a number of triples and the memory size (specified in gigabytes) given to the current run from the user. Triples from the in-memory graph are moved to the Lucene graph using the pointer of every subject node (from the sorted buffer) and the selected persistence strategy. This process of moving triples continues as long as x% of the writeThreshold is not reached (x is also user configurable). Finally, when the dbThreshold is reached we move all triples to Jena’s RDB graph. From this point onwards all incoming triples are directly stored in the RDB graph. We use a combination of in-memory, Lucene and RDB graphs for non-inference models and a combination of in-memory and Lucene graphs for inference models. For query execution, the input query is submitted to the graph that is currently being used. A non-inference query is run on either the in-memory and Lucene graphs or the RDB graph and a complete result is returned to the user. For an inference query, Pellet infers additional triples by reasoning over the result from the in-memory and Lucene graphs, using the TBox triples that are always in memory. The resulting triples are then returned to the user. 3

Experimental Results

We performed benchmark experiments to compare the performance of the unified model to both, the Jena database backends and a purely Lucene triple store. We used the Sp2Bench [ 5 ] benchmark to check non-inference query execution and the LUBM [ 6 ] benchmark to test inference. Although we have tested all queries of both benchmarks on our system, in this section we show results only for Q5b and Q8 from Sp2Bench and for Q4 and Q6 from LUBM as they are representative of the overall trend. The graphs below show only query time and they do not include loading times. We have also performed scalability tests with varying graph sizes, but in this poster we only show graph sizes of 50168 triples for Sp2Bench and 1 university ( 103000 triples) for LUBM. We use these small sizes since we only want to determine the best algorithm and Lucene persistence strategy in this paper. Further, we set writeT hreshold = (3=4) no. of triples in the graph, totalM em = 1 and x = no. of triples in mem=90. We chose these values for the parameters so that we always have a good balance of triples between memory and Lucene giving us a good indication of the overall performance of various queries of both benchmarks.

30000 25000 ) 20000 s (m15000 e iTm10000 5000

LRU+DegC MRU+DegC FIFO LIFO DegC IndCC Random Lucene RDB SDB 20000 15000 ) s (m10000 e m i T 5000

LRU MRU FIFO LIFO DegC IndCC Random Lucene RDB SDB 0

0 Q5b

Q8

Q4

Q6 Query

Query (a) Algorithms - Sp2Bench (b) Algorithms - LUBM We have used the degree and timestamp values to implement the memory management algorithms. For example, if we use LRU, we sort the buffer in the increasing order of timestamp values while for degree centrality we sort the buffer in increasing order of DC values. The reader should note that the DC and CC values are recomputed for every node each time the buffer is sorted. We then move triples to the Lucene graph for every node starting from the top of the buffer until x% of the triples are moved. We have also combined LRU and MRU with both DC and CC by first using the timestamp to sort the buffer and if there is a tie we use DC or CC to break the tie. Figure 2 shows a comparison of all memory management algorithms that we have tested for Sp2Bench and LUBM. 5000 5000

C-S C-S-Eff Mem Lucene RDB SDB For Sp2Bench, we see that DC gives us the best result because it keeps nodes that are relevant to the Sp2Bench queries in memory. In comparison, for LUBM, we see that MRU performs the best. This is due to the fact that MRU leaves the least recently used nodes in memory that are used by the Pellet reasoner for inference and query execution.

25000 25000 (a) Persistence strategies - Sp2Bench (b) Persistence strategies - LUBM

References

1. Dave Beckett . Scalability and Storage: Survey of Free Software/Open Source RDF storage systems . http://www.w3.org/2001/sw/Europe/reports/rdf_scalable_ storage_report/, July 2002 .

2. AllegroGraph RDFStore. http://www.franz.com/agraph/allegrograph/, 2005 .

3. Hong-Tai Chou and David J. DeWitt. An Evaluation of Buffer Management Strategies for Relational Database Systems . In VLDB, pages 127 - 141 , 1985 .

4. M. O. Jackson . Social and Economic Networks . Princeton University Press, 2008 .

5. Michael Schmidt , Thomas Hornung, Georg Lausen, and Christoph Pinkel. SP2Bench: A SPARQL Performance Benchmark . In ICDE , pages 222 - 233 , 2009 .

6. Yuanbo Guo , Zhengxiang Pan, and Jeff Heflin . LUBM: A benchmark for OWL knowledge base systems . J. Web Sem ., 3 ( 2 -3): 158 - 182 , 2005 .