基于GPU的RDF类型同构并行算法

冯佳颖; 张小旺; 冯志勇

doi:10.7544/issn1000-1239.2018.20160845

基于GPU的RDF类型同构并行算法

冯佳颖^1,3,
张小旺^1,3,
冯志勇^2,3

¹(天津大学计算机科学与技术学院天津 300350)
²(天津大学软件学院天津 300350)
³(天津市认知计算与应用重点实验室天津 300350) (fengjiaying@tju.edu.cn)

基金项目: 国家重点研发计划项目(2016YFB1000603)；国家自然科学基金项目(61672377)；天津市科技支撑重点项目(16YFZCGX00210)

详细信息

中图分类号: TP392
计量
- 文章访问数: 1147
- HTML全文浏览量: 0
- PDF下载量: 693
出版历程
- 发布日期: 2018-02-28

Parallel Algorithms for RDF Type-Isomorphism on GPU

¹(School of Computer Science and Technology, Tianjin University, Tianjin 300350)
²(School of Computer Software, Tianjin University, Tianjin 300350)
³(Tianjin Key Laboratory of Cognitive Computing and Application, Tianjin 300350)

摘要

摘要: 资源描述框架(resource description framework, RDF)作为W3C(World Wide Web Consortium)组织提出的语义网数据规范，描述了资源及其之间的关系.随着RDF数据规模不断增加，高效地检索RDF数据成为当前面临的重大挑战.在RDF数据上的查询响应问题可以被简化为子图同构问题.作为子图同构的重要部分，类型同构(type-isomorphism)在处理部分RDF查询，如星状查询和链状查询等，具有较高的性能.目前，现有解决类型同构的方法匹配效率均依赖于CPU的计算能力.近年来，图像处理单元(graphic processing units, GPU)的发展提高了图数据处理的性能.与CPU相比，GPU多处理器具有高并发、易扩展以及价格成本低等优势.由于CPU处理大规模RDF数据的计算能力有限，提出一种基于GPU的RDF类型同构算法，使类型同构问题在GPU架构上通过并行的方式解决.最后，实现了基于GPU的RDF类型同构算法，并在基准数据集LUBM上对该算法进行性能测试，实验结果表明:该算法显著优于基于CPU架构的算法.
- 资源描述框架 /
- SPARQL查询处理 /
- 子图同构 /
- 类型同构 /
- 图像处理单元
Abstract: Resource description framework (RDF), officially recommended by the World Wide Web Consortium (W3C), describes resources and the relationships of them on the Web. With the volume of RDF data rapidly increasing, a high performance method is necessary to efficiently process SPAQRL (simple protocol and RDF query language) query over RDF data, which can be reduced to the classical problem—subgraph isomorphism. As an important class of subgraph isomorphism, type-isomorphism helps many interesting queries over RDF data to get high performance such as star or linear query structures. However, many existing approaches, which are proposed to solve type-isomorphism, mostly depend on calculative capabilities of CPU. In recent years, graphic processing units (GPU) has been adopted to accelerate graph data processing widely in several works, which have better computational performance, superior scalability, and more reasonable prices. Considering the limited calculative capabilities of CPU in handling large-scale RDF data, we propose an algorithm that processes type-isomorphism problem on parallel GPU architecture over RDF datasets. In this paper, we implement the algorithm and evaluate it in the benchmark datasets—lehigh university benchmark (LUBM) through a mass of experiments. The experimental results show that our algorithm outperforms significantly than the CPU-based algorithms.
- resource description framework /
- SPARQL query processing /
- subgraph isomorphism /
- type-isomorphism /
- graphic processing units

HTML全文

参考文献(0)

施引文献(19)

期刊类型引用(13)

1.	程巍，王红英，娄岩. 基于“5G云+VR”的心脏解剖虚拟仿真教学系统的构建与应用. 中国医学教育技术. 2025(02): 223-228 . 百度学术
2.	费星瑞，谢逸. 基于HMM-NN的用户点击流识别. 计算机科学. 2022(07): 340-349 . 百度学术
3.	王同贺，华昊辰，曹军威. 共识边缘计算及其在能源互联网中的应用. 电力建设. 2021(02): 116-125 . 百度学术
4.	柴艳娜. 内核网络堆栈的Go语言实现与分析. 电子设计工程. 2021(13): 34-37+42 . 百度学术
5.	樊琦，李卓，陈昕. 基于边缘计算的分支神经网络模型推断延迟优化. 计算机应用. 2020(02): 342-346 . 百度学术
6.	向安玲，杨钰雯. 边缘计算在传媒领域的应用. 中国传媒科技. 2020(03): 113-116 . 百度学术
7.	常国锋. 基于信任域的环形网络介质访问时延控制仿真. 计算机仿真. 2020(03): 349-353 . 百度学术
8.	董召杰，林志达. 基于边缘计算的机巡图像缺陷识别算法研究. 自动化与仪器仪表. 2020(07): 77-80 . 百度学术
9.	张翠芳，姬楠楠. 基于模糊矩阵的多线程网络通信延迟检测技术研究. 科学技术与工程. 2020(27): 11198-11203 . 百度学术
10.	华昊辰，李宇童，王同贺，秦兆铭，曹军威. 一种基于混合随机H_2/H_∞方法的能源互联网边缘计算系统控制策略. 中国电机工程学报. 2020(21): 6875-6885 . 百度学术
11.	闫朝峰，刘清莉. 王者荣耀业务网络感知保障浅析. 通讯世界. 2019(09): 81-82 . 百度学术
12.	肖文华，刘必欣，刘巍，程钢，王跃华. 面向恶劣环境的边缘计算综述. 指挥与控制学报. 2019(03): 181-190 . 百度学术
13.	丁祥海，王志会. 边缘计算在计算机科学方向的进展研究. 信息与管理研究. 2019(06): 73-83 . 百度学术