Two guest lists at one door

A conference has an invited list and a checked-in list. Both are sorted by badge number:

invited    3   8  14  21  34  55
checked    1   8  13  21  22  34  89

The people who may enter are on both lists: $\{8,21,34\}$. One method starts again at the top of checked for every invited badge. Another puts one finger on each list.

At 3 and 1, badge 1 is too small. Because the invited list is sorted, 1 cannot reappear later there. Advance only the checked-in finger. At 3 and 8, the same argument discards 3. Equality emits an answer and advances both.

One comparison has ruled out an entire future possibility. Order is doing the work.

For two query terms $a$ and $b$, Boolean AND asks for the set intersection

$$P(a) \cap P(b),$$

where $P(t)$ is the set of documents containing term $t$. OR is union and a AND NOT b is relative complement. The index has turned words into ordinary set algebra over integers.

The reference walk

Let $A[1:m]$ and $B[1:n]$ be strictly increasing sequences. The reference algorithm carries two forward-only indices.

MERGE-INTERSECT(A, B)
Input:  strictly increasing sequences A[1:m] and B[1:n]
Output: the strictly increasing sequence A intersect B

i ← 1
j ← 1
R ← empty sequence
while i ≤ m and j ≤ n
    if A[i] = B[j]
        append A[i] to R
        i ← i + 1
        j ← j + 1
    else if A[i] < B[j]
        i ← i + 1
    else
        j ← j + 1
return R

The loop invariant is the whole proof:

Initially both prefixes are empty. On equality, the shared value belongs in the answer and strict increase means it occurs nowhere else. If $A[i] < B[j]$, then every unconsumed value in $B$ is at least $B[j]$, so $A[i]$ can never match; advancing $i$ is safe. The other inequality is symmetric. When either list ends, no further pair can match. Thus R is exactly $A\cap B$.

Every iteration advances at least one index and neither retreats. The time is $O(m+n)$ comparisons and the working space is $O(1)$ beyond the output. If the consumer accepts a stream, the result need not be retained at all.

The bound is tight for this algorithm, but not for every instance. Consider

A = [47]
B = [4, 6, 10, 12, 14, 16, 18, 20, 22, 32, 47, 81, ...]

A merge walks ten losing values before reaching 47. Sorted random access lets the short list ask a sharper question: where could 47 occur in the remaining suffix of $B$?

Gallop, then close the bracket

Binary search from the beginning of $B$ for every member of $A$ costs $O(m\log n)$. It throws away information: after searching for $A[i]$, the next target $A[i+1]$ is larger, so it cannot lie before the position just reached.

A finger search retains that position. A galloping search probes offsets $1,2,4,8,\ldots$ until it passes the target, then binary-searches only the bracket just found.

GALLOP-LOWER-BOUND(B, start, target)
Input:  strictly increasing B[1:n], valid start, target not before B[start]
Output: least j at or after start with B[j] ≥ target, or n + 1

if start > n or B[start] ≥ target
    return start
step ← 1
while start + step ≤ n and B[start + step] < target
    step ← 2 × step
low ← start + step / 2 + 1
high ← min(start + step, n)
while low ≤ high
    middle ← low + floor((high - low) / 2)
    if B[middle] < target
        low ← middle + 1
    else
        high ← middle - 1
return low

GALLOP-INTERSECT(A, B)
Input:  strictly increasing A[1:m] and B[1:n], with m ≤ n
Output: the strictly increasing sequence A intersect B

j ← 1
R ← empty sequence
for each value x in A
    j ← GALLOP-LOWER-BOUND(B, j, x)
    if j > n
        return R
    if B[j] = x
        append x to R
        j ← j + 1
return R

The finger never moves backward, so the intervals searched for successive targets are disjoint. Suppose their traversed lengths are $g_1,g_2,\ldots,g_m$. Galloping and closing a bracket of length $g_i$ takes $O(1+\log(g_i+1))$ comparisons. Because the finger crosses at most $n$ positions,

$$\sum_{i=1}^{m} g_i \le n.$$

The logarithm is concave. Jensen's inequality therefore gives

$$\sum_{i=1}^{m}\left(1+\log(g_i+1)\right) \le m + m\log\left(1+\frac{\sum_i g_i}{m}\right).$$

Because $\sum_i g_i\le n$, this is at most

$$m + m\log\left(1+\frac{n}{m}\right).$$

Thus the intersection costs

$$O\!\left(m\log\left(1+\frac{n}{m}\right)\right).$$

When $m\ll n$, this beats touching all $n$ entries and improves on $m$ unrelated $O(\log n)$ searches. When $m$ and $n$ are similar, the bound becomes $O(m)$, but the plain merge often wins in elapsed time: it has a predictable sequential access pattern and less branch machinery.

More than two terms

For a conjunctive query with postings $P_1,\ldots,P_q$, intersection is associative:

$$(P_1\cap P_2)\cap P_3 = P_1\cap(P_2\cap P_3).$$

The answer does not depend on parenthesization. The work does. A simple small-versus-small plan sorts the lists by increasing document frequency and repeatedly intersects the current result with the next list.

SVS-INTERSECT(L)
Input:  finite sequence L of sorted postings lists
Output: the intersection of every list in L

order L by nondecreasing length
R ← first list in L
for each remaining list P in L
    R ← GALLOP-INTERSECT(shorter of R and P, longer of R and P)
    if R is empty
        return R
return R

After any step, $|R\cap P|\le |R|$. Starting with the shortest list gives the smallest available upper bound on every later intermediate result. This does not prove that length order wins on every concrete set: contents, compression, cache residence, and correlations can reverse two plans. It proves the worst-case cardinality fact the planner is using.

The two main evaluation views now have names:

• term-at-a-time combines one whole term's evidence with an accumulator, then moves to the next term;
• document-at-a-time advances several postings cursors in document order and finishes one candidate document before the next.

Boolean pairwise intersection looks term-at-a-time because it materializes an intermediate set. The forward cursors inside it already foreshadow document-at-a-time ranked retrieval: later chapters will keep several cursors aligned and use score bounds to decide which document can be skipped.

A skip is a stored promise

Sequentially encoded postings may not support constant-time random access. A skip pointer stores a shortcut from one decoded position to a later one. It may be followed only when its destination is still below the opposing target; that comparison proves every posting under the jump cannot match.

How far apart should skips be? Let a list contain $n$ postings and place a skip every $s$ postings. A deliberately simple model charges about $n/s$ skip checks to cross the list and at most $s$ ordinary advances after the last useful jump:

$$T(s) \approx \frac{n}{s}+s.$$

By the arithmetic–geometric mean inequality,

$$\frac{n}{s}+s \ge 2\sqrt{n},$$

with equality at $s=\sqrt n$. This derives the familiar square-root spacing heuristic: about $\sqrt n$ skips, each spanning about $\sqrt n$ postings.

It is a model, not a universal optimum. It ignores the query distribution, compressed-block boundaries, cache lines, update costs, and the possibility that checking a skip costs more than advancing one decoded integer. The Stanford information-retrieval text presents square-root spacing as a practical heuristic and explicitly notes those limitations.

The input carries its own difficulty

Worst-case analysis asks for one bound covering every pair of lengths $m,n$. Adaptive analysis asks what this particular arrangement forced an algorithm to learn.

Suppose the two lists occupy distant, cleanly separated ranges. A few boundary comparisons can certify that their intersection is empty. Suppose instead that their values alternate and nearly coincide. Many local comparisons may be unavoidable. The lengths are identical in both cases; the proof burden is not.

In 2000, Erik Demaine, Alejandro López-Ortiz, and J. Ian Munro formalized this view for intersection, union, and difference of sorted sets. They characterized proofs of an answer and gave comparison algorithms within a constant factor of an instance-sensitive difficulty measure. The theorem is stronger than “it ran quickly on sparse lists”: it names the information any correct comparison algorithm must expose on that input.

The full instance-optimal result needs a careful certificate definition and comparison-model proof; it is cited here rather than disguised as the short galloping derivation above. Galloping is one concrete lesson from the same stance: retain what earlier comparisons proved, and let long gaps be cheap.

The machine underneath the notation

Asymptotics decide which growth curves are possible. Hardware decides which curve wins on a given machine.

J. Shane Culpepper and Alistair Moffat compared intersection methods for inverted indexes and separated two representation regimes: sorted arrays with constant-time indexed access, and sequential or compressed lists where reaching the $d$th integer has its own cost. That distinction changes which “skip” is physically available.

For flat resident arrays:

• merge streams contiguous memory and gives prefetchers an easy job;
• galloping performs fewer comparisons on imbalanced inputs but probes less predictably;
• branch mispredictions can cost more than several integer comparisons;
• vectorized block comparisons can move the crossover point.

For compressed postings:

• a logical jump may first require finding and decoding a block;
• auxiliary samples consume bytes but can bound the decode distance;
• the best skip spacing follows blocks and query frequencies, not merely $\sqrt n$;
• dynamic updates can invalidate a layout whose performance assumed a static list.

Measure at least comparisons, decoded integers, bytes touched, and elapsed time. Reporting only the last number hides why the winner changed. Reporting only comparisons pretends the memory hierarchy does not exist.

What not to do

Several plausible approaches fail for different reasons.

The honest production rule is a dispatch, not a champion: compare list lengths and representation capabilities, choose a sequential merge for balanced resident lists, choose finger or galloping search for strong imbalance, and measure the threshold on the actual encoding and machine. Preserve a simple merge as the differential oracle.

The unresolved match

Intersection has now proved that every returned document contains every query term. It has not proved what the reader probably meant.

A document containing “new evidence arrived yesterday” in its first paragraph and “York hosted the meeting” in its last contains both new and york. It survives the Boolean intersection for “New York.” The lists have met; the words have not.

To answer that question, a posting must remember where a term occurred. The next chapter turns a phrase into another intersection—this time shifted by an offset—and makes us pay explicitly for storing position.

Lessons

• A comparison between sorted cursors proves which smaller value cannot match later; this is why linear merge is correct.
• Linear merge costs $O(m+n)$ time and $O(1)$ working space beyond its output.
• A forward-only galloping intersection costs $O(m\log(1+n/m))$ for $m\le n$ because it pays logarithmically for disjoint gaps.
• Shortest-list-first minimizes a worst-case bound on intermediate cardinality; it does not know correlations or physical access costs.
• The square-root skip rule follows from the model $n/s+s$ and remains a heuristic, not a law of storage.
• A certificate measures the comparison evidence this instance needs, which worst-case length bounds deliberately erase.
• Fewer comparisons need not mean less time; layout, decoding, branches, and cache traffic choose the practical crossover.

Practice

1. Trace MERGE-INTERSECT on [3, 8, 14, 21, 34, 55] and [1, 8, 13, 21, 22, 34, 89]. Record every comparison and restate the invariant after each emitted match.
2. For $m=8$ and $n=1,048,576$, compare the upper bounds for merge, independent binary searches, and forward galloping. State what each bound omits about memory access.
3. Derive the minimizer of $n/s+cs$ for a skip check that costs $c$ ordinary advances. What happens to the spacing as skip checks become more expensive?
4. Construct two pairs of lists with the same lengths: one whose empty intersection has a short comparison certificate, and one whose answer requires comparisons throughout the range.
5. Design a dispatcher using a measured imbalance threshold. State the reference oracle and the observations a differential test must preserve.

References

1. Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro. “Adaptive Set Intersections, Unions, and Differences.” Proceedings of the Eleventh Annual ACM–SIAM Symposium on Discrete Algorithms, 2000.
2. J. Shane Culpepper and Alistair Moffat. “Efficient Set Intersection for Inverted Indexing.” ACM Transactions on Information Systems 29, no. 1, 2010.
3. F. K. Hwang and Shen Lin. “A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets.” SIAM Journal on Computing 1, no. 1, 1972.
4. Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze. “Faster Postings List Intersection via Skip Pointers.” In Introduction to Information Retrieval. Cambridge University Press, 2008.