基于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)

施引文献(63)

期刊类型引用(12)

1.	武家辉，李科研，陈丽新，张家诺，刘帅兵，逯鹏. 神经架构搜索技术研究综述. 计算机应用研究. 2025(01): 11-18 . 百度学术
2.	刘倩男，闫佳，刘诚. 基于改进MobileNetV3的岩石薄片分类研究. 电脑知识与技术. 2025(07): 26-28 . 百度学术
3.	吴艳灵，汤宝平，邓蕾，付豪. 低通筛选优化神经架构搜索的风电齿轮箱边缘侧故障诊断方法. 机械工程学报. 2025(07): 361-372 . 百度学术
4.	宋玉红，沙行勉，诸葛晴凤，许瑞，王寒. RR-SC:边缘设备中基于随机计算神经网络的运行时可重配置框架. 计算机研究与发展. 2024(04): 840-855 . 本站查看
5.	蒋鹏程，薛羽. 基于排序得分预测的演化神经架构搜索方法. 计算机学报. 2024(11): 2522-2535 . 百度学术
6.	刘威，郭直清，王东，刘光伟，姜丰，牛英杰，马灵潇. 改进鲸鱼算法及其在浅层神经网络搜索中的权值阈值优化. 控制与决策. 2023(04): 1144-1152 . 百度学术
7.	鞠翰文，邓扬，李爱群. 桥梁结构挠度-温度-车辆荷载监测数据相关性模型. 振动与冲击. 2023(06): 79-89 . 百度学术
8.	丁熠，郑伟，耿技，邱泸谊，秦志光. 基于多层级并行神经网络的多模态脑肿瘤图像分割框架. 中国图象图形学报. 2023(07): 2182-2194 . 百度学术
9.	王上，唐欢容. 一种基于混合粒子群优化算法的深度卷积神经网络架构搜索方法. 计算机应用研究. 2023(07): 2019-2024 . 百度学术
10.	朱光辉，祁加豪，朱振南，袁春风，黄宜华. 渐进式深度集成架构搜索算法研究. 计算机学报. 2023(10): 2041-2065 . 百度学术
11.	钟运琴，朱月琴，焦守涛. 边缘大数据分析预测建模方法研究. 高技术通讯. 2022(10): 1067-1075 . 百度学术
12.	包振山，秘博闻，张文博. 基于人工经验网络架构为初始化的NAS算法. 北京工业大学学报. 2021(08): 854-862 . 百度学术