Jump to content United States-English
HP.com Home Products and Services Support and Drivers Solutions How to Buy
» Contact HP

HP.com home

Technical Reports


HP Labs

» Research
» News and events
» Technical reports
» About HP Labs
» Careers @ HP Labs
» People
» Worldwide sites
» Downloads
Content starts here

Click here for full text: PDF

RDF Graph Digest Techniques and Potential Applications

Sayers, Craig; Karp, Alan H.


Keyword(s): RDF; graph; digest; signature; RDF applications; Resource Description Framework

Abstract: 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

Back to Index

»Technical Reports

» 2009
» 2008
» 2007
» 2006
» 2005
» 2004
» 2003
» 2002
» 2001
» 2000
» 1990 - 1999

Heritage Technical Reports

» Compaq & DEC Technical Reports
» Tandem Technical Reports
Printable version
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.