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

随着越来越多的信息被表示为RDF格式,如何高效地对RDF信息进行分发和过滤成为一个重要的问题·在语义Web环境下的信息分发系统中,输入的RDF信息需要和大量的用户订阅条件进行匹配,而用户的订阅条件可以被表示为RDF图模式·根据RDF图的特点,并对其增加了一些约束,设计了一种新的RDF图模式匹配算法·实验结果表明,该算法的匹配效率远远高于传统的图模式匹配算法·

An Efficient Matching Algorithm for RDF Graph Patterns

The semantic Web is increasingly accepted as the next generation of WWW. The fo undation of semantic Web is resource description framework (RDF). As more and m ore information is represented in RDF format, the efficient dissemination and filtering of RDF information becomes an important problem. In information dissem ination 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. Base d on the characteristics of RDF and several restrictions on the RDF graph, a nov el matching algorithm is proposed for RDF graph patterns. RDF graph and RDF pat terns 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. RD F patterns are indexed according to the concept model to further improve efficie ncy. Experimental results show that the algorithm is much more efficient than c onventional graph matching algorithms.