1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Is $N^S$ less than $2^{64}$? $\endgroup$
    – jbapple
    Jan 10, 2023 at 14:43
  • $\begingroup$ No, $S \le 32$. $\endgroup$ Jan 10, 2023 at 14:57
  • $\begingroup$ The difference between $O(\log N)$, $O(S)$ and even $O(1)$ seems likely to be swamped by the constant factors. So I'm not convinced that analyzing this using asymptotic analysis is going to be useful to you in practice. $\endgroup$
    – D.W.
    Jan 10, 2023 at 19:53

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I don't think this preserves order (your first requirement that $i < j \rightarrow f(t_i) < f(t_j)$). $\endgroup$
    – jbapple
    Jan 15, 2023 at 20:21
  • $\begingroup$ @jbapple The function is a hash table that contains tuple indexes. $\endgroup$ Jan 15, 2023 at 22:49

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.