AI Glossary / Retrieval and knowledge systems / Intermediate

Tiered indexes

Definition

Tiered indexes organize retrieval information into levels so a search can examine a promising subset first and fall back to broader levels when needed. In the classic information-retrieval example, tiers select postings using term-frequency thresholds. The aim is to reduce work while still returning enough useful candidates.

What it means

A full inverted index may contain very long postings lists. Many queries need only a small number of results. A tiered design tries the entries considered most promising before consulting less selective material.

The tiers can be defined by a chosen criterion, such as high term frequency or a document-level quality measure. Their exact membership and overlap depend on the design. One implementation may use cumulative thresholds, while another stores separate groups and combines them during fallback.

This term concerns retrieval organization. It should not be assumed to mean that one copy resides on fast storage and another on slow storage, although a system could combine retrieval tiers with a physical storage policy.

How it works

During index construction, the system determines which postings or documents belong to each tier. At query time, it applies the query-processing rule to the first tier and scores its candidates. If the candidate count is insufficient, it searches additional tiers.

Postings within a tier still need an appropriate order, such as document-identifier order, for efficient merging or intersection. Cumulative tiers require duplicate handling when the system expands its search. Disjoint tiers need a clear rule for combining previously examined and newly available information.

Having k candidates is not the same as proving they are the true top k under the full scoring model. A simple count-based stopping rule is generally a retrieval heuristic. Exact stopping requires additional conditions or bounds that show unseen candidates cannot improve the result.

Three practical examples

• A search prototype checks high-frequency term postings before falling back to lower-frequency postings.
• A curated collection searches a preferred candidate tier first, then broadens when it has too few eligible matches.
• A retrieval experiment compares the work saved by tiered processing with changes in the quality of returned rankings.

Think of it this way

Think of checking a small display of likely useful reference books before searching the rest of the library. If the display lacks enough candidates, you broaden the search.

Finding enough books on the display does not prove that the library contains no better ones. That is the important limit of the analogy: a convenient first tier is a selection heuristic, not an automatic optimality certificate.

Worked example

Enough candidates can still miss a better result

Use an invented two-term query, alpha AND beta. The four documents have term frequencies: D1 has (25, 2), D2 has (2, 25), D3 has (15, 15), and D4 has (12, 12). All four contain both terms. Define the full score, only for this example, as the sum of the two frequencies.

Tier one contains postings with frequency greater than 20. D1 appears for alpha and D2 for beta, so their intersection is empty. The search falls back to a cumulative tier two containing frequencies greater than 10. Now D3 and D4 appear in both lists.

A rule stopping after finding two candidates returns D3 and D4, with full scores 30 and 24. But D1 and D2 each score 27 in the complete index. Thus a true top-two set would contain D3 and one of D1 or D2, using a tie rule. The fallback produced enough matches but missed a higher-scoring candidate.

Illustrative case study

The fictional MapleSearch team uses tiers to reduce the amount of index data read for common queries. A count-based stopping rule usually fills the requested results page, but a comparison with exhaustive scoring reveals missed high-scoring documents.

The team labels the method as approximate and measures the trade-off on representative queries. For tasks requiring exact results under the scoring formula, it uses a method with justified stopping conditions instead. It also checks that cumulative fallback does not return the same document twice.

The case is fictional and reports no measured speedup. It illustrates why candidate sufficiency and ranking correctness need separate evaluation.

Common misconceptions and mistakes

• Once the first tier returns k documents, they must be the best k. That requires a guarantee the simple count rule does not provide.
• All tier designs are disjoint. Some use cumulative thresholds and need deduplication.
• Tiered indexing is necessarily a storage-hardware hierarchy. The retrieval sense describes selective levels of index information.

Business use

Tiered indexes can support efficient approximate retrieval when a small promising subset often provides satisfactory results. Their usefulness depends on the collection, query distribution, scoring model and quality requirements.

Document tier criteria, overlap and fallback rules. Compare against a full-index baseline and inspect queries with rare terms, uneven term evidence or restrictive filters. A tier with many raw matches may still have too few eligible results after access or metadata filtering. Measure both resource use and ranking quality, and make the approximation boundary explicit when the stopping rule can omit better candidates.

People also ask

Are tiered indexes related to champion lists?

Yes. They can be viewed as extending the idea of retaining promising per-term candidates into multiple levels.

Must term frequency define the tiers?

No. It is a classic example, while other selection criteria are possible.

Can later tiers change earlier rankings?

Yes. They can introduce stronger candidates or additional evidence, depending on how scoring and membership are organized.

Check your understanding

A first tier yields ten eligible documents for a request for ten results. Does that count alone prove exact top-ten retrieval?

Answer: No. Unexamined tiers may contain higher-scoring documents. Exactness needs further justification beyond the number found.

Related terms

• Inverted index
• Candidate generation
• Early stopping
• Static quality scores
• Champion list
• postings list
• inexact top-k retrieval
• index elimination
• static quality score

Learn next

Read champion lists and exact top-k retrieval. Trace both cumulative and disjoint tier designs on a small index, noting how fallback and duplicate handling differ.

More in Retrieval and knowledge systems

• Term discrimination
• Term partitioning - Term partitioning distributes an inverted index across machines by assigning different vocabulary terms to different partitions.
• Thesaurus (information retrieval) - A Thesaurus (information retrieval) is a structured vocabulary used to describe and retrieve information consistently.
• Topic-specific PageRank - Topic-specific PageRank is a PageRank distribution biased toward a chosen topic by changing where the modeled random surfer teleports.
• Tragedy of the commons - The tragedy of the commons is a collective-action problem in which individually attractive use of a shared, limited resource can produce excessive use and a...
• Two-Tower Embedding Model - A Two-Tower Embedding Model uses two encoders to map two kinds of input, such as queries and documents or users and items, into compatible vector...

Sources

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

The authors' threshold example and fallback rule were read. The four-document counterexample is original and uses explicitly defined cumulative tiers, conjunctive matching and additive frequencies. It demonstrates a limitation of count-based stopping rather than every possible tiered retrieval algorithm.

Previous: Tied covariance in Gaussian discriminant analysis Next: Tiling