RDF Graph Digest Techniques and Potential Applications

Sayers, Craig ; Karp, Alan H.

HP Development Company

关键词: RDF;    graph;    digest;    signature;    RDF applications;    Resource Description Framework;   

RP-ID  :  HPL-2004-95

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

Digests are short digital abbreviations computed from original content. This paper compares existing algorithms for computing the digest of a Resource Description Framework (RDF) graph and discusses potential applications. Digest computation is complicated by blank node relabeling and statement reordering. We treat these separately: surveying four techniques for handling blank node identity and three algorithms for dealing with statement ordering. It is possible to avoid the issue of blank nodes by limiting permissible graph operations, placing restrictions on allowable graph content, or modifying the RDF specification. Assuming none of those are reasonable, then practical solutions are still possible but they require adding additional information to the graph. To deal with statement ordering, the simplest approach is to use a sort with the attending O(Nlog(N))runtime. An incremental algorithm is also possible. This is theoretically faster, offering O(N) runtime but may be slower in practice for applications which do not benefit from the incrementality. Graph digests are applicable to digital signatures. Other applications include verifying integrity, detecting changes, generating content-based identifiers, and improving efficiency when accessing remote stores. 15 Pages