Assume an ordered set $M = \{\tau_1, \tau_2, ..., \tau_n\}$ and a subset $S = \{\tau_k,\tau_l,...,\tau_m\}\subset M$ where $1\leq k,l,m \leq n$. All the items of $S$ are randomly ordered.

The task is to transform the set $M$ to set $S$ using the least amount of data.

The naive approach is to use a set of indexes $I=\{k, l, ..., m\}$ and take the items from set $M$ and reconstruct $S$. If we assume that $n=65536$ then each index would take $\log_2(n)=16$ bits, using a total of 128KiB. If I am not mistaken this is $\Theta(nlog_2n)$ space complexity.

Are there algorithms or data structures that are able to archive better space complexity characteristics? A possible trade off is false positive probabilities i.e. having to items with the same index (that can detected by using a hash of $S$).

I considered the Bloomier Filter algorithm, where $\tau_j$ is the key and the index is the value, unfortunately the data structure becomes bigger than the naive method.

If it is important, the set items are fixed size 256 bits long (sha256 hashes).


Your Answer

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

Browse other questions tagged or ask your own question.