# Data structure for or-lookups over bit-field associations maps

For a mapping between a bit-arrays and values I want cheap lookups using bitwise-or instead of equality.

Slightly more formally, I have a set of associations $$k_i \mapsto v_i$$ where $$k_i \in \mathcal{P}(\mathbb{N})$$ is a set of naturals and $$v_i$$ can be of any type $$T$$. A query on $$q \in \mathcal{P}(\mathbb{N})$$ matches pairs $$(k_j,v_j) \in \mathcal{P}(\mathbb{N}) \times T$$ such that $$k$$ overlaps with $$q$$ (ie $$q \cap k \neq \varnothing$$). Also the maximum element $$M$$ encountered in any $$k_i$$ is bounded, typically not larger than 5k and each $$k_i$$ is small $$|k_i| \ll M$$, ie the bitfield corresponding to the set $$k_i$$ would be sparse.

I imagine it could be a tree or a heap with (bitfield,a) values at the leaves and at each node a bitfield that is the bitwise-or combination of all bitfields in it's subtree? I failed to find any literature on the subject. Any pointers?

• Have you considered inverted indexes? – Pseudonym Apr 15 at 23:03
• Your notation is very strange. so $\{\mathbb{N}\}$ denotes a set of natural numbers? The usual meaning of this notation would be "the set containing one element, called $\mathbb{N}$". And then I don't understand the following statements: are $\{\mathbb{N}\}$ all referring to the same set? – 6005 Apr 16 at 3:14
• You are right, I rephrased, maybe it's a bit clearer now. – fakedrake Apr 16 at 9:45

## 1 Answer

Unfortunately I'm not aware of any data structure that will have better worst-case running time than a naive approach of simply a linear scan through the entire list of associations.

Therefore, if you want to solve this in practice, you will have to hope for some kind of structure that you can take advantage of (e.g., that most sets are sparse, that there are usually few overlaps, or something like that), and we won't be able to suggest algorithms without knowing those specifics.