Somewhat unrelated, but I realized that Facebook has tons of face/name data from all the tagged photos. Not only do they have photos tagged with names, but they also know who your friends are, thus who is most likely to be in your photos. I imagine Facebook + Riya could be pretty accurate.

So... when are they going to roll out an (optional) auto-tagging feature?