AI Glossary / Retrieval and knowledge systems / Intermediate

Term partitioning

Definition

Term partitioning distributes an inverted index across machines by assigning different vocabulary terms to different partitions. A partition stores its assigned terms and their postings across the indexed collection. It is also called global index organization in the information-retrieval literature.

What it means

An inverted index answers which documents contain each term. With term partitioning, the machine responsible for battery stores the battery postings, while another machine may hold the recycling postings. A query is routed to the partitions that own its terms.

This differs from document partitioning, where each machine indexes a subset of documents and usually contains many of the same vocabulary terms as other machines. The distinction concerns how the index is divided, not how words are tokenized.

Term partitioning can allow unrelated queries to use different machines. However, a query involving terms on several partitions requires coordination to combine their evidence. Avoiding a broadcast to every machine does not automatically make the complete query cheaper.

How it works

A partitioning rule maps each term to an owner. The owner keeps the corresponding postings, including whatever document identifiers, frequencies or positions the retrieval design requires. A query processor identifies the relevant owners and obtains or combines their contributions.

For a Boolean conjunction, the system must find document identifiers shared by the terms. For ranked retrieval, it must combine term contributions under a consistent scoring model. The exact communication pattern depends on the implementation: lists, candidates, partial scores or intermediate results can move between machines.

Balanced vocabulary counts do not guarantee balanced load. Common query terms, long postings and bursts of related searches can concentrate work. Co-locating frequently queried term combinations may reduce communication, while also creating other imbalances. Updates and failures need a design that preserves a consistent view of the distributed index.

Three practical examples

• A research search engine assigns term postings to several servers and routes each query to the relevant owners.
• An indexing experiment groups terms that frequently appear together in queries to examine the communication trade-off.
• A distributed retrieval team compares vocabulary-based partitioning with document-based partitioning under its actual query workload.

Think of it this way

Think of a reference service where one desk handles words beginning with A through M and another handles N through Z. A single-word request visits one desk, while a request combining words may require the desks to coordinate.

The analogy does not guarantee equal queues. A few popular words can keep one desk busy even when the alphabet has been divided evenly.

Worked example

Combining postings from two owners

In an invented six-document collection, server P owns battery and stores postings [D1, D3, D5]. Server Q owns recycling and stores [D2, D3, D5, D6]. A conjunctive query for battery AND recycling needs the intersection, [D3, D5].

Suppose this simple implementation sends both complete lists to a coordinator. It transfers seven document identifiers to obtain two matching identifiers. If each identifier occupies four uncompressed bytes, the list payload is 7 × 4 = 28 bytes, excluding all headers and other metadata.

That small count illustrates where communication occurs; it is not a realistic network-performance estimate. A different protocol could send one list to the other owner or use more selective intermediate information. With long frequent-term lists, the choice can matter much more than it does in this toy example.

Illustrative case study

The fictional AlderSearch team divides its vocabulary into equally sized partitions. Initial storage sizes look reasonable, but a burst of queries about one product repeatedly contacts the same two owners. Their response times dominate the service.

The team studies query frequency and term co-occurrence rather than assuming that equal numbers of dictionary entries imply equal work. It compares alternative placements and considers replication or a different partitioning design, with consistent update handling.

The case illustrates workload-sensitive design. It reports no actual latency gain and does not claim that term partitioning is always preferable to document partitioning.

Common misconceptions and mistakes

• Term partitioning splits each document's text into separate files. It divides index ownership by vocabulary term.
• Equal-sized term sets create equal server loads. Posting lengths and query patterns can vary dramatically.
• Each query is answered entirely by one server. Multi-term queries can require several term owners and a combination step.

Business use

Term partitioning is an architectural choice for distributed search, useful to understand when evaluating index placement, query routing and communication costs. Its strengths depend on how terms and queries are distributed.

Measure posting sizes, query frequencies, co-occurring terms and workload changes. Include the cost of merging evidence, not only local lookup time. Define how document updates reach every relevant term owner and how partial failures affect returned results. Compare alternatives using the same scoring semantics and freshness requirements. A low number of contacted servers is not sufficient evidence of good end-to-end performance.

People also ask

Is a hash-based term assignment possible?

Yes. It can spread term ownership, but popular terms can still produce uneven query load.

Does term partitioning require lexical ranges?

No. The mapping can use hashing, explicit assignments or other placement strategies.

Does it remove the need for document identifiers?

No. Postings still need to identify documents so evidence from different terms can be combined.

Check your understanding

Server A stores all postings for some terms across the collection. Server B stores all postings for other terms. Is this term or document partitioning?

Answer: Term partitioning. Ownership follows vocabulary terms rather than subsets of documents.

Related terms

• Inverted index
• Document partitioning
• postings list
• distributed retrieval
• query routing
• load balancing
• index sharding
• query co-occurrence

Learn next

Read document partitioning and distributed retrieval. Trace the same two-term query under both layouts, listing what each machine stores and what information must be combined.

• Document partitioning

More in Retrieval and knowledge systems

• Subject indexing - Subject indexing is the process of describing what an information resource is about through assigned terms, headings, codes, or other subject indicators.
• Subsetting - Subsetting is selecting and retrieving a specified portion of a larger dataset or data object.
• Tag (metadata) - A Tag (metadata) is a descriptive label or attribute associated with a resource to help identify, organize, filter, or manage it.
• Term-at-a-time - Term-at-a-time is a query-scoring strategy that processes one query term's postings before moving to another query term.
• Term discrimination
• Thesaurus (information retrieval) - A Thesaurus (information retrieval) is a structured vocabulary used to describe and retrieve information consistently.

Sources

Christopher Manning, Prabhakar Raghavan and Hinrich Schutze, Introduction to Information Retrieval, Distributing indexes: https://nlp.stanford.edu/IR-book/html/htmledition/distributing-indexes-1.html

The authors' term-partitioned organisation, communication and load-balancing discussion was read. The two-server postings and payload calculation are original. The historical source's architecture discussion is not presented as a current survey of all commercial search systems.

Previous: Term-document matrix Next: Term weight