Fingerprints for Testing Multi Set Equality

Problem

Let $\vec v = (v_1, ..., v_d) \in \mathbb{R}^d$ be a vector, such that $\exists$ some positive integer $M$, $\forall i \in [d], v_i \in [M]$. Assume that $d$ is very large and $\vec v$ is sparse, so it is represented by a set of pairs that record the non-zero positions and values of $\vec v:$

A fingerprint $h( \vec v) \in \mathbb{R}$ is a succinct summary of $\vec v$, which can be used to test whether two vectors $\vec{v}, \vec{u} \in \mathbb{R}^d$ are equal.

Goal: For a given $\delta \in (0, 1)$, find an $h: \mathbb{R}^d \rightarrow \mathbb{R}$, such that, $\forall \vec v, \vec u \in \mathbb{R}^d$, if $\vec v \neq \vec u$, then

$$\Pr [ h( \vec v) = h ( \vec u) ] \le \delta.$$

Solution

Theorem. Let $p \ge \max\{ d / \delta, M \}$ be a prime number and let $a$ be an integer generated from $1$ to $p - 1$ uniformly at random. Then

$$h( \vec v ) \doteq \sum_{i \in [d] } v_i \cdot a^i$$

satisfies the goal.

Remark. It is easy to see that fingerprint is a linear summary:

Proof. $\forall \vec v, \vec u \in \mathbb{R}^d$, if $\vec v \neq \vec u$, if $h( \vec v) = h ( \vec u)$, then

However, the polynomial $p(x) \doteq \sum_{i \in [d] } (v_i - u_i) \cdot x^i$ has at most $d$ distinct roots. As $p(0) = 0$, it has at most $d - 1$ distinct non-zero root. The probability that $a \neq 0$ being one of them is bounded by

$\square$

$h (\vec v)$ can be computed by the following pseudo-codes:

1. $h \leftarrow 0$.
2. For $(i, v_i) \in S( \vec v):$
3. $\qquad$ $h \leftarrow h + v_i \cdot a^i$.
4. Return $h$.

Reference

[1] G. Cormode and K. Yi, Small Summaries for Big Data, 1st ed. Cambridge University Press, 2020.