Read

Proximity Queries

A plain Boolean AND query for quick AND fox tells you both terms appear somewhere in a document — but says nothing about whether they're related. In "the quick brown fox jumps," quick and fox are two words apart and clearly describing the same idea; in a document where quick appears in paragraph one and fox in paragraph twelve, the AND match is far less meaningful. Proximity search — "these terms within k positions of each other" — is a standard way to make phrase-like and near-phrase queries possible without requiring an exact contiguous match.

The data structure: a positional index

A plain inverted index maps term -> set of doc_ids. That's enough for Boolean AND/OR, but it throws away where in the document each term occurred — which is exactly the information proximity needs. A positional index keeps that: term -> {doc_id -> [positions]}, where positions are the term's 0-based token offsets within that document.

Note this exercise deliberately keeps stopwords (unlike a typical relevance-ranking index, which often drops them) — proximity is a positional/structural notion, and dropping "the" or "is" would shift every later token's position, silently breaking distance calculations. Position lists must reflect the actual token stream.

Answering a proximity query

Given two terms and a window k, a document qualifies if some occurrence of term A and some occurrence of term B in that document are within k positions of each other — in either direction (A before B, or B before A both count).

The naive approach — compare every position of A against every position of B — is O(|posA| * |posB|) per document. Since both position lists are already sorted ascending (positions were appended in token order), a two-pointer sweep finds a qualifying pair (or proves none exists) in O(|posA| + |posB|):

The intuition: at each step, look at the current smaller position and try to catch up to the other list. If the current pair is already within k, you're done. If not, whichever pointer is "behind" needs to advance — the one with the smaller position can never get closer to a later position in the other list by staying still, so advancing it is always safe and never causes you to miss a valid pair.

Putting it together

1. Find the set of documents where both terms appear at all (a set intersection over the two terms' doc-id keys) — no point running the pointer sweep on documents missing one of the terms entirely.
2. For each such document, run the two-pointer sweep over that document's two position lists.
3. Collect and sort the doc ids where the sweep found a qualifying pair.

Edge cases

• A term that never appears in the corpus at all should short-circuit to "no results" immediately.
• k = 0 means the terms must occupy the exact same position — impossible for two distinct tokens, so it always yields no matches (unless your tokenizer could ever place two terms at one position, which it shouldn't).
• Larger k values are strictly more permissive — every document that matches at k also matches at any k' > k — which is a good sanity check to test your implementation against.

This positional index is also the foundation for exact phrase queries ("quick fox" verbatim) — that's just proximity with k = 1 and a constraint that A's position is exactly one less than B's, rather than either order being acceptable.