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

发布时间：2018-01-10 13:36

本文关键词：双目标优化的RDF图分割算法　出处：《计算机工程与应用》2017年21期 　论文类型：期刊论文

【摘要】：分布式存储是解决大规模数据存储的一种比较有效的方法,而数据分割是实现分布式存储的前提。面对不断增长的RDF数据,提出一种基于双目标优化的RDF图分割算法(RDF Graph Partitioning algorithm based on Double Objective Optimization,RGPDOO)。RGPDOO将边割和分割平衡两项图分割指标融合到一个目标函数,并依据此目标函数,实现了RDF图的静态和动态分割。其中静态图分割通过对图进行初始划分,将图中顶点分成内核顶点、交叉顶点和自由顶点三类。然后通过计算目标函数增益对交叉和自由顶点进行分配。动态图分割部分,针对RDF元组的插入和删除给出相应的解决方案。同时,为了满足图分割目标,算法每隔一段时间T会根据子图的平衡性和紧密性进行一次动态调整。实验选择合成和真实数据集进行测试,并分别与几种通用的静态和动态图分割算法进行比较。实验结果表明提出的算法能够有效地实现RDF图的静态和动态分割。
[Abstract]:Distributed storage is a more effective method to solve large-scale data storage, and data segmentation is the premise of distributed storage. Facing the growing RDF data. A two-objective optimization based RDF image segmentation algorithm is proposed. RDF Graph Partitioning algorithm based on Double Objective. Optimization. RGPDOO).RGPDOO merges edge cutting and partition equilibrium into one objective function and according to this objective function. The static and dynamic segmentation of the RDF graph is realized, in which the vertices in the graph are divided into kernel vertices by initial partition of the graph. Crossover vertices and free vertices are divided into three categories. Then the crossover and free vertices are allocated by calculating the objective function gain. The corresponding solution for RDF tuple insertion and deletion is given. At the same time, in order to meet the goal of graph segmentation. Every other time T adjusts dynamically according to the balance and compactness of the subgraph. The experiment chooses the composition and the real data set to test. Compared with several general static and dynamic image segmentation algorithms, the experimental results show that the proposed algorithm can effectively realize the static and dynamic segmentation of RDF images.
【作者单位】：大连理工大学软件学院;渤海大学信息科学与技术学院;
【基金】：国家自然科学基金(No.U1301253,No.61672123) 广东省科技计划(No.2015B010110006) 国家重点研发计划(No.2016YFD0800300) 辽宁省博士科研启动基金项目(No.201601348,No.201601349)
【分类号】：TP333
【正文快照】： 1引言万维网联盟(W3C)推荐的资源描述框架(ResourceDescription Framework,RDF)是描述语义网中各种资源与它们之间语义关系的一个重要框架标准[1]。RDF使用三元组主语,谓语,宾语来描述世界,当把主语和宾语看做图中两个顶点,谓语看做是由主语指向谓语的有向边时,RDF数据集

【相似文献】