1
$\begingroup$

Suppose we have a universe of $u=|U|$ elements. We called a set of $H$ function $(U,m)$ order-preserving minimal perfect hash family (OPMPHF) if for every subset $M\subset U$ of size $m$ has at least one function $h\in H$ which is an over preserving minimal prefect hash. It is shown in [1,2] that for every $(U,m)$-OPMPHF $H$ obeys:

$$H=m! \cdot \left.\binom{u}{m}\middle/\left(\frac{u}{m}\right)^m\right. $$

Thus, the program length for any order preserving minimal perfect hash function should contain at least $\log_2 |H|$ bits.

In particular, if $m=3,u=8$, we have that $|H|\geq 17.7$.

However, I think I can create as set of $|H|=6$ functions for such family. For every $2\leq i\leq 7$ we define $f_i(x)$ to be equal $1$ if $x<i$, equal $2$ if $x=i$ and equal $3$ if $x\geq i$. Every function $f_i$ is order-preserving, and for each set $M$ with second element $i$ has a perfect function $f_i$.

Do I miss something in my analysis?

[1] Havas and Majewski, Optimal algorithms for minimal perfect hashing

[2] Kurt Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching, volume 1. Springer-Verlag, Berlin Heidelberg, New York, Tokyo, 1984

$\endgroup$
3
  • $\begingroup$ What is an order-preserving minimal perfect hash? $\endgroup$ May 20 '20 at 7:15
  • $\begingroup$ An order preserving minimal prefect hash function $f$ for a set $S\subset U$ satisfies the following properties: 1) For each $x,y\in S$ such that $x<y$ we have $f(x)<f(y)$ (order preserving). 2) The function $f:S\to {1,2..,|S|}$ is a bijection (minimal perfect hash). $\endgroup$ May 21 '20 at 8:00
  • $\begingroup$ Don't leave clarifications in the comments. Instead, please edit the question so that the question is self-contained and reads well for someone who encounters it for the first time. People shouldn't have to read the comments to understand what you are asking. $\endgroup$
    – D.W.
    May 21 '20 at 23:31
1
$\begingroup$

Reference [1] defines order-preserving as follows:

A hash function is order preserving if it puts entries into the hash table in a prespecified order.

In your case, this means that given any three elements $x,y,z \in \{1,\ldots,8\}$, you want there to be a hash function which maps $x$ to $1$, $y$ to $2$, $z$ to $3$.

In particular, it need not be the case that $x < y < z$.

If you add the assumption that $x < y < z$, then you can remove the $m!$ factor in the lower bound on $H$. The new lower bound states $H \geq 2.95$, that is, $H \geq 3$, which is not tight.

$\endgroup$

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.