<p>1.56 bits per key is now possible using <a href="https://arxiv.org/abs/1910.06416" rel="nofollow noreferrer">"RecSplit: Minimal Perfect Hashing via Recursive Splitting" by Emmanuel Esposito, Thomas Mueller Graf, and Sebastiano Vigna</a>. It is quite expensive: 1,700 times more expensive than 1.79 bits per key!</p>

CC BY-SA 4.0
2019-11-04T05:33:12.227Z
2019-11-04T05:33:12.227Z
jbapple
<ul>
<li>2.09 bits per element is practically achievable. See <a href="http://cmph.sourceforge.net/" rel="noreferrer">http://cmph.sourceforge.net/</a>: "[Compress, Hash, Displace] can generate MPHFs that can be stored in approximately 2.07 bits per key."</li>
<li><p>1.44 bits per element is optimal. See</p>

<ul>
<li><p><a href="http://cmph.sourceforge.net/papers/esa09.pdf" rel="noreferrer">"Hash, displace, and compress"</a></p></li>
<li><p><a href="https://pdfs.semanticscholar.org/904e/4d8e7b6027ae131c9d8c3d2ec76889f6249b.pdf" rel="noreferrer">"Improved Bounds For Covering Complete Uniform Hypergraphs"</a></p></li>
<li><p><a href="https://people.mpi-inf.mpg.de/~mehlhorn/ftp/EATCSmonograph/chapter3.ps" rel="noreferrer"><em>Data Structures and Algorithms
, Vol. 1: Sorting and Searching</em>, Theorem III.2.3.6 (a)</a></p></li>
<li><p>Fredman, Michael L., and János Komlós. "On the size of separating systems and families of perfect hash functions." SIAM Journal on Algebraic Discrete Methods 5.1 (1984): 61-68.</p></li>
</ul></li>
</ul>

CC BY-SA 4.0
2018-05-07T01:29:37.223Z
2018-05-07T01:29:37.223Z
jbapple
<p>While we usually use large e.g. 64 bit hashes, there are many techniques to reduce this size, e.g. for savings in storage and transmission.</p>

<p>Popular <a href="https://en.wikipedia.org/wiki/Bloom_filter" rel="nofollow noreferrer">Bloom filter</a> instead of marking just 1 hash position in a bit table - indicating element in our database, marks $k$ random positions ($k$ hashes). Finally it requires $\lg(e)\cdot n \lg(1/p_f)$ bits for $n$ element database and $p_f$ probability of false positive - that it will accidentally answer that a given element is in the database, while it is not there. For example for $p_f=10^{-6}$ we need <strong>$\approx 29$ bits/hash</strong> this way.</p>

<p>We can reduce it further to $n \lg(n/p_f)-\lg(n!)\approx n(\lg(1/p_f)+\lg(e))$ bits if using a single bit table (size $n/p_f$ for $n$ elements and $p_f$ probability of false positive), but storing the $n$ values without information about their order - saving $\lg(n!)$ bits. It can be done e.g. by entropy coding of such bit table, and <a href="http://fabpedigree.com/james/appixm.htm" rel="nofollow noreferrer">there are also nice approximations</a>. This way we need <strong>$\approx 22$ bits/hash</strong> for $p_f=10^{-6}$.</p>

<p><strong>But what if we don't need to worry about false positives?</strong> - when we are certain that query will only regard objects from our database, expecting to return ID/position for a given hash. </p>

<p>I was able (<a href="https://arxiv.org/pdf/1206.4555" rel="nofollow noreferrer">paper</a>, <a href="https://www.dropbox.com/s/36hs1oug3l0tvt2/hashsem.pdf" rel="nofollow noreferrer">slides</a>) to get to asymptotically $(3/2+\gamma \lg(e))$ $\approx 2.33275$ <strong>bits/hash for this case and would like to ask if it can be further improved?</strong></p>

<p>Specifically, to get such low number we need to compress minimal prefix tree (<a href="https://en.wikipedia.org/wiki/Trie" rel="nofollow noreferrer">trie</a>) obtained for all our hashes - going to the first node distinguishing given hash/leaf in our database. </p>

<p>Assuming hashes are are $Pr(0)=Pr(1)=1/2$ random uncorrelated bit sequences (i.i.d.), we can calculate entropy as required to choose how many leaves are on the left of the root ($k$ out of $n$ with probability $p_{kn}={n \choose k}/2^n$) and then go recursively to both subtrees:</p>

<p>$$H_n=\sum_{k=0}^n p_{kn} \left( \lg\left(1/p_{kn}\right)+H_k+H_{n-k}\right)\to \approx 2.77544 n$$</p>

<p>We can reduce it further by not writing direction in internal degree 1 nodes - as it isn't required to distinguish elements, reducing by $1$ bit/degree 1 node: to $\approx 2.33275$ bits/hash. It can be approached by compressing the tree e.g. using the recurrence above (combining two degree 1 possibilities).</p>

<p>Some examples, $F_n$ denotes false positive probability - that a random value will get to a leaf, index $d$ means expanding at least to depth $d$, $D$ is average depth of all leaves:</p>

<p><a href="https://i.sstatic.net/PGTyi.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/PGTyi.png" alt="enter image description here"></a></p>

<p>It is a nice example of that "subtracting the order": $\lg(n!)$ bits can take us from $n \lg n$ to linear requirement - while length of label has go grow with logarithm of database size $(D_n\approx \lg(n)+1.33275)$, compressing all labels  together we can use asymptotically a constant number of bits/element.</p>

<p>My derivation assumed $Pr(0)=Pr(1)=1/2$ i.i.d. hash sequences - which seems the natural choice as they contain maximal amount of information, but technically there is still needed a proof if a different choice cannot improve it (and it becomes much more difficult) ... <strong>can this $\approx 2.33275$ bits/object "distinguishability constant" be further reduced?</strong></p>

<hr>

<p><strong>Update</strong>: let's formalize the problem: <strong>imagine you get n random potentially infinite bit sequences (hash values) - what is the minimal expected size of structure, which determines some injection from this set of hashes to {1,..,n}?</strong> </p>

<p>Looking at such formulation, <strong>I have just got down from ~2.33 to ~1.44 bits/element</strong>, however, the current algorithm is absolutely impractical.</p>

<p>So while the above construction used only prefixes, it might turn out it is more efficient to use different positions in obtained hashes. A more general approach might be:</p>

<ol>
<li>Basing on obtained hashes choose better (more distinguishing) positions and encode these positions.</li>
<li>For these chosen positions build minimal distinguishing tree as above.</li>
</ol>

<p>Previously we had trivial 1. (just prefixes), now let's look at approach with trivial 2.: choose position such that we get complete binary tree (constant depth, assume $n=2^m$) - where we don't need to encode the tree.</p>

<p>First position should have one half of 0 and 1, probability of finding it is ${n \choose n/2}/2^n$. Second should have half of 0 and 1 within both previous sets, and so on - finally the bits on the positions chosen this way uniquely determine all $n$ hashes.</p>

<p>We can encode distance to successive such position - it has geometric distribution $(1-p)^k p$ with entropy $h(p)=(-p \lg(p)-(1-p)\lg(1-p))/p$. </p>

<p>Finally summing over cost of writing positions halving all previous subsets, we get ($n=2^m$): </p>

<p>$$\sum_{i=1}^m h\left(\left({2^i \choose 2^{i-1}}/2^{(2^i)}\right)^{(2^{m-i})}  \right)  \to n\lg(e)$$</p>

<p>Numerics suggest that it quickly approaches $\lg(e)n\approx 1.4427 n$ bits (?)</p>

<p>While it is completely impractical - requiring testing exponential number of positions, there might be some practical intermediate algorithms: using both 1. and 2. It might be a valuable minimal description length lesson - of choosing features, still having cost of their description in consideration.</p>

<p><strong>There remains question if this 1.4427 bits/element is optimal?</strong> (now I doubt it)</p>

<p>To enforce the previous 2.33275 bits/element, we might require that the original lexicographic order is maintained.</p>

<hr>

<p>Update: Instead of pointing $m$ interesting position as above, <a href="https://www.reddit.com/r/compsci/comments/85ayys/improving_bloom_filter_can_we_distinguish/dvymdde/" rel="nofollow noreferrer">I was suggested</a> to build tree of positions to consider, what means replacing $h(p^k)$ with $kh(p)$ in the above formula. While it is much closer to a practical algorithm, it has turned out that it gives 2.544 bits/element instead.</p>

<p>To see that the previous recurrence approaches $\lg(e)\approx 1.44$ bits/element, imagine that we analogously search for just $m$ successive positions to get all $n=2^m$ length $m$ possibilities different. Its probability is $p=n!/n^n\approx e^{-n}$. For small $p$ we have $h(p)\approx -\lg(p)\approx n \lg(e)$.</p>

CC BY-SA 3.0
2018-03-18T14:36:59.973Z
A theoretical problem is compressing trees built from random hashes - minimal sufficient to distinguish/enumerate all hashes from our database. Leaf's (e.g. inorder) number can correspond to its position in the database. So practical application can be compressed structure which allows to translate hashes into ID/position. Usually this translation is made by database, but sending such cheap compressed structure we could shift this cost of translation to individual users - such that they can directly ask for ID.
Jarek Duda
CC BY-SA 3.0
2018-03-18T15:43:59.627Z
To formalize the problem: imagine you get n random potentially infinite bit sequences (hash values) - what is the minimal expected size of structure, which determines some injection from this set of hashes to {1,..,n}? The above construction uses ~2.33275n bits here, the question is if it can be reduced, e.g. using a different probability distribution in bit sequences of hashes (the same for all hashes)?
Jarek Duda
CC BY-SA 3.0
2018-03-18T16:55:08.967Z
There are known data structures that achieve (up to lower order terms) the information-theoretic optimal # bits/element. Look up "cuckoo filter", for instance.
David Eppstein
CC BY-SA 3.0
2018-03-18T17:09:24.383Z
Thank you, I will have to take a closer look, but looking at fig. 4 of [introductory cuckoo filter paper](https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf), it is comparable with Bloom filter - with its 44% overhead comparing to optimum I have mentioned in third paragraph above - e.g. 22 bits/element ... while here I am talking about working in completely different regime: ~2.3 bits/element - when we can focus only on queries from our database - only distinguish elements inside, not determine if given element belongs to our database.
Jarek Duda
CC BY-SA 3.0
2018-03-18T17:45:48.517Z
This ~n(lg(1/p)+lg(e)) optimum for Bloom-like situation is picture c) above - extend all hashes to large depth d, requiring nd - lg(n!) bits thanks to not storing their order. Here I am discarding the suffixes not distinguishing elements - gray part in the picture above: 1 bit/node of savings, leading to ~2.775n bits in fig. a) above. Additionally removing direction in degree 1 nodes, we get to extreme: ~2.33n bits in fig. d), at cost of completely loosing ability to determine that given hash does not belong to our database (false positive probability = 1).
Jarek Duda
<ds.data-structures><it.information-theory><tree><hash-function><db.databases>
Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?
Jarek Duda
# Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?

(Asked by: username_0 on 2018-03-18)

While we usually use large e.g. 64 bit hashes, there are many techniques to reduce this size, e.g. for savings in storage and transmission.

Popular [Bloom filter](https://en.wikipedia.org/wiki/Bloom_filter) instead of marking just 1 hash position in a bit table - indicating element in our database, marks $k$ random positions ($k$ hashes). Finally it requires $\lg(e)\cdot n \lg(1/p\_f)$ bits for $n$ element database and $p\_f$ probability of false positive - that it will accidentally answer that a given element is in the database, while it is not there. For example for $p\_f=10^{-6}$ we need **$\approx 29$ bits/hash** this way.

We can reduce it further to $n \lg(n/p\_f)-\lg(n!)\approx n(\lg(1/p\_f)+\lg(e))$ bits if using a single bit table (size $n/p\_f$ for $n$ elements and $p\_f$ probability of false positive), but storing the $n$ values without information about their order - saving $\lg(n!)$ bits. It can be done e.g. by entropy coding of such bit table, and [there are also nice approximations](http://fabpedigree.com/james/appixm.htm). This way we need **$\approx 22$ bits/hash** for $p\_f=10^{-6}$.

**But what if we don't need to worry about false positives?** - when we are certain that query will only regard objects from our database, expecting to return ID/position for a given hash.

I was able ([paper](https://arxiv.org/pdf/1206.4555), [slides](https://www.dropbox.com/s/36hs1oug3l0tvt2/hashsem.pdf)) to get to asymptotically $(3/2+\gamma \lg(e))$ $\approx 2.33275$ **bits/hash for this case and would like to ask if it can be further improved?**

Specifically, to get such low number we need to compress minimal prefix tree ([trie](https://en.wikipedia.org/wiki/Trie)) obtained for all our hashes - going to the first node distinguishing given hash/leaf in our database.

Assuming hashes are are $Pr(0)=Pr(1)=1/2$ random uncorrelated bit sequences (i.i.d.), we can calculate entropy as required to choose how many leaves are on the left of the root ($k$ out of $n$ with probability $p\_{kn}={n \choose k}/2^n$) and then go recursively to both subtrees:

$$H\_n=\sum\_{k=0}^n p\_{kn} \left( \lg\left(1/p\_{kn}\right)+H\_k+H\_{n-k}\right)\to \approx 2.77544 n$$

We can reduce it further by not writing direction in internal degree 1 nodes - as it isn't required to distinguish elements, reducing by $1$ bit/degree 1 node: to $\approx 2.33275$ bits/hash. It can be approached by compressing the tree e.g. using the recurrence above (combining two degree 1 possibilities).

Some examples, $F\_n$ denotes false positive probability - that a random value will get to a leaf, index $d$ means expanding at least to depth $d$, $D$ is average depth of all leaves:

[![enter image description here](https://i.sstatic.net/PGTyi.png)](https://i.sstatic.net/PGTyi.png)

It is a nice example of that "subtracting the order": $\lg(n!)$ bits can take us from $n \lg n$ to linear requirement - while length of label has go grow with logarithm of database size $(D\_n\approx \lg(n)+1.33275)$, compressing all labels together we can use asymptotically a constant number of bits/element.

My derivation assumed $Pr(0)=Pr(1)=1/2$ i.i.d. hash sequences - which seems the natural choice as they contain maximal amount of information, but technically there is still needed a proof if a different choice cannot improve it (and it becomes much more difficult) ... **can this $\approx 2.33275$ bits/object "distinguishability constant" be further reduced?**

---

**Update**: let's formalize the problem: **imagine you get n random potentially infinite bit sequences (hash values) - what is the minimal expected size of structure, which determines some injection from this set of hashes to {1,..,n}?**

Looking at such formulation, **I have just got down from ~2.33 to ~1.44 bits/element**, however, the current algorithm is absolutely impractical.

So while the above construction used only prefixes, it might turn out it is more efficient to use different positions in obtained hashes. A more general approach might be:

1. Basing on obtained hashes choose better (more distinguishing) positions and encode these positions.
2. For these chosen positions build minimal distinguishing tree as above.

Previously we had trivial 1. (just prefixes), now let's look at approach with trivial 2.: choose position such that we get complete binary tree (constant depth, assume $n=2^m$) - where we don't need to encode the tree.

First position should have one half of 0 and 1, probability of finding it is ${n \choose n/2}/2^n$. Second should have half of 0 and 1 within both previous sets, and so on - finally the bits on the positions chosen this way uniquely determine all $n$ hashes.

We can encode distance to successive such position - it has geometric distribution $(1-p)^k p$ with entropy $h(p)=(-p \lg(p)-(1-p)\lg(1-p))/p$.

Finally summing over cost of writing positions halving all previous subsets, we get ($n=2^m$):

$$\sum\_{i=1}^m h\left(\left({2^i \choose 2^{i-1}}/2^{(2^i)}\right)^{(2^{m-i})} \right) \to n\lg(e)$$

Numerics suggest that it quickly approaches $\lg(e)n\approx 1.4427 n$ bits (?)

While it is completely impractical - requiring testing exponential number of positions, there might be some practical intermediate algorithms: using both 1. and 2. It might be a valuable minimal description length lesson - of choosing features, still having cost of their description in consideration.

**There remains question if this 1.4427 bits/element is optimal?** (now I doubt it)

To enforce the previous 2.33275 bits/element, we might require that the original lexicographic order is maintained.

---

Update: Instead of pointing $m$ interesting position as above, [I was suggested](https://www.reddit.com/r/compsci/comments/85ayys/improving_bloom_filter_can_we_distinguish/dvymdde/) to build tree of positions to consider, what means replacing $h(p^k)$ with $kh(p)$ in the above formula. While it is much closer to a practical algorithm, it has turned out that it gives 2.544 bits/element instead.

To see that the previous recurrence approaches $\lg(e)\approx 1.44$ bits/element, imagine that we analogously search for just $m$ successive positions to get all $n=2^m$ length $m$ possibilities different. Its probability is $p=n!/n^n\approx e^{-n}$. For small $p$ we have $h(p)\approx -\lg(p)\approx n \lg(e)$.

**Tags:** ds.data-structures, it.information-theory, tree, hash-function, db.databases

> **Comments:**
> **username_0**: A theoretical problem is compressing trees built from random hashes - minimal sufficient to distinguish/enumerate all hashes from our database. Leaf's (e.g. inorder) number can correspond to its position in the database. So practical application can be compressed structure which allows to translate hashes into ID/position. Usually this translation is made by database, but sending such cheap compressed structure we could shift this cost of translation to individual users - such that they can directly ask for ID.  
> **username_0**: To formalize the problem: imagine you get n random potentially infinite bit sequences (hash values) - what is the minimal expected size of structure, which determines some injection from this set of hashes to {1,..,n}? The above construction uses ~2.33275n bits here, the question is if it can be reduced, e.g. using a different probability distribution in bit sequences of hashes (the same for all hashes)?  
> **username_1**: There are known data structures that achieve (up to lower order terms) the information-theoretic optimal # bits/element. Look up "cuckoo filter", for instance.  
> **username_0**: Thank you, I will have to take a closer look, but looking at fig. 4 of [introductory cuckoo filter paper](https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf), it is comparable with Bloom filter - with its 44% overhead comparing to optimum I have mentioned in third paragraph above - e.g. 22 bits/element ... while here I am talking about working in completely different regime: ~2.3 bits/element - when we can focus only on queries from our database - only distinguish elements inside, not determine if given element belongs to our database.  
> **username_0**: This ~n(lg(1/p)+lg(e)) optimum for Bloom-like situation is picture c) above - extend all hashes to large depth d, requiring nd - lg(n!) bits thanks to not storing their order. Here I am discarding the suffixes not distinguishing elements - gray part in the picture above: 1 bit/node of savings, leading to ~2.775n bits in fig. a) above. Additionally removing direction in degree 1 nodes, we get to extreme: ~2.33n bits in fig. d), at cost of completely loosing ability to determine that given hash does not belong to our database (false positive probability = 1).  

---

## 2 answers

### Answer by username_2 on 2018-05-07. Score: 7 | Accepted answer

* 2.09 bits per element is practically achievable. See <http://cmph.sourceforge.net/>: "[Compress, Hash, Displace] can generate MPHFs that can be stored in approximately 2.07 bits per key."
* 1.44 bits per element is optimal. See

  + ["Hash, displace, and compress"](http://cmph.sourceforge.net/papers/esa09.pdf)
  + ["Improved Bounds For Covering Complete Uniform Hypergraphs"](https://pdfs.semanticscholar.org/904e/4d8e7b6027ae131c9d8c3d2ec76889f6249b.pdf)
  + [*Data Structures and Algorithms
    , Vol. 1: Sorting and Searching*, Theorem III.2.3.6 (a)](https://people.mpi-inf.mpg.de/~mehlhorn/ftp/EATCSmonograph/chapter3.ps)
  + Fredman, Michael L., and János Komlós. "On the size of separating systems and families of perfect hash functions." SIAM Journal on Algebraic Discrete Methods 5.1 (1984): 61-68.


---

### Answer by username_2 on 2019-11-04. Score: 4

1.56 bits per key is now possible using ["RecSplit: Minimal Perfect Hashing via Recursive Splitting" by Emmanuel Esposito, Thomas Mueller Graf, and Sebastiano Vigna](https://arxiv.org/abs/1910.06416). It is quite expensive: 1,700 times more expensive than 1.79 bits per key!


---

