In this paper, we propose and evaluate a scheme to produce canonical labels for
blank nodes in RDF graphs. These labels can be used as the basis for a
Skolemisation scheme that gets rid of the blank nodes in an RDF graph by
mapping them to globally canonical IRIs. Assuming no hash collisions, the
scheme guarantees that two Skolemised graphs will be equal if and only if the
two input graphs are isomorphic. Although the proposed scheme is exponential in
the worst case, we claim that such cases are unlikely to be encountered in
practice. To support these claims, we present the results of applying our
Skolemisation scheme over a diverse collection of 43.5 million real-world RDF
graphs (BTC-2014); we also provide results for some nasty synthetic cases.