ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2018, Vol. 55 ›› Issue (3): 651-661.doi: 10.7544/issn1000-1239.2018.20160845

Previous Articles     Next Articles

Parallel Algorithms for RDF Type-Isomorphism on GPU

Feng Jiaying1,3, Zhang Xiaowang1,3, Feng Zhiyong2,3   

  1. 1(School of Computer Science and Technology, Tianjin University, Tianjin 300350); 2(School of Computer Software, Tianjin University, Tianjin 300350); 3(Tianjin Key Laboratory of Cognitive Computing and Application, Tianjin 300350)
  • Online:2018-03-01

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.

Key words: resource description framework, SPARQL query processing, subgraph isomorphism, type-isomorphism, graphic processing units

CLC Number: