TF-IDF and BM25 scoring in Elasticsearch - Time & Space Complexity

Time Complexity: TF-IDF and BM25 scoring

O(n * m)

Understanding Time Complexity

When searching documents, Elasticsearch uses scoring methods like TF-IDF and BM25 to rank results.

We want to understand how the time to calculate these scores grows as the number of documents or terms increases.

Scenario Under Consideration

Analyze the time complexity of this Elasticsearch query using BM25 scoring.

GET /my_index/_search
{
  "query": {
    "match": {
      "content": "search terms here"
    }
  }
}
    

This query searches documents matching the given terms and scores them using BM25 by default.

Identify Repeating Operations

Look at what repeats during scoring:

• Primary operation: Calculating term frequency and inverse document frequency for each term in each document.
• How many times: For each query term, Elasticsearch checks every document containing that term.

How Execution Grows With Input

As the number of documents and query terms grow, the scoring work increases.

Input Size (n)	Approx. Operations
10 documents, 2 terms	About 20 checks (2 terms x 10 docs)
100 documents, 2 terms	About 200 checks
1000 documents, 5 terms	About 5000 checks

Pattern observation: The work grows roughly with the number of documents times the number of query terms.

Final Time Complexity

Time Complexity: O(n * m)

This means the scoring time grows proportionally with the number of documents n and the number of query terms m.

Common Mistake

[X] Wrong: "Scoring time depends only on the number of query terms, not on documents."

[OK] Correct: Each term must be checked in every document that contains it, so more documents mean more scoring work.

Interview Connect

Understanding how scoring scales helps you explain search performance and design efficient queries in real projects.

Self-Check

What if we changed the scoring method from BM25 to a simpler constant score? How would the time complexity change?

Practice

1. What is the main difference between TF-IDF and BM25 scoring in Elasticsearch?

easy

A. BM25 ignores inverse document frequency, TF-IDF uses it heavily.

B. TF-IDF is the default scoring algorithm in Elasticsearch, BM25 is optional.

C. BM25 considers term frequency saturation and document length normalization, TF-IDF does not.

D. TF-IDF scores are always higher than BM25 scores for the same query.

Solution

1. Step 1: Understand TF-IDF basics

   TF-IDF scores words by multiplying term frequency (TF) with inverse document frequency (IDF), but it does not adjust for document length or term frequency saturation.

2. Step 2: Understand BM25 improvements

   BM25 improves TF-IDF by adding term frequency saturation (diminishing returns for repeated terms) and normalizing by document length, making scores more balanced.

3. Final Answer:

   BM25 considers term frequency saturation and document length normalization, TF-IDF does not. -> Option C

4. Quick Check:

   BM25 adds saturation and length normalization [OK]

Hint: BM25 adjusts TF-IDF with saturation and length normalization [OK]

Common Mistakes:

• Thinking TF-IDF is default in Elasticsearch
• Believing BM25 ignores IDF
• Assuming TF-IDF always scores higher

2. Which Elasticsearch query parameter correctly switches the similarity scoring to TF-IDF instead of BM25?

easy

A. ""{
"similarity": "classic"
}"""

B. ""{
"similarity": "bm25"
}"""

C. ""{
"similarity": "tfidf"
}"""

D. ""{
"similarity": "default"
}"""

Solution

1. Step 1: Recall Elasticsearch similarity options

   Elasticsearch uses "bm25" by default. To switch to TF-IDF, you use the "classic" similarity setting.

2. Step 2: Match parameter to TF-IDF

   The "classic" similarity corresponds to TF-IDF scoring, so setting "similarity": "classic" enables TF-IDF.

3. Final Answer:

   { "similarity": "classic" } -> Option A

4. Quick Check:

   TF-IDF similarity is "classic" [OK]

Hint: Use similarity: classic to enable TF-IDF scoring [OK]

Common Mistakes:

• Using "tfidf" as similarity name (not valid)
• Assuming "default" switches to TF-IDF
• Confusing bm25 with TF-IDF

3. Given the following Elasticsearch query using BM25, what will happen to the score if a term appears multiple times in a document?

medium

A. The score increases but with diminishing returns due to term frequency saturation.

B. The score increases linearly with each additional term occurrence.

C. The score stays the same regardless of term frequency.

D. The score decreases as term frequency increases.

Solution

1. Step 1: Understand BM25 term frequency effect

   BM25 applies a saturation function to term frequency, so each additional occurrence adds less to the score than the previous one.

2. Step 2: Compare to linear increase

   Unlike TF-IDF which can increase linearly, BM25 limits the impact of repeated terms to avoid overvaluing them.

3. Final Answer:

   The score increases but with diminishing returns due to term frequency saturation. -> Option A

4. Quick Check:

   BM25 uses saturation, not linear increase [OK]

Hint: BM25 scores repeated terms with diminishing returns [OK]

Common Mistakes:

• Assuming linear score increase with term frequency
• Thinking score stays constant with repeats
• Believing score decreases with more terms

4. You configured Elasticsearch to use TF-IDF similarity but notice search results are not ranking as expected. Which of the following is a likely cause?

medium

A. TF-IDF requires a special query syntax different from standard queries.

B. TF-IDF does not use inverse document frequency, so scores are random.

C. BM25 must be disabled in the cluster settings to use TF-IDF.

D. You forgot to reindex the data after changing similarity settings.

Solution

1. Step 1: Understand similarity changes require reindexing

   Changing similarity settings affects how documents are scored, but Elasticsearch applies these only after reindexing the data.

2. Step 2: Identify common mistake

   If you don't reindex, old scores remain, so results won't reflect the new TF-IDF similarity.

3. Final Answer:

   You forgot to reindex the data after changing similarity settings. -> Option D

4. Quick Check:

   Reindexing needed after similarity change [OK]

Hint: Always reindex after changing similarity settings [OK]

Common Mistakes:

• Believing TF-IDF ignores IDF
• Thinking BM25 must be disabled cluster-wide
• Assuming query syntax changes for TF-IDF

5. You want to improve search relevance for a collection of very short documents using Elasticsearch. Which scoring approach and adjustment is best to handle short documents effectively?

hard

A. Use BM25 with a higher k1 parameter to ignore term frequency saturation.

B. Use BM25 with a lower b parameter to reduce length normalization effect.

C. Use TF-IDF similarity because it handles short documents better by default.

D. Use TF-IDF and disable inverse document frequency to boost short docs.

Solution

1. Step 1: Understand BM25 parameters for short docs

   BM25's b parameter controls length normalization. Lowering b reduces penalty on short documents, improving their scores.

2. Step 2: Compare to TF-IDF and other options

   TF-IDF lacks length normalization control. Increasing k1 ignores saturation, which can hurt relevance. Disabling IDF is incorrect.

3. Final Answer:

   Use BM25 with a lower b parameter to reduce length normalization effect. -> Option B

4. Quick Check:

   Lower b helps short docs in BM25 [OK]

Hint: Lower BM25 b parameter to favor short documents [OK]

Common Mistakes:

• Assuming TF-IDF is better for short docs by default
• Increasing k1 to ignore saturation hurts relevance
• Disabling IDF reduces search quality