双目标优化的RDF图分割算法

RDF graph partitioning algorithm based on double objective optimization

分布式存储是解决大规模数据存储的一种比较有效的方法,而数据分割是实现分布式存储的前提。面对不断增长的RDF数据,提出一种基于双目标优化的RDF图分割算法(RDF Graph Partitioning algorithm based on Double Objective Optimization,RGPDOO)。RGPDOO将边割和分割平衡两项图分割指标融合到一个目标函数,并依据此目标函数,实现了RDF图的静态和动态分割。其中静态图分割通过对图进行初始划分,将图中顶点分成内核顶点、交叉顶点和自由顶点三类。然后通过计算目标函数增益对交叉和自由顶点进行分配。动态图分割部分,针对RDF元组的插入和删除给出相应的解决方案。同时,为了满足图分割目标,算法每隔一段时间T会根据子图的平衡性和紧密性进行一次动态调整。实验选择合成和真实数据集进行测试,并分别与几种通用的静态和动态图分割算法进行比较。实验结果表明提出的算法能够有效地实现RDF图的静态和动态分割。

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.