Approximate Membership Problem

In the approximate membership problem, we have subset $S \subset U$ , that supports two operations:

update( $x$ ): $S \leftarrow S \cup \{x\}$
query( $x$ ): return True if $x\in S$ else False.

where $U$ is the domain that elements $x$ belongs to. If $U = 2^{32}$ , then each representation of $x$ takes $32$ bits. If $U = 2^{64}$ , then each $x$ needs $64$ bits. If $U$ is the website address, the length of its elements might is unlimited. Suppose that the average length is about $15$ chars, and each char takes $8$ bits, then the representation could occupy most $120$ bits.

We can solve the membership problem exactly by dictionaries, such as balanced-binary search tree and hash set. This requires space $O(n \log U)$ bits. If we allows false positive, we can break this bound.

The idea is to have a bit array $A$ with length $O(kn)$ bits and a pairwise hash family $H$ that maps the elements in $U$ uniformly at random to each bit in the array. After picking a hash function uniformly at random from $H$ , the operation on $S$ is performed as follows:

update( $x$ ): $A[h(x)] \leftarrow 1$
query( $x$ ): return True if $A[h(x)] = 1$ else False.

We can only make a mistake if an element $y \notin S$ and $A[h(y)] = 1$ . However, the probability of such event is bounded by

\Pr[\exists x \in S, s.t., h(x) = h(y)] \le \sum_{x \in S} \Pr[h(x) = h(y)] = \frac{n}{m} = \frac{1}{k}

Remark: the accurate probability is given by

1 - \Pr[\forall x \in S, s.t., h(x) \neq h(y)] = 1 - (1 - \frac{1}{m})^n \le \frac{n}{m}

To amplify the failure probability to a specified threshold $\delta$ , we can set $k = \frac{1}{\delta}$ . A more efficient way is by repetition the array $\ln \frac{1}{\delta} /\ln k$ times. Then the overall space usage is

\frac{ n k \ln \frac{1}{\delta} }{ \ln k }

Note that $f(k) = \frac{k}{\ln k} \ge e$ , since it holds that $y = x - e\ln x$ (click to see the plot) for $x > 0$ :

y' = 1 - e / x = 0 \longrightarrow x = e.

When $k = e$ the space usage is

ne \ln \frac{1}{\delta}

The compress ratio is given by

\frac{\log U}{e \ln \frac{1}{\delta} }

If we require the failure probability $\delta = 1 / 100$ , then $\ln 1 / \delta \approx 4.6$ , and $e \ln 1/\delta \approx 12.5 \le 13$ . That is, we need on $13$ bits for each element in $S$ , and the average number of operations for updating $S$ is $5$ , which is about $1/2$ space when $U = 2^{32}$ , $1/5$ space when $U = 2^{64}$ , and much less when $U$ is the set of possible web addresses.

Remark

There is another implementation that use a single bit array $A$ of size $m$ but $k$ hash functions $h_1, h_2, ..., h_k$ . We initialization by setting

For $x \in S$ :
$\qquad$ set $A[h_i(x)] = 1$ for all $i \in [k]$ .

As a result, at most $kn$ bits of $A$ are initialized to be 1.

Now, for an element $x' \notin S$ , we accidentally report it as a member $\in S$ if $h_i(x') = 1$ for all $i \in [k]$ . But the probability that

\Pr[h_i(x') = 1] \le \frac{kn}{m}

and

\Pr[h_i(x') = 1, \forall i \in [k]] \le (\frac{kn}{m} )^k

If we use $k = \ln \frac{1}{\delta}$ hash functions and set the size $m = ne \ln \frac{1}{\delta}$ , we can also achieve failure probability $\delta$ .

Question to ponder: what is $S$ is dynamic?