Proximity Queries

A proximity query like PROX 3 quick fox matches documents where quick and fox appear within 3 token positions of each other (in either order).

Phrase queries are a special case: "quick fox" is essentially PROX 1 with order enforced. Proximity loosens the constraint to "anywhere nearby."

Why it matters

• "United States" (phrase) is strict, but "States United Nations of America" should also match a query about the United States.
• Proximity is the bridge between strict phrase and bag-of-words: rewards co-occurrence locally.
• Used in Google's older ranking signals, in scholarly search (Lexis-Nexis), and in any "near" operator.

Data

You need a positional index: term -> {doc_id: [positions]}. Same structure as for phrase queries — proximity is one more query type that piggybacks on the same index.

Algorithm

Given termA, termB, and gap k:

1. docs = postings(A) ∩ postings(B)
2. For each common doc, you have two sorted position lists pA and pB.
3. Two-pointer walk: at each step compare pA[i] vs pB[j]. If |pA[i] - pB[j]| <= k, hit. Otherwise advance the smaller pointer.

Two-pointer is O(|pA| + |pB|) — same as boolean intersection.