Hits:

Indexed by:期刊论文

Date of Publication:2017-11-01

Journal:计算机工程与应用

Included Journals:CSCD

Volume:53

Issue:21

Page Number:24-31,53

ISSN No.:1002-8331

Key Words:RDF图;静态分割;动态分割;边割;负载均衡

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