Section 6.5: Retrieval on Secondary Keys

Exercise 19. [M22] [M22] Analyze the ABD(8,5) of (15), as (13) has been analyzed in (14): How many of the 32 locations must be searched for an average query with k bits unspecified? How many must be searched in the worst case?

Verified: yes
Solve time: 3m54s

---

The error in the previous solution comes from treating ABD(8,5) as if query elements were randomly scattered across rows. In fact, ABD has a rigid bit-structured partition, so row occupancy is determined combinatorially by how the query’s fixed bits intersect the row index bits.

We restart from the correct structure.

1. Structure of ABD$(8,5)$

Each 8-bit key $x$ is decomposed as

$$ x = (a,b), $$

where:

• $a \in {0,1}^5$ determines the row (32 rows total),
• $b \in {0,1}^3$ determines the position within the row (8 entries per row).

Thus:

• Each row corresponds to a fixed 5-bit prefix $a$,
• Each row contains all 8 possible 3-bit suffixes $b$.

A query therefore does not “hit random rows”; it restricts the set of possible prefixes $a$ in a structured way.

Each accessed row costs exactly 8 location examinations.

2. Query model

A query with $k$ bits unspecified means:

• $8-k$ bit positions are fixed,
• $k$ bit positions are free.

So the query describes a subcube of size $2^k$ in ${0,1}^8$.

We analyze how many distinct row prefixes $a$ are compatible with this subcube.

3. Correct characterization of accessed rows

A row indexed by $a \in {0,1}^5$ is accessed if and only if:

• The fixed bits in the query that lie in the prefix part do not contradict $a$.

Let:

• $T$ = number of fixed query bits that fall inside the 5 prefix-bit positions.

Then:

• Those $T$ bits fix $T$ bits of $a$,
• The remaining $5-T$ prefix bits are free.

Hence the number of compatible rows is exactly:

$$ #\text{rows} = 2^{5-T}. $$

This is deterministic once $T$ is known.

4. Distribution of $T$

The $8-k$ fixed bit positions are chosen uniformly among the 8 bit positions.

Among the 8 positions:

• 5 belong to the row index,
• 3 belong to the within-row suffix.

Thus:

$$ T \sim \text{Hypergeometric}(8,5,8-k). $$

So:

$$ \Pr(T=t)

\frac{\binom{5}{t}\binom{3}{(8-k)-t}}{\binom{8}{8-k}}, $$

with valid range determined by feasibility:

$$ 0 \le t \le 5, \quad 0 \le 8-k-t \le 3. $$

5. Average number of rows accessed

We compute expectation directly from the correct structure:

$$ \mathbb{E}[#\text{rows}]

\sum_{t} 2^{5-t} \cdot \frac{\binom{5}{t}\binom{3}{8-k-t}}{\binom{8}{8-k}}. $$

Factor out $2^5 = 32$:

$$ \mathbb{E}[#\text{rows}]

32 \sum_{t} 2^{-t} \cdot \frac{\binom{5}{t}\binom{3}{8-k-t}}{\binom{8}{8-k}}. $$

Each accessed row requires 8 location inspections, so:

$$ \boxed{ \mathbb{E}[\text{locations searched}]

256 \sum_{t} 2^{-t} \cdot \frac{\binom{5}{t}\binom{3}{8-k-t}}{\binom{8}{8-k}} }. $$

This replaces the incorrect independence-based binomial model with the correct structured hypergeometric analysis.

6. Worst-case number of locations searched

To maximize the number of rows accessed, we minimize $T$, since:

$$ #\text{rows} = 2^{5-T}. $$

We can choose the fixed bit positions adversarially (worst case).

To minimize $T$, we place as many fixed bits as possible in the 3 suffix positions.

Let $8-k$ be the number of fixed bits. Then:

• At most 3 fixed bits can avoid the prefix,
• Any remaining fixed bits must lie in the prefix.

Hence:

$$ T_{\min} = \max\bigl(0, (8-k) - 3\bigr). $$

Thus:

$$ #\text{rows}{\max} = 2^{5 - T{\min}}. $$

Each row costs 8 accesses, so:

$$ \boxed{ \text{Worst-case locations searched}

8 \cdot 2^{5 - \max(0,,5-k)} } $$

since $(8-k)-3 = 5-k$.

We can simplify piecewise:

• If $k \ge 5$: $T_{\min}=0$, so worst case is $8 \cdot 32 = 256$.
• If $k < 5$: $T_{\min}=5-k$, so

$$ \text{worst case} = 8 \cdot 2^{k}. $$

Thus:

$$ \boxed{ \text{Worst-case locations searched}

\begin{cases} 256, & k \ge 5,\[4pt] 8 \cdot 2^k, & k < 5. \end{cases} } $$

7. Final answer

$$ \boxed{ \mathbb{E}[\text{locations searched}]

256 \sum_{t} 2^{-t} \frac{\binom{5}{t}\binom{3}{8-k-t}}{\binom{8}{8-k}} } $$

$$ \boxed{ \text{Worst case}

\begin{cases} 256, & k \ge 5,\ 8 \cdot 2^k, & k < 5. \end{cases} } $$

The key correction is that ABD queries are structured subcubes of the 8-bit space, so row access is governed by how fixed bits intersect the 5-bit row index, not by probabilistic occupancy of independent samples.