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...) the

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).