Postingslister

Postingslister, in information retrieval and computer science, are the data structures that store, for each term, the list of documents in which the term occurs. In many systems, a postingslister is part of an inverted index, which maps terms to their postings lists. A postingslister typically records, alongside a document identifier, metadata such as term frequency and the positions where the term appears within the document. The positions enable supporting advanced queries such as phrase searches and proximity queries, where the relative locations of terms matter.

The data in postingslister can be compressed to save space, using techniques such as delta encoding of document IDs, gap encoding, and variable-length coding or bit packing. Skip pointers or hierarchical structures may be added to speed intersections when processing multi-term queries. Different implementations may store only document IDs, or also include term frequency, positions, and other payloads.

During query processing, the search system retrieves the postings lists for the query terms and computes unions or intersections to identify candidate documents. The inclusion of term positions allows efficient phrase matching and can influence ranking by signals such as term frequency and document frequency. In practice, postingslister implementations vary; some store compact doc IDs, others store frequencies and positions, and they may be organized as contiguous arrays or as linked structures, depending on indexing and compression goals.

In common usage, postingslister corresponds to the English term “postings list” or “positional index.” It is a core component of most modern search engines and information retrieval systems, underpinning tasks from basic keyword search to complex analytics over large text collections.