Let me fix the notation and write in python for simplicity.

What you call an ENTITY is a set of dictionaries labeled by 'keys' with
lists of objects as values. For simplicity let's assume that values are
numbers (but what we truly need is just comparison operation)

```
E1 = {
{'k1': [4], 'k2': [20,12]},
{'k4': [2,20,25], 'k3': [2,3]}
}
E2 = {
{'k2': [2,3,4], 'k4': [2], 'k3': [14]},
{'k3': [1]},
{'k3': [12,23]}
}
```

Input is just a dictionary, again labeled by 'keys' and with lists of
objects as values.

```
INPUT = {'k2': [2], 'k3': [14,12] }
```

I think you should keep arrays of values in sorted order. This should
allow you to compare lists for a given key in linear time. In total the
complexity for given input should be O(EKL), where E is a number of
entities, K is a number of keys and L is the length of the list. Similarly,
it will take O(EKL) memory.

I expect that with your bounds comparison in this case will take up to
several seconds. If this is not enough then let's think further :)

--

EDIT: You can simply use a set of tuples (entity_id, set_id, key,
value), with a balanced BST as an index for values. Then search should take
around O(log n). Have you thought about a structure like this?