Dictionary with sets as keys where lookup can be set intersection

Question

Normally, when working with dictionaries, we expect around O(1) complexity when we go to retrieve a value given the key (and when we insert). I work in Python, but this might apply to any dynamic typed language. I have been working with dictionaries where the keys are frozensets, which are just sets that are hashable and thus can be used as keys for your dictionary. I have a problem which would be magically solved if I could do "lookups" which are actually not key based, but set based. That is to say, it would be great if I had a data structure like a dictionary where I can pass in a set as a key and the data structure returns all values where the keys have a non-zero intersection with the key I passed in. I am quickly coming to the conclusion that this is never going to be O(1), but who knows. So, the question is, can we create a data structure that is basically a dictionary, but the keys are sets and it has a magic lookup ability where you can pass in a set and get all values back who's keys have non-zero intersection with the key (set) I passed in?

I imagined something to do with loading the values in. Firstly, you need keys that are sets of tuples (hashable). Then, when you load in a new value, you update the key to have a pointer to one other key and then these form long chains that do the job of getting you your sets of keys that meet the intersection criteria. This means that you push the complexity of insert way up, but lookup is fast. Apart from this, I have no idea, and I think a simple argument could be made that any such data structure will have either a bad O(N) insert or bad O(N) lookup, or both, where N is the number of keys.

Answer 1

Unfortunately, no, this isn't achievable (at least not if you want to handle arbitrary sets as keys).

The reason is simple: if $N$ denotes the number of elements in a key set, then it takes $O(N)$ time just to read all of those elements, and any correct algorithm will have to read all of those elements to handle a query.

There is a simple data structure that might suffice: a dictionary that maps from each element to a list of all keys that contain that element. Then, given a query set, you can iterate over all the elements in the query set, look them up in the dictionary, and check whether any of them are an element of any stored key.

While this is linear time in the size of the query set, note that the running time is only a constant factor of the time it takes to create the query set. So there is a sense in which this is a constant-factor overhead, and thus the best you could hope for (in asymptotic analysis).

Where you might be able to do better is if you knew there was some structure on how query sets were created. For instance, suppose every query set was created via the union of two prior query sets, the intersection of two prior query sets, or by inserting an element into a prior query set. Then we could improve on the above data structure. If you have some more specific situation, I suggest pondering exactly what are the operations the data structure has to be able to handle and then asking a new question about how to support those operations efficiently.

Answer 2

My understanding: You might have three values in the table with keys (a, b), (a, c), (b, c). When you lookup (d, e, c) you want the values for the keys (a, c) and (b, c) containing a “c”.

First you implement a hash-table like data structure where a key can occur multiple times. When a key/value set is added or removed to the original hash, all strings in its key set are added or removed in the second set.

Your lookup function in this second set would actually iterate and return all the values. And to lookup a set in the original hash, you lookup all strings in the key set in the second set.