For what it's worth, I recently implemented something similar for my work application, to keep a one-bit-per-node vector of "messages seen". In my case, those flags are updated whenever the server attempts to deliver the node to the user, and this hasn't caused a significant extra load (with the busiest site serving a choice of 27k nodes to 24k users, and sharing the web and database servers with 21 other live sites).

We use the information to specify the class of the node title as 'seen' or 'unseen', and it has made it far easier to find new information in a useful fashion.

For PM, the size of the vector would be larger, but updating it only as a result of an explicit request would balance that. I suspect the main difficulty would be the UI design: individually selecting a subset of 100 or more checkboxes on Newest Nodes would be unpleasant.

Hugo