RDF is considered to be an important data model for Semantic Web as a labeled directed graph. Querying in massive RDF graph data is known to be hard. In order to reduce the data size, we present ASSG, an Adaptive Structural Summary for RDF Graph data by bisimulations between nodes. ASSG compresses only the part of the graph related to queries. Thus ASSG contains less nodes and edges than existing work. More importantly, ASSG has the adaptive ability to adjust its structure according to the updating query graphs. Experimental results show that ASSG can reduce graph data with the ratio 85% in average, higher than that of existing work.
The resource description framework (RDF) data model has been designed as a
flexible representation of schema-relaxable or even schema-free information for
the Semantic Web [
In this paper, we present ASSG (Adaptive Structural Summary of Graphs), a graph compression method that further reduces the size of the graph data. ASSG has less components than Gr and more importantly, it has adaptive ability to adjust its structure according to different subgraph matchings. In the following sections, we mainly introduce our novel technique. 2
In this section, we present our approach of adaptive structural summary for labeled directed graph data (such as RDF). ASSG is actually an compressed graph constructed by equivalence classes of nodes and it has adaptive ability to adjust its structure according to different query graphs.
Graph data is divided into different equivalence classes by bisimulation
relations as [
An equivalence class ECG of nodes in graph data G = (V; E; L) is denoted by a triple (Ve; Re; Le), where (1) Ve is a set of nodes included in the equivalence class, (2) Re is the rank of the nodes, and (3) Le denotes the labels of the nodes.
A1 B1
A2 B2
A3 B3
A1A2A3
B1B2B3 C1
D1 C2
D2 C3
D3
C1C2C3
D1D2D3
B C
D Q1
A B
Q2 C
D (a) Graph data G
(b) ASSG (c) Query graphs Fig. 1. Graph data and equivalence classes A1
A2
A3
B1B2B3 C1C2C3
D1D2D3 (d) ASSGÿ
Obviously, ASSG is the minimum pattern that can describe labeled directed graph data because nodes with the same label and rank will be collapsed. Unfortunately, the process of measuring ranks will lose some descendants or ancestors of nodes. And this case will not conform to the definition of bisimulation, and thus bring out wrong answers for subgraph matching. For example, in Fig. 1(b), the nodes A1 and A2 in the same equivalence class have different children. To solve the problem, ASSG will adaptively adjust its structure for updating query graphs.
For each subgraph matching, the procedure of adaptively updating
ASSG includes two stages: matching and partitioning. Given a query graph Q =
(VQ; EQ; LQ) and ASSG GASS = (VASS ; EASS ; LASS ; RASS ), assuming that
RQ=frank(vQ)jvQ2VQg. For the matching stage, 8v2VQ and u2VQ, 9v′, u′2VASS ,
if LQ(v) = LASS (v′), LQ(u) = LASS (u′), and RQ(v) RQ(u) = RASS (v′)
RASS (u′), then v, u matches v′, u′ respectively. For the partitioning stage,
nodes in ASSG matching current query graph will be partitioned into different
parts according to its neighbors by the algorithm presented in [
In this section, we performed experiments on both realistic and synthetic data sets to verify the performance of ASSG.
Firstly, we use compression ratio as a measurement for evaluating the effectiveness of ASSG for subgraph matchings compared with Gr. We define compression ratio of ASSG as: CASS = jVASS j=jV j. Similarly, the compression ratio of Gr is CGr = jVrj=jV j. The ration is lower, the better. The effectiveness of ASSG compared with Gr is reported in Table 1 where jGj denotes to the size of graph data. For a query graph Gq = (Vq; Eq; Lq), the compression ratio of ASSG is decided by the number of labels jLqj in the query graph. Assuming that jLqj = 15% jLj, then we can study from table 1: By ASSG, graph data can be highly compressed according to query graphs. ASSG reduces graph data by 85% in average. The compression ratio of ASSG is lower than that of Gr.
Secondly, we evaluate the efficiency of updating ASSG. Assuming that number of labels in query graph is 15% of jLj. We generate two query graphs for updating ASSG. The number of repeated labels in these two graphs are 0, 1, 2, 5 respectively as table 2 shows. We can study that the more repeated labels in different query graphs, the less time occupation for ASSG to update. As a result, for frequent subgraph matchings, ASSG can be updated and maintained with low cost of time.
We have proposed ASSG, adaptive structural summary for RDF graph data. ASSG is based on equivalence classes of nodes, and ASSG compresses graph data according to the query graphs. We presented main idea for constructing and updating ASSG and designed experiments on realistic and synthetic data sets to evaluate the effectiveness and efficiency of our technique. Experimental results show that the compression ratio of ASSG is lower than that of existing work Gr and ASSG is efficiently updated for frequent queries. Further more, we will use ASSG for optimizing SPARQL queries on RDF data for semantic web. Acknowledgments. This work is supported by National Natural Science Foundation of China under Grant No. 61170184, 61402243, the National 863 Project of China under Grant No. 2013AA013204, National Key Technology R&D Program under Grant No.2013BAH01B05, and the Tianjin Municipal Science and Technology Commission under Grant No.13ZCZDGX02200, 13ZCZDGX01098 and 13JCQNJC00100.