Perfect ordered hash function on ordered sequence

Question

I have a sequence of integer tuples $t_1, t_2,..., t_N$ of different sizes in lexicographic order, e.g.:

$(1, 1), (1, 2), (1, 3, 5), (1, 3, 6), (1, 5), (3), (3, 2, 3), (3, 7), (3, 8, 1), ...$

• sequence length is $N \le 10^9 \space (2^{30})$,
• a tuple size bounded by $S, |t| \le S \le 32$,
• $i$-th element of a tuple is bounded: $0 \le x_i \le s_i$, $s_i \le N, \prod{s_i} > 2^{64}$

Currently I use tuple indexes in the sequence as keys in some associative array, I can search the sequence for a tuple index in $O(\log N)$.

I want to create a substitute for tuple indexes,
a function $f(t)$ that maps a tuple into a $64$-bit integer and has following qualities:

• preservation of the order: $i < j \rightarrow f(t_i) < f(t_j)$
• time of calculation of $f(t)$ is better than $O(\log N)$, ideally $O(S)$
• preprocessing time is $O(SN)$, requires $O(N)$ additional memory
• the sequence is the domain of $f$, behavior of $f$ for any other tuple is undefined
• given $f(t)$ value it is possible to find $t$ in $O(\log N)$ time

The motivation/context: I'm trying to improve performance of an in-memory OLAP cube. The tuples are indexes of unique values in data columns.

Answer 1

I believe you're looking for "monotone minimal perfect hashing".

Answer 2

How I solved the problem:
$f(t_i) = i$, but it is possible to find element index quickly by using several static hash tables.

Construction

There are hash functions $h_1, h_2, h_3$ with codomains $1..M_1, 1..M_2, 1..M_3$ which are almost universal.

1. Allocate array $K_1$ of length $2M_1$ and fill it with zeros, for every element $t_i$ in the sequence calculate $j_1 = h_1(t_i)$,
   store $i$ in the array $K_1[j_1] = i$, if $K_1[j_1]$ is already occupied (a collision) then $K_1[j_1] = -1$ and mark $i$ for the next round.
2. Allocate array $K_2$ of length $2M_2$ and fill it with zeros, for every previously marked element calculate $j_2 = h_2(t_i)$,
   store $i$ in the array $K_2[j_2] = i$, if $K_2[j_2]$ is already occupied (a collision) then $K_2[j_2] = -1$ and mark $i$ for the next round.
3. Allocate array $K_3$ of length $2M_3$ and fill it with zeros, for every marked element calculate $j_3 = h_3(t_i)$,
   store $i$ in the array $K_3[j_3] = i$, if $K_3[j_3]$ is already occupied (a collision) then $K_3[j_3] = -1$.

Calculation

1. For a given $t$ calculate $j_1 = K_1[h_1(t)]$, if $j_1 > 0$ then $f(t) = j_1$
2. else calculate $j_2 = K_2[h_2(t)]$, if $j_2 > 0$ then $f(t) = j_2$
3. else calculate $j_3 = K_3[h_3(t)]$, if $j_3 > 0$ then $f(t) = j_3$
4. else find $f(t)$ with old good binary search.

If $M_1 = 2N, M_2 = N, M_3= N/2$ then on average there will be $1$ binary search in $1024$ calls of $f$
(apply 3 times formula for expected number of collisions in a hash table with size $N$ and number of elements $M$: $\frac{M(M-1)}{2N}$).

There is a lot of fine tuning ahead like choosing the right functions, their codomain sizes, hash table sizes but "smoke" performance tests on both live and synthetic datasets are quite promising.

The idea came from BBHash which is a modern minimum perfect function.