4
$\begingroup$

Assume you have universe $\mathcal{U}=\{e_1,e_2,\ldots e_N\}$.

If we like to encode an ordered sequence of $k$ elements from $\mathcal{U}$, it's not hard to argue that $k\log |\mathcal{U}|$ bits are needed.

I'd like to be able to have a "Set" data structure, which take advantage of the fact that the set is unordered to save memory.

It seems that theoretically (information bound), we could only use $k\log \frac{|\mathcal{U}|}{k}$ bits for encoding the set, but I was wondering if such result is known.

I considered looking into implementations of current set structures in popular programming languages, but assumed they'll be more optimized for runtime rather than memory, so my questions are:

  • Is there a known data structure that allows storing $k$ elements set using $k\log \frac{|\mathcal{U}|}{k} + O(1)$ bits (supporting adding and deleting items of course)?

  • What is the best runtime of such structure?

I'm well aware we could probably save some memory by hashing (if $k << \mathcal{U}$), but I'm looking for a deterministic structure.

$\endgroup$
  • $\begingroup$ Could you just use arithmetic coding? $\endgroup$ – Zsbán Ambrus Jun 13 '14 at 14:59
  • $\begingroup$ @ZsbánAmbrus - I'm not sure I follow. Doesn't arithmetic coding encodes ordered words? How can I use it to encode an unordered set of letters without having to save the additional bits required for saving the order? $\endgroup$ – R B Jun 13 '14 at 15:49
  • $\begingroup$ You can implement the information-theoretic optimum by listing out (or computing) all ${n \choose k}$ possible subsets of length $k$ and giving each a binary encoding of $\log {n \choose k} \in O(k \log \frac{n}{k} )$ bits. $\endgroup$ – Ari Trachtenberg Jun 13 '14 at 19:56
  • $\begingroup$ @AriTrachtenberg - can you do that and support insertion/deletion/lookup in time depending only on $k$? $\endgroup$ – R B Jun 13 '14 at 19:59
  • 1
    $\begingroup$ @R B - Insertion / deletion of set elements or into the universal set? The problem didn't say anything about the running time of insertions/deletions. $\endgroup$ – Ari Trachtenberg Jun 13 '14 at 20:14
0
$\begingroup$

You can implement the information-theoretic optimum by listing out (or computing) all ${n \choose k}$ possible subsets of length $k$ and giving each a binary encoding of $log{n \choose k} \in O(k \, log \frac{n}{k})$ bits.

$\endgroup$
5
$\begingroup$

What you're looking for is called a "succinct" or "implicit" dictionary. The best solution I know of is Backyard cuckoo hashing, by Arbitman et al from FOCS 2010, which "guarantees constant-time [insert, delete, lookup] operations in the worst case with high probability" while using $B + o(B)$ bits, where $B$ is the lower bound you mention.

If you need updates, I don't know if you'll be able to beat $O\left(\sqrt{B}\right)$ redundancy, given the lower bounds in Brodnik et al.'s "Resizable Arrays in Optimal Time and Space".

$\endgroup$
  • $\begingroup$ Thanks for the answer. While this gets close, they still sacrifice space optimality for $O(1)$ worst case runtime. I'm hoping for a data structure which is first optimal by memory consumption (even if it means $O(k)$ time per operation). I'll accept the answer in a few days if no one comes up with a smaller structure (this $o(B)$ could be costly for my purpose). $\endgroup$ – R B Jun 13 '14 at 8:54

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.