一种高效的RDF图模式匹配算法  

An Efficient Matching Algorithm for RDF Graph Patterns

作　　者：汪锦岭[1] 金蓓弘[1] 李京[1] 

机构地区：[1]中国科学院软件研究所软件工程技术中心,北京100080

出　　处：《计算机研究与发展》2005年第10期1763-1770,共8页Journal of Computer Research and Development

基　　金：国家"九七三"重点基础研究发展规划基金项目(2002CB312005);国家自然科学基金项目(60173023);国家"八六三"高技术研究发展计划基金项目(2001AA113010)

摘　　要：随着越来越多的信息被表示为RDF格式,如何高效地对RDF信息进行分发和过滤成为一个重要的问题·在语义Web环境下的信息分发系统中,输入的RDF信息需要和大量的用户订阅条件进行匹配,而用户的订阅条件可以被表示为RDF图模式·根据RDF图的特点,并对其增加了一些约束,设计了一种新的RDF图模式匹配算法·实验结果表明,该算法的匹配效率远远高于传统的图模式匹配算法·The semantic Web is increasingly accepted as the next generation of WWW. The foundation of semantic Web is resource description framework （RDF）. As more and more information is represented in RDF format, the efficient dissemination and filtering of RDF information becomes an important problem. In information dissemination systems under the semantic Web, input RDF data should be matched with a database of user profiles, which can be represented as RDF graph patterns. Based on the characteristics of RDF and several restrictions on the RDF graph, a novel matching algorithm is proposed for RDF graph patterns. RDF graph and RDF patterns are all traversed from a special node to form BFS trees; the matching state of two BFS trees are represented as an AND-OR tree to avoid backtracking. RDF patterns are indexed according to the concept model to further improve efficiency. Experimental results show that the algorithm is much more efficient than conventional graph matching algorithms.

关 键 词：吾义Web RDF 图模式 匹配算法 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]