List Intersection

Formula#

Properties#

1.Zipper (Linear Merge Intersection)#

Walk through both sorted lists simultaneously with two pointers. Advance the pointer pointing to the smaller element; when both point to equal elements, emit that element to the result (Slides 01, p. 18).

def intersect(list1, list2):
    result = []
    i, j = 0, 0
    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            i += 1
        elif list1[i] > list2[j]:
            j += 1
        else:
            result.append(list1[i])
            i += 1
            j += 1
    return result

Runtime: $O(k + n)$: every step advances at least one pointer.

2.Binary Search Intersection#

For each element of the shorter list, perform a binary search in the longer list.

def intersect_binary(list1, list2):
    if len(list1) > len(list2):
        list1, list2 = list2, list1
    result = []
    for x in list1:
        lo, hi = 0, len(list2)
        while lo < hi:
            mid = (lo + hi) // 2
            if list2[mid] < x:
                lo = mid + 1
            elif list2[mid] > x:
                hi = mid
            else:
                result.append(x)
                break
    return result

Runtime: $O(k \cdot \log n)$: $k$ binary searches of $O(\log n)$ each.

3.Galloping (Exponential) Search Intersection#

A refinement of binary search: for each element $x$ of the shorter list, run an exponential (galloping) search in the longer list: find a range $[2^{j-1}, 2^j]$ in which $x$ could lie by doubling the index, then binary search within that range.

Runtime: $O\!\left(k \cdot \log\!\left(1 + \frac{n}{k}\right)\right)$

Galloping is never worse than the zipper#

Using $e^x \geq 1 + x$, i.e. $\ln(1 + x) \leq x$, with $x = n/k$:

$\log$ and $\ln$ differ only by a constant factor, hence $O(k \cdot \log(1 + n/k)) \subseteq O(k + n)$ (DBIS Exam WS1819 (not published), Task 1.2).

Practical choice#

Galloping search has a larger constant factor due to its more complex algorithm. When $k/n$ is close to 1, the zipper’s simplicity wins in practice. A common heuristic: use galloping when $n/k > 10$, otherwise use the zipper (DBIS Exam WS1819 (not published), Task 1.3).

Multi-List Intersection ($m > 2$ lists)#

Given inverted lists $L_1, L_2, \ldots, L_m$ for $m$ query terms (Slides 01, p. 19):

1. Sequential pairwise: Intersect $L_1 \cap L_2 \to L_{12}$, then $L_{12} \cap L_3 \to L_{123}$, etc.
2. Optimization: Sort lists by length ($|L_1| \leq |L_2| \leq \cdots \leq |L_m|$) to minimize intermediate result sizes.
3. $m$-way intersection using a priority queue: $O(\log m \cdot \sum_i |L_i|)$.

Example#

Lists for query “spielberg dinosaurs” (Slides 01, p. 18):

The zipper walks both lists left to right: $L_1$’s pointer advances over $6, 22, 24, 53$ (all $< 62$), both pointers meet at $62$ (emit), $L_1$ advances over $102, 148$ (all $< 194$), both meet at $194$ (emit), and so on.

Sources#

• Slides 01, p. 18 (two keywords, zipper), Slides 01, p. 19 ($k > 2$ keywords)
• DBIS_VL01 > Query Processing
• Slides 02, p. 8, DBIS_VL02 > Ranking: Basic Idea (merging scored lists)
• Slides 05, p. 13, DBIS_VL05 > Merge join (merge join = zipper)
• Past exams: DBIS Exam WS1819 (not published) Task 1 (binary search intersection, galloping vs. zipper), DBIS Exam WS2324 (not published) Task 1.2 (merge)