{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T20:29:11Z","timestamp":1792787351923,"version":"4.5.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,7,25]],"date-time":"2017-07-25T00:00:00Z","timestamp":1500940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Fondecyt","award":["11140900"],"award-info":[{"award-number":["11140900"]}]},{"name":"Millennium Nucleus Center for Semantic Web Research","award":["NC120004"],"award-info":[{"award-number":["NC120004"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Web"],"published-print":{"date-parts":[[2017,11,30]]},"abstract":"<jats:p>\n                    Existential blank nodes greatly complicate a number of fundamental operations on Resource Description Framework (RDF) graphs. In particular, the problems of determining if two RDF graphs have the same structure modulo blank node labels (i.e., if they are\n                    <jats:italic>isomorphic<\/jats:italic>\n                    ), or determining if two RDF graphs have the same meaning under simple semantics (i.e., if they are\n                    <jats:italic>simple-equivalent<\/jats:italic>\n                    ), have no known polynomial-time algorithms. In this article, we propose methods that can produce two canonical forms of an RDF graph. The first canonical form preserves isomorphism such that any two isomorphic RDF graphs will produce the same canonical form; this\n                    <jats:italic>iso-canonical<\/jats:italic>\n                    form is produced by modifying the well-known canonical labelling algorithm N\n                    <jats:sc>auty<\/jats:sc>\n                    for application to RDF graphs. The second canonical form additionally preserves simple-equivalence such that any two simple-equivalent RDF graphs will produce the same canonical form; this\n                    <jats:italic>equi-canonical<\/jats:italic>\n                    form is produced by, in a preliminary step, leaning the RDF graph, and then computing the iso-canonical form. These algorithms have a number of practical applications, such as for identifying isomorphic or equivalent RDF graphs in a large collection without requiring pairwise comparison, for computing checksums or signing RDF graphs, for applying consistent Skolemisation schemes where blank nodes are mapped in a canonical manner to Internationalised Resource Identifiers (IRIs), and so forth. Likewise a variety of algorithms can be simplified by presupposing RDF graphs in one of these canonical forms. Both algorithms require exponential steps in the worst case; in our evaluation we demonstrate that there indeed exist difficult synthetic cases, but we also provide results over 9.9 million RDF graphs that suggest such cases occur infrequently in the real world, and that both canonical forms can be efficiently computed in all but a handful of such cases.\n                  <\/jats:p>","DOI":"10.1145\/3068333","type":"journal-article","created":{"date-parts":[[2017,7,25]],"date-time":"2017-07-25T08:14:39Z","timestamp":1500970479000},"page":"1-62","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Canonical Forms for Isomorphic and Equivalent RDF Graphs"],"prefix":"10.1145","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9482-1982","authenticated-orcid":false,"given":"Aidan","family":"Hogan","sequence":"first","affiliation":[{"name":"Center for Semantic Web Research, DCC, University of Chile, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,7,25]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Foundations of modern graph query languages. CoRR abs\/1610.06264","author":"Angles Renzo","year":"2016","unstructured":"Renzo Angles , Marcelo Arenas , Pablo Barcel\u00f3 , Aidan Hogan , Juan L. Reutter , and Domagoj Vrgoc . 2016. Foundations of modern graph query languages. CoRR abs\/1610.06264 ( 2016 ), 1--50. http:\/\/arxiv.org\/abs\/1610.06264 Renzo Angles, Marcelo Arenas, Pablo Barcel\u00f3, Aidan Hogan, Juan L. Reutter, and Domagoj Vrgoc. 2016. Foundations of modern graph query languages. CoRR abs\/1610.06264 (2016), 1--50. http:\/\/arxiv.org\/abs\/1610.06264"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.01.003"},{"key":"e_1_2_1_3_1","volume-title":"Graph isomorphism in quasipolynomial time. CoRR abs\/1512.03547","author":"Babai L\u00e1szl\u00f3","year":"2015","unstructured":"L\u00e1szl\u00f3 Babai . 2015. Graph isomorphism in quasipolynomial time. CoRR abs\/1512.03547 ( 2015 ), 1--89. http:\/\/arxiv.org\/abs\/1512.03547 L\u00e1szl\u00f3 Babai. 2015. Graph isomorphism in quasipolynomial time. CoRR abs\/1512.03547 (2015), 1--89. http:\/\/arxiv.org\/abs\/1512.03547"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209047"},{"key":"e_1_2_1_5_1","unstructured":"David Beckett Tim Berners-Lee Eric Prud\u2019hommeaux and Gavin Carothers. 2014. RDF 1.1 Turtle -- Terse RDF Triple Language. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/turtle\/.  David Beckett Tim Berners-Lee Eric Prud\u2019hommeaux and Gavin Carothers. 2014. RDF 1.1 Turtle -- Terse RDF Triple Language. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/turtle\/."},{"key":"e_1_2_1_6_1","unstructured":"David Booth. 2012. Well Behaved RDF: A Straw-Man Proposal for Taming Blank Nodes. Retrieved from http:\/\/dbooth.org\/2013\/well-behaved-rdf\/Booth-well-behaved-rdf. pdf.  David Booth. 2012. Well Behaved RDF: A Straw-Man Proposal for Taming Blank Nodes. Retrieved from http:\/\/dbooth.org\/2013\/well-behaved-rdf\/Booth-well-behaved-rdf. pdf."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_2_1_8_1","unstructured":"Gavin Carothers. 2014. RDF 1.1 N-Quads. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/n-quads\/.  Gavin Carothers. 2014. RDF 1.1 N-Quads. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/n-quads\/."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39718-2_24"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983673"},{"key":"e_1_2_1_11_1","unstructured":"Richard Cyganiak David Wood and Markus Lanthaler. 2014. RDF 1.1 Concepts and Abstract Syntax. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/rdf11-concepts\/.  Richard Cyganiak David Wood and Markus Lanthaler. 2014. RDF 1.1 Concepts and Abstract Syntax. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/rdf11-concepts\/."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061323"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1331904.1331908"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 4th International Semantic Web Conference (ISWC\u201905)","author":"Giereth Mark","year":"2005","unstructured":"Mark Giereth . 2005 . On partial encryption of RDF-graphs. In The Semantic Web - ISWC 2005 , Proceedings of the 4th International Semantic Web Conference (ISWC\u201905) . Springer, 308--322. Mark Giereth. 2005. On partial encryption of RDF-graphs. In The Semantic Web - ISWC 2005, Proceedings of the 4th International Semantic Web Conference (ISWC\u201905). Springer, 308--322."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065187"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346334"},{"key":"e_1_2_1_17_1","unstructured":"Bernardo Cuenca Grau Boris Motik Zhe Wu Achille Fokoue and Carsten Lutz. 2009. OWL 2 Web Ontology Language: Profiles. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/owl2-profiles\/.  Bernardo Cuenca Grau Boris Motik Zhe Wu Achille Fokoue and Carsten Lutz. 2009. OWL 2 Web Ontology Language: Profiles. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/owl2-profiles\/."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.04.009"},{"key":"e_1_2_1_19_1","unstructured":"Steve Harris Andy Seaborne and Eric Prud\u2019hommeaux. 2013. SPARQL 1.1 Query Language. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/sparql11-query\/.  Steve Harris Andy Seaborne and Eric Prud\u2019hommeaux. 2013. SPARQL 1.1 Query Language. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/sparql11-query\/."},{"key":"e_1_2_1_20_1","unstructured":"Patrick Hayes. 2004. RDF Semantics. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/2004\/REC-rdf-mt-20040210\/.  Patrick Hayes. 2004. RDF Semantics. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/2004\/REC-rdf-mt-20040210\/."},{"key":"e_1_2_1_21_1","volume-title":"Patel-Schneider","author":"Hayes Patrick","year":"2014","unstructured":"Patrick Hayes and Peter F . Patel-Schneider . 2014 . RDF 1.1 Semantics. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/2014\/REC-rdf11-mt-20140225\/. Patrick Hayes and Peter F. Patel-Schneider. 2014. RDF 1.1 Semantics. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/2014\/REC-rdf11-mt-20140225\/."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-79432-2","volume-title":"Linked Data: Evolving the Web into a Global Data Space.","author":"Heath Tom","year":"2011","unstructured":"Tom Heath and Christian Bizer . 2011 . Linked Data: Evolving the Web into a Global Data Space. Vol. 1 , Issue 1. Morgan 8 Claypool . 1--136 pages. Tom Heath and Christian Bizer. 2011. Linked Data: Evolving the Web into a Global Data Space. Vol. 1, Issue 1. Morgan 8 Claypool. 1--136 pages."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90282-K"},{"key":"e_1_2_1_24_1","volume-title":"Ivan Herman, Ben Adida, Manu Sporny, and Mark Birbeck. 2013. RDFa 1.1 Primer --","year":"2013","unstructured":"Ivan Herman, Ben Adida, Manu Sporny, and Mark Birbeck. 2013. RDFa 1.1 Primer -- Second Edition -- Rich Structured Data Markup for Web Documents. W3C Working Group Note . (22 Aug. 2013 ). http:\/\/www.w3.org\/TR\/rdfa-primer\/. Ivan Herman, Ben Adida, Manu Sporny, and Mark Birbeck. 2013. RDFa 1.1 Primer -- Second Edition -- Rich Structured Data Markup for Web Documents. W3C Working Group Note. (22 Aug. 2013). http:\/\/www.w3.org\/TR\/rdfa-primer\/."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 11th International Workshop on Scalable Semantic Web Knowledge Base Systems co-located with the 14th International Semantic Web Conference (ISWC\u201915) (CEUR Workshop Proceedings)","volume":"1457","author":"Hern\u00e1ndez Daniel","year":"2015","unstructured":"Daniel Hern\u00e1ndez , Aidan Hogan , and Markus Kr\u00f6tzsch . 2015 . Reifying RDF: What works well with wikidata? . In Proceedings of the 11th International Workshop on Scalable Semantic Web Knowledge Base Systems co-located with the 14th International Semantic Web Conference (ISWC\u201915) (CEUR Workshop Proceedings) , Vol. 1457 . 32--47. http:\/\/ceur-ws.org\/Vol-1457\/SSWS2015_paper3.pdf. Daniel Hern\u00e1ndez, Aidan Hogan, and Markus Kr\u00f6tzsch. 2015. Reifying RDF: What works well with wikidata?. In Proceedings of the 11th International Workshop on Scalable Semantic Web Knowledge Base Systems co-located with the 14th International Semantic Web Conference (ISWC\u201915) (CEUR Workshop Proceedings), Vol. 1457. 32--47. http:\/\/ceur-ws.org\/Vol-1457\/SSWS2015_paper3.pdf."},{"key":"e_1_2_1_26_1","unstructured":"Edzard H\u00f6fig and Ina Schieferdecker. 2014. Hashing of RDF graphs and a solution to the blank node problem. In Proceedings of the 10th International Workshop on Uncertainty Reasoning for the Semantic Web (URSW\u201914) co-located with the 13th International Semantic Web Conference (ISWC\u201914) (CEUR Workshop Proceedings) Vol. 1259. 55--66. http:\/\/ceur-ws.org\/Vol-1259\/method2014_submission_1.pdf.  Edzard H\u00f6fig and Ina Schieferdecker. 2014. Hashing of RDF graphs and a solution to the blank node problem. In Proceedings of the 10th International Workshop on Uncertainty Reasoning for the Semantic Web (URSW\u201914) co-located with the 13th International Semantic Web Conference (ISWC\u201914) (CEUR Workshop Proceedings) Vol. 1259. 55--66. http:\/\/ceur-ws.org\/Vol-1259\/method2014_submission_1.pdf."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741653"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2014.06.004"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2012.02.001"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.13"},{"key":"e_1_2_1_31_1","unstructured":"Tobias K\u00e4fer and Andreas Harth. 2014. Billion Triples Challenge data set. Retrieved from http:\/\/km.aifb.kit.edu\/projects\/btc-2014\/.  Tobias K\u00e4fer and Andreas Harth. 2014. Billion Triples Challenge data set. Retrieved from http:\/\/km.aifb.kit.edu\/projects\/btc-2014\/."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07443-6_11"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Tobias Kuhn and Michel Dumontier. 2014. Trusty URIs: Verifiable immutable and permanent digital artifacts for linked data. In ESWC. 395--410.  Tobias Kuhn and Michel Dumontier. 2014. Trusty URIs: Verifiable immutable and permanent digital artifacts for linked data. In ESWC. 395--410.","DOI":"10.1007\/978-3-319-07443-6_27"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-016-0945-9"},{"key":"e_1_2_1_35_1","volume-title":"Swick","author":"Lassila Ora","year":"1999","unstructured":"Ora Lassila and Ralph R . Swick . 1999 . Resource Description Framework (RDF) Model and Syntax Specification. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/1999\/REC-rdf-syntax-19990222\/. Ora Lassila and Ralph R. Swick. 1999. Resource Description Framework (RDF) Model and Syntax Specification. W3C Recommendation. Retrieved from http:\/\/www.w3.org\/TR\/1999\/REC-rdf-syntax-19990222\/."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500130"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25073-6_27"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920859"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIC.2002.1067737"},{"key":"e_1_2_1_40_1","volume-title":"Congressum Numerantium","volume":"30","author":"McKay Brendan","year":"1980","unstructured":"Brendan McKay . 1980 . Practical graph isomorphism . In Congressum Numerantium , Vol. 30 . 45--87. Brendan McKay. 1980. Practical graph isomorphism. In Congressum Numerantium, Vol. 30. 45--87."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2012.03.004"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11964-9_18"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/028\/14"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/2786088.2786090"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Reinhard Pichler Axel Polleres Fang Wei and Stefan Woltran. 2008. dRDF: Entailment for domain-restricted RDF. In ESWC. 200--214.  Reinhard Pichler Axel Polleres Fang Wei and Stefan Woltran. 2008. dRDF: Entailment for domain-restricted RDF. In ESWC. 200--214.","DOI":"10.1007\/978-3-540-68234-9_17"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.09.035"},{"key":"e_1_2_1_48_1","volume-title":"Search space contraction in canonical labeling of graphs (preliminary version). CoRR abs\/0804.4881","author":"Piperno Adolfo","year":"2008","unstructured":"Adolfo Piperno . 2008. Search space contraction in canonical labeling of graphs (preliminary version). CoRR abs\/0804.4881 ( 2008 ). http:\/\/arxiv.org\/abs\/0804.4881 Adolfo Piperno. 2008. Search space contraction in canonical labeling of graphs (preliminary version). CoRR abs\/0804.4881 (2008). http:\/\/arxiv.org\/abs\/0804.4881"},{"key":"e_1_2_1_49_1","volume-title":"Dagstuhl Follow-Ups","volume":"5","author":"Savenkov Vadim","year":"2013","unstructured":"Vadim Savenkov . 2013 . Algorithms for core computation in data exchange. In Data Exchange, Integration, and Streams . Dagstuhl Follow-Ups , Vol. 5 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 38--68. Vadim Savenkov. 2013. Algorithms for core computation in data exchange. In Data Exchange, Integration, and Streams. Dagstuhl Follow-Ups, Vol. 5. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 38--68."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11964-9_16"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.57"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062745.1062848"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629489"}],"container-title":["ACM Transactions on the Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3068333","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3068333","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:03:44Z","timestamp":1750201424000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3068333"}},"subtitle":["Algorithms for Leaning and Labelling Blank Nodes"],"short-title":[],"issued":{"date-parts":[[2017,7,25]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11,30]]}},"alternative-id":["10.1145\/3068333"],"URL":"https:\/\/doi.org\/10.1145\/3068333","relation":{},"ISSN":["1559-1131","1559-114X"],"issn-type":[{"value":"1559-1131","type":"print"},{"value":"1559-114X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,7,25]]},"assertion":[{"value":"2016-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}