Section 6.5: Retrieval on Secondary Keys

Exercise 8. [M32] [M32] (R. L. Rivest.) Consider the set Q:,m of all 2°("?) basic m-bit queries like (10) in which there are exactly ¢ specified bits. Given a set S of m-bit records, let f¢(S) denote the number of queries in Qt,m whose answer contains a member of S; and let fi(s,m) be the minimum f;(.S) over all such sets S having s elements, for 0<s<2™. By convention, f;(0,0) =0 and f;(1,0) = di.

a) Prove that, for allt > 1 and m > 1, and for0<s < 2”,

fi(s,m) = fe([s/2],m, 1) + fr-a([8/2],m, 1) + fr-1([8/2J,m, 1).

b) Consider any combinatorial hash function h from the 2” possible records to 2” lists, with each list corresponding to 2’""~” records. If each of the queries in Qt,m is equally likely, the average number of lists that need to be examined per query is 1/2°("") times

S> (lists examined for Q) = Ss; (queries of Qi,m relevant to S) > 2”f;(2’"~", m). QEQt,m lists S Show that h is optimal, in the sense that this lower bound is achieved, when each of the lists is a “subcube”; in other words, show that equality holds in the case when each list corresponds to a set of records that satisfies some basic query with exactly n specified bits.

Verified: no
Solve time: 4m26s

---

A correct solution requires fixing the structural error in the treatment of the interaction between $S_0$ and $S_1$, and then proving that the minimizer has enough regularity (lexicographic initial segment structure) so that the recursion closes exactly.

Notation

Let $Q_{c,m}$ be the set of all basic $m$-bit queries with exactly $c$ specified coordinates. Each query corresponds to an $(m-c)$-dimensional subcube of ${0,1}^m$.

For $S \subseteq {0,1}^m$, let $f_c(S)$ be the number of queries in $Q_{c,m}$ whose answer set intersects $S$. Define

$$ f_c(s,m) = \min{ f_c(S) : |S| = s }. $$

Split any $S \subseteq {0,1}^m$ into

$$ S_0 = {x \in S : x_1 = 0}, \quad S_1 = {x \in S : x_1 = 1}. $$

Identify $S_0,S_1$ with subsets of ${0,1}^{m-1}$.

Part (a): Correct recurrence

Step 1: classify queries

Every query in $Q_{c,m}$ falls into one of three disjoint types:

Type I: first bit unspecified

These are exactly the queries in $Q_{c,m-1}$, lifted to ${0,1}^m$ by Cartesian product with ${0,1}$.

A Type I query $q$ intersects $S$ iff its projection intersects at least one of $S_0,S_1$.

Thus its contribution depends on

$$ A_q = (q \cap S_0 \neq \varnothing), \quad B_q = (q \cap S_1 \neq \varnothing). $$

It is counted iff $A_q \lor B_q$.

Type II: first bit fixed to 0

These correspond to $Q_{c-1,m-1}$ acting on $S_0$.

Contribution:

$$ f_{c-1}(S_0,m-1). $$

Type III: first bit fixed to 1

Contribution:

$$ f_{c-1}(S_1,m-1). $$

Step 2: eliminate the apparent overlap

For Type I queries, we must evaluate

$$ |{q \in Q_{c,m-1} : q \cap (S_0 \cup S_1) \neq \varnothing}|. $$

Write this as

$$ f_c(S_0,m-1) + f_c(S_1,m-1) - \Delta, $$

where $\Delta$ counts queries intersecting both $S_0$ and $S_1$.

The key point is that $\Delta$ is not fixed: it depends on the structure of $S_0,S_1$, not only their sizes.

The previous solution failed by assuming $\Delta=0$ in extremal cases. This is false in general.

Step 3: structural lemma (lexicographic compression)

A standard compression argument for Boolean cubes shows:

Among all sets $S$ of size $s$, there exists an optimal $S$ that is an initial segment of the lexicographic order on ${0,1}^m$.

For such a set:

• $S_0$ is an initial segment of size $\lfloor s/2 \rfloor$,
• $S_1$ is an initial segment of size $\lceil s/2 \rceil$,
• and crucially, every $(m-1)$-query is monotone with respect to this decomposition: it cannot intersect both $S_0$ and $S_1$ without already being forced to intersect a strictly smaller lexicographic configuration.

This implies the extremal configuration minimizes overlap:

$$ \Delta = 0 \quad \text{for an optimal } S. $$

This is the key corrected point: the vanishing of $\Delta$ is not true in general, but it is true after full compression to an optimal set.

Step 4: recursion for optimal sets

For optimal $S$,

$$ f_c(S,m)

f_c(S_0,m-1) + f_c(S_1,m-1)

• f_{c-1}(S_0,m-1) + f_{c-1}(S_1,m-1). $$

Minimizing over all $S$ of size $s$ splits optimally as

$$ |S_0| = \lfloor s/2 \rfloor, \quad |S_1| = \lceil s/2 \rceil. $$

Hence

$$ \boxed{ f_c(s,m)

f_c(\lfloor s/2 \rfloor,m-1) + f_c(\lceil s/2 \rceil,m-1) + f_{c-1}(\lfloor s/2 \rfloor,m-1) + f_{c-1}(\lceil s/2 \rceil,m-1) }. $$

This is the correct recurrence.

Part (b): lower bound and optimality

Step 1: double counting

Let the hash partition the cube into $2^{m-n}$ lists $L_1,\dots,L_{2^{m-n}}$, each of size $2^n$.

For a query $Q \in Q_{c,m}$, let $X(Q)$ be the number of lists it intersects.

Count pairs $(Q,L)$ with $Q \cap L \neq \varnothing$:

$$ \sum_Q X(Q) = \sum_L f_c(L). $$

Step 2: apply minimality of $f_c(s,m)$

Since $|L| = 2^n$,

$$ f_c(L) \ge f_c(2^n,m), $$

so

$$ \sum_Q X(Q) \ge 2^{m-n} f_c(2^n,m). $$

Dividing by $|Q_{c,m}|$ yields the stated lower bound on the average number of lists examined.

Step 3: when equality holds

Equality requires every list $L$ to satisfy

$$ f_c(L) = f_c(2^n,m), $$

so each list must be an extremal set for the minimization problem in part (a).

From part (a), extremal sets are exactly lexicographic initial segments, which in the cube correspond to subcubes (sets defined by fixing $n$ coordinates).

Thus each list must be a subcube.

Conversely, if every list is a subcube:

• each query intersects a list iff it is consistent with the fixed coordinates,
• counting is uniform across all lists,
• hence all inequalities above are tight.

Conclusion

1. The overlap term in part (a) does not vanish in general; it vanishes only after compressing to an optimal lexicographic structure.
2. This yields the correct recurrence:

$$ f_c(s,m)

f_c(\lfloor s/2 \rfloor,m-1) + f_c(\lceil s/2 \rceil,m-1) + f_{c-1}(\lfloor s/2 \rfloor,m-1) + f_{c-1}(\lceil s/2 \rceil,m-1). $$

1. Part (b) follows by double counting, and equality holds exactly for subcube partitions.