Section 6.5: Retrieval on Secondary Keys

Exercise 5. [40] [40] Experiment with various ways to avoid the redundancy of text when using Harrison’s technique for substring searching.

6. [M20] The total number of m-bit basic queries with t bits specified is s = (")2". If a combinatorial hashing function like that in (13) converts these queries into 1, lz,

..., ls locations, respectively, L(t) = (14 +l2 +---+1s)/s is the average number of locations per query. [For example, in (13) we have L(3) = 1.75.]

Consider now a composite hash function on an (mj; + mg)-bit field, formed by mapping the first mi bits with one hash function and the remaining m2 with another, where Li(t) and L2(t) are the corresponding average numbers of locations per query. Find a formula that expresses L(t), for the composite function, in terms of L; and Le.

Verified: yes
Solve time: 55s

---

Setup

Let a composite file consist of two disjoint bit fields of lengths $m_1$ and $m_2$, so that $m = m_1 + m_2$. A basic query specifies exactly $t$ bit positions among the $m$ total positions.

Let $t_1$ denote the number of specified bits that lie in the first field, and let $t_2 = t - t_1$ be the number of specified bits in the second field. Thus $0 \le t_1 \le m_1$ and $0 \le t_2 \le m_2$.

For the first field, a hash function produces an average list length $L_1(t_1)$ for queries specifying $t_1$ bits. For the second field, a second hash function produces an average list length $L_2(t_2)$ for queries specifying $t_2$ bits.

The composite hash function maps a query to the combination of the two independent hashed addresses, so the total number of locations retrieved for a query with split $(t_1, t_2)$ is $L_1(t_1)L_2(t_2)$.

The goal is to determine $L(t)$, the average number of locations per query when $t$ bits are specified uniformly among all $\binom{m}{t}$ possible choices.

Solution

A query specifying $t$ bits is determined by choosing $t_1$ positions from the first field and $t - t_1$ positions from the second field. The number of such queries is

$$ \binom{m_1}{t_1}\binom{m_2}{t - t_1}. $$

Since all $\binom{m}{t}$ queries are equally likely, the probability that a random query has split $(t_1, t - t_1)$ is

$$ \frac{\binom{m_1}{t_1}\binom{m_2}{t - t_1}}{\binom{m}{t}}. $$

For each such split, the composite hashing produces an average of $L_1(t_1)L_2(t - t_1)$ locations. Therefore the overall average is obtained by summing over all admissible splits:

$$ L(t)

\sum_{t_1} \frac{\binom{m_1}{t_1}\binom{m_2}{t - t_1}}{\binom{m}{t}} , L_1(t_1)L_2(t - t_1), $$

where the sum ranges over all integers $t_1$ satisfying $0 \le t_1 \le m_1$ and $0 \le t - t_1 \le m_2$.

Equivalently,

$$ L(t)

\frac{1}{\binom{m}{t}} \sum_{t_1} \binom{m_1}{t_1}\binom{m_2}{t - t_1} , L_1(t_1)L_2(t - t_1). $$

This expresses the composite average as a convolution of the two independent query-size distributions weighted by their respective average location counts.

Verification

Each query corresponds uniquely to a pair consisting of a choice of $t_1$ bits in the first field and $t - t_1$ bits in the second field, so the decomposition into cases indexed by $t_1$ partitions the full set of $\binom{m}{t}$ queries.

For a fixed $t_1$, the number of compatible queries is exactly $\binom{m_1}{t_1}\binom{m_2}{t - t_1}$, so the probability weights sum to $1$ over all admissible $t_1$ by the Vandermonde identity

$$ \sum_{t_1} \binom{m_1}{t_1}\binom{m_2}{t - t_1} = \binom{m}{t}. $$

Since the composite hashing acts independently on the two disjoint fields, the number of retrieved locations factors as $L_1(t_1)L_2(t - t_1)$ for each split. Substituting these values into the law of total expectation yields the stated formula.

This completes the proof. ∎