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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Could you just use arithmetic coding? $\endgroup$
    – Zsbán Ambrus
    Commented Jun 13, 2014 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
    Commented Jun 13, 2014 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
    Commented Jun 13, 2014 at 19:56
  • $\begingroup$ @AriTrachtenberg - can you do that and support insertion/deletion/lookup in time depending only on $k$? $\endgroup$
    – R B
    Commented Jun 13, 2014 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
    Commented Jun 13, 2014 at 20:14

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Moreover, you can do it efficiently using "binomial encoding", described in several answers on this site and cs.se. $\endgroup$
    – Yuval Filmus
    Commented Jun 14, 2014 at 0:54
  • $\begingroup$ What you need is a constant-weight code (ideally perfect). See also cstheory.stackexchange.com/questions/19313/…. $\endgroup$
    – Ari Trachtenberg
    Commented Jun 15, 2014 at 18:56
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".

Improve this answer
$\endgroup$
1
  • $\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
    Commented Jun 13, 2014 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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