# 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 '20 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 '20 at 3:14
• You are right, I rephrased, maybe it's a bit clearer now. – fakedrake Apr 16 '20 at 9:45

Preprocessing: For each $$(k_i, v_i)$$ pair, and for each $$x \in k_i$$, add $$(x, (k_i, v_i))$$ to a map data structure (e.g., a hashtable) with $$x$$ as the key.
To process a query $$q$$, for each $$y \in q$$ look up all values in the map, append all of them to a list, and finally remove duplicates (or instead add them directly to a data structure that can collapse duplicates immediately, like a hashtable).