关键词: RDF图, 静态分割, 动态分割, 边割, 负载均衡

Abstract: Distributed storage is a more effective method for the mass data storage. And, the data partitioning is the premise of distributed storage. In facing of the growing semantic web data, RDF Graph Partitioning algorithm is proposed by Double Objective Optimization（RGPDOO）. RGPDOO fuses edge cut and load balancing together to get an objective function. According to this objective function, RGPDOO achieves static and dynamic partitioning of RDF graph. For the static partitioning, an initial partitionis executed to divide the node into three kinds：kernel nodes, boundary nodes and freedom nodes. And then, the boundary and freedom nodes are distributed to apartition with the max gain of objective function. For the dynamic partitioning, the insertion and deletion solution of triples are given by the objective function. And, RGPDOO will execute a dynamic adjustment at a certain time interval according to the balance and tightness of partitioning subgraph to satisfy the partitioning object. Finally, the algorithm is tested on synthetic and real datasets in comparison with several general graph partitioning algorithms. The experimental results show that RGPDOO is more suitable for RDF graph partitioning.

Key words: RDF graph, static partitioning, dynamic partitioning, edge cut, load balancing