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?

  • 1
    $\begingroup$ Have you considered inverted indexes? $\endgroup$
    – Pseudonym
    Apr 15 '20 at 23:03
  • $\begingroup$ 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? $\endgroup$
    – 6005
    Apr 16 '20 at 3:14
  • $\begingroup$ You are right, I rephrased, maybe it's a bit clearer now. $\endgroup$
    – 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).


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.