Sunday, August 06, 2006

Globally unique identifiers

I really enjoyed listening to Tim Bray's talk on developing the ATOM specification on ITConversations. He made a lot of interesting points, but the one that resonated most was ATOM's requirement for a globally unique identifier for every feed and entry. With more syndication, we all see lots of duplicate material. Examples of duplication can readily be seen on rojo.com (used to be my customer, and I still enjoy their site a lot) and technorati.com: we end up with many URIs that refer to the same material.

It is possible to write software that detects duplicate feeds, but comparing two articles is not an inexpensive operation, and when comparing a very large number of feeds, the O(N^2) runtime is painful. I have experimented with much a less accurate algorithm: hash NGRAMs of articles and check for duplication using a hash lookup. I have found that this gives poor results - at least in my experiments. If you do partial matching of NGRAMs, you are back to O(N^2). (If anyone knows a good way to handle this, let me know :-)

Globally unique identifiers help solve many duplication problems, makes it easier to implement container relations, and in general ATOM just seems to be a better and more scalable platform than RSS 2.0 for complex new applications.

No comments: