2
$\begingroup$

More precisely: The input is set of $M$ sets (most likely stored sequentially on disk) that contain partitions of the set $\{1..N\}$. I want to efficiently (as far as memory and time complexity goes) represent this structure. Let's call this hypothetical structure $S$. I need the structure to support just a single function $p : S \times \{1 \ldots N\} \rightarrow \{1 \ldots M\}$.

It's also safe to assume that I will call this function in order, meaning I will be interested first in $p(S, 1)$, then in $p(S,2)$, etc.

I can represent this structure as an array of $N \times \lceil log_2(M)\rceil$ bits, but that seems too memory inefficient when $M$ is small and $N$ is in billions. I have a hunch that perfect-hashing might be of use here.

$\endgroup$
  • $\begingroup$ Perfect hashing won't help you here; if the distribution of values in the codomain is flat and random (i.e. there are no correlations higher than zero-order), any perfect hash function which represents the function exactly must itself require at least $N \log M$ bits for its representation. $\endgroup$ – Pseudonym Sep 27 '14 at 14:42
  • $\begingroup$ Just to clarify, are the partitions of 1..N sequential or arbitrary? Eg is a partition {{1,3},{2}} of {1,2,3} allowed? $\endgroup$ – jkff Sep 29 '14 at 6:17
  • $\begingroup$ Sadly arbitrary, otherwise I could represent the data in O(M), which would have been ideal. $\endgroup$ – TheCuriousOne Sep 29 '14 at 6:24
4
$\begingroup$

You can reduce your $N \lceil \log_2 M \rceil$ bits to $\lceil N \log_2 M\rceil$ by using Dodis et al's "Changing Base without Losing Space".

I don't think you're going to get much smaller than $N \log_2 M$ bits. For $N \gg M$, many functions will be surjective. In particular, there are $\{{N \atop M}\}$ surjective functions, which is at least $M^{N-M}$. Thus, at least $\log_2 \left(M^{N-M}\right) = N \log_2 M - M \log_2 M \in \Omega(N \log_2 M)$ bits must be used to represent one, on average.

$\endgroup$
  • $\begingroup$ Given that it will be called in order, arithmetic coding will also do the trick. $\endgroup$ – Pseudonym Sep 27 '14 at 14:38
  • $\begingroup$ Thanks. @Pseudonym could you elaborate, please? I do not see how calling in order relates to the arithmetic coding. $\endgroup$ – TheCuriousOne Sep 28 '14 at 14:56
  • $\begingroup$ Think of compressing a file via your favourite compression tools, like zlib. Tools like that support compressing and decompressing a file in order from start to finish. This is basically the same as calling the function in order. You have to get trickier if you need random access. $\endgroup$ – Pseudonym Sep 29 '14 at 2:29
1
$\begingroup$

You essentially want to store a compressed string of size N, with characters from an alphabet of size M. I suspect that wavelet trees http://www.dcc.uchile.cl/~gnavarro/ps/cpm12.pdf may be exactly what you need. They are a "succinct data structure", which means they take almost the information-theoretically optimal amount of space.

$\endgroup$
  • $\begingroup$ Yes, that is another way to phrase it. I will take a look, thanks for the suggestion. $\endgroup$ – TheCuriousOne Sep 29 '14 at 6:25
  • $\begingroup$ You may want to read about "rank/select dictionaries" first - they are a key primitive used in wavelet trees, and generally a very useful data structure (e.g. you can partition a range 0..N and look up which range a number belongs to in essentially O(1), which is actually much faster than binary search not only in theory but in practice). $\endgroup$ – jkff Sep 29 '14 at 16:07

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.