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?
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).