It's interesting to see that the main reason for the complexity of this task seems to lie, according to the authors, in the fact that the processing has to be done on Google's servers and thus needs to scale to a 100+ million users.

Would gmail be a desktop client, instead of a webmail, the problem would be much easier. But of course it would probably never get millions of users in the first place.

Yet, I'm pointing this out because while everyone can see the benefits of moving into the cloud, it's quite easy to forget that that in doing so we also give up on the processing power of the clients, and that their cumulative total is far from insignificant.

disclaimer: I'm working on a desktop client for gmail.