[FridgeSeal]

I was thinking about just this thing recently, although more from a search perspective: notably, how do I build a full text search index where different users can see different amounts of the documents, ideally without storing multiple copies of the documents. I’m convinced there’s some clever data structures that might allow this to happen, but I haven’t found them yet.

[hansvm]

Without any additional constraints (e.g. that users/documents are clustered, that each user only has access to a small or large subset of documents, etc...) there aren't any great solutions. No matter the data structure, with n documents and m users you need on average at least nm bits in addition to the space to store the documents. Document insertion is at least an O(m) operation, and user insertion is at least an O(n) operation (for any fixed data structure on average across all possible user-document mappings of that size).