Let’s say I have a set of sets, for example:
{
{1, 2, 3, 4, 5, 6, 7},
{1, 3, 4, 5, 6, 7, 8},
{5, 6, 7, 8},
{4, 7, 9},
}
I’d like to make some queries such as:
“which sets contain {3, 5, 7}
?”
This is probably a very similar problem that Search Engines need to solve when searching for multiple keywords. I suppose the obvious solution is to use a reverse index and have every element pointing to a list of references to sets that contain itself; and then somehow intersect those lists.
Is there something more efficient/clever?
Would the answer be different if all sets contained the same number of elements or they were reasonably bounded (e.g. 16 bits numbers) to something that could fit in a bit-array?