Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Inverted indexes: intersect sorted incident postings

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A document-level inverted index maps a term to the sorted IDs of documents containing that term. It stores each document ID only once per term, even if the term repeats inside the document. For an all-term query, sorted postings can be intersected with two advancing cursors; neither cursor needs to retreat. This implementation processes the shortest list first, retains the caller's exact pre-tokenized terms, and returns IDs in ascending order. A missing term makes the intersection empty. An empty query also returns an empty list by this API's choice, rather than matching every document. It builds one immutable snapshot and does not silently update the index when the source document collection changes.

Operational case

Four incident records use IDs 103, 218, 347, and 492. Record 103 says valve, pressure, pressure; record 218 says pump, pressure; record 347 says valve, pressure, pump; record 492 says valve, sensor. The query valve AND pressure returns IDs 103 and 347. Valve AND sensor returns 492, and valve AND offline returns none. Pressure appears twice in record 103, yet that document ID appears once in its posting list. A Boolean query tests document membership, not how often a word occurs. Tokenization and case normalization must be agreed with upstream producers; this example deliberately accepts exact tokens as supplied.

Working Python program

python
from collections import defaultdict


class IncidentPostings:
    def __init__(self, documents):
        self.postings = defaultdict(list)
        for document_id in sorted(documents):
            for term in set(documents[document_id]):
                self.postings[term].append(document_id)

    @staticmethod
    def _intersect(left, right):
        matched = []
        left_at = right_at = 0
        while left_at < len(left) and right_at < len(right):
            if left[left_at] == right[right_at]:
                matched.append(left[left_at])
                left_at += 1
                right_at += 1
            elif left[left_at] < right[right_at]:
                left_at += 1
            else:
                right_at += 1
        return matched

    def containing_all(self, terms):
        unique_terms = list(dict.fromkeys(terms))
        if not unique_terms:
            return []
        lists = [self.postings.get(term, []) for term in unique_terms]
        lists.sort(key=len)
        matched = lists[0][:]
        for posting_list in lists[1:]:
            matched = self._intersect(matched, posting_list)
            if not matched:
                break
        return matched


if __name__ == "__main__":
    incidents = IncidentPostings({
        103: ["valve", "pressure", "pressure"],
        218: ["pump", "pressure"],
        347: ["valve", "pressure", "pump"],
        492: ["valve", "sensor"],
    })
    print("valve-and-pressure=", incidents.containing_all(["valve", "pressure"]), sep="")
    print("valve-and-sensor=", incidents.containing_all(["valve", "sensor"]), sep="")
    print("missing=", incidents.containing_all(["valve", "offline"]), sep="")

Output

Output
valve-and-pressure=[103, 347]
valve-and-sensor=[492]
missing=[]

Time, space, and tradeoff

Let D be the number of documents, T the total supplied tokens, and P the total unique document-term pairs. Sorting document IDs costs O(D log D), and building postings requires O(T) expected set and hash work plus O(P) storage. A two-list intersection of lengths A and B takes O(A + B) time and O(min(A, B)) result space; several intersections take time proportional to the lists examined and intermediate results. A full document scan would revisit every record per query. A dictionary of unsorted ID sets may be simpler for small corpora, but sorted lists make merge behavior explicit and support compact ordered storage. This version has no deletion, ranking, or phrase semantics.

Common Mistakes

  • Do not add the same document ID twice for a repeated term.
  • Do not assume document-level membership proves adjacent word order.
  • Do not return the shortest posting list without intersecting the rest.
  • Do not change source documents without rebuilding this immutable snapshot.

Connected lessons

Compare its query with Positional postings: find exact token phrases, Trigram indexes: filter and verify substring candidates, Front-coded lexicons: store shared prefixes within sorted term blocks, then run the incident text index audit and index contract quiz.

Chunked integer sets: switch sparse arrays to dense bitmaps adds a compact lookup contract.

Gap-encoded postings: add checkpoints to bytewise seeks adds a compact lookup contract.

Block-max postings: skip safe document-score regions adds a distinct structure contract to compare.

data structures
hash-tables
Storage details