Synonym handling in Elasticsearch - Time & Space Complexity

Time Complexity: Synonym handling

O(n)

Understanding Time Complexity

When Elasticsearch processes synonyms, it changes how many words it looks at during a search.

We want to know how adding synonyms affects the work Elasticsearch does as the input grows.

Scenario Under Consideration

Analyze the time complexity of the following synonym filter in Elasticsearch.

{
  "settings": {
    "analysis": {
      "filter": {
        "synonym_filter": {
          "type": "synonym",
          "synonyms": ["quick,fast", "jumps,leaps"]
        }
      },
      "analyzer": {
        "synonym_analyzer": {
          "tokenizer": "standard",
          "filter": ["lowercase", "synonym_filter"]
        }
      }
    }
  }
}
    

This code defines a synonym filter that replaces words with their synonyms during analysis.

Identify Repeating Operations

Look at what repeats when analyzing text with synonyms.

• Primary operation: For each token (word), check if it matches any synonym group.
• How many times: Once per token in the input text.

How Execution Grows With Input

As the number of words (tokens) grows, the synonym filter checks each one against the synonym list.

Input Size (n tokens)	Approx. Operations
10	10 synonym checks
100	100 synonym checks
1000	1000 synonym checks

Pattern observation: The work grows directly with the number of tokens; more words mean more checks.

Final Time Complexity

Time Complexity: O(n)

This means the time to process synonyms grows in a straight line with the number of words analyzed.

Common Mistake

[X] Wrong: "Adding synonyms makes the search time explode exponentially."

[OK] Correct: Actually, each word is checked once against the synonym list, so time grows linearly, not exponentially.

Interview Connect

Understanding how synonym handling scales helps you explain search performance clearly and confidently.

Self-Check

What if the synonym list grew from 10 to 10,000 entries? How would that affect the time complexity?

Practice

1. What is the main purpose of synonym handling in Elasticsearch?

easy

A. To find search results that include different words with the same meaning

B. To speed up the indexing process

C. To store data in multiple languages automatically

D. To encrypt search queries for security

Solution

1. Step 1: Understand synonym handling concept

   Synonym handling allows Elasticsearch to match words that mean the same, improving search results.

2. Step 2: Identify the main goal

   The goal is to find results with different words but same meaning, not speed or encryption.

3. Final Answer:

   To find search results that include different words with the same meaning -> Option A

4. Quick Check:

   Synonym handling = find similar meaning words [OK]

Hint: Synonyms help find words with same meaning [OK]

Common Mistakes:

• Thinking synonyms speed up indexing
• Confusing synonyms with encryption
• Assuming synonyms translate languages automatically

2. Which of the following is the correct way to define a synonym filter in Elasticsearch settings?

easy

A. "filter": { "synonym_filter": { "type": "keyword", "synonyms": ["quick,fast"] } }

B. "filter": { "synonym_filter": { "type": "stop", "synonyms": ["quick,fast"] } }

C. "filter": { "synonym_filter": { "type": "synonym", "synonyms": ["quick,fast"] } }

D. "filter": { "synonym_filter": { "type": "stemmer", "synonyms": ["quick,fast"] } }

Solution

1. Step 1: Identify correct filter type for synonyms

   The filter type for synonyms must be "synonym" to handle synonym lists.

2. Step 2: Check the filter definition syntax

   "filter": { "synonym_filter": { "type": "synonym", "synonyms": ["quick,fast"] } } correctly uses "type": "synonym" and defines synonyms as a list.

3. Final Answer:

   "filter": { "synonym_filter": { "type": "synonym", "synonyms": ["quick,fast"] } } -> Option C

4. Quick Check:

   Synonym filter type = "synonym" [OK]

Hint: Synonym filters use type "synonym" [OK]

Common Mistakes:

• Using wrong filter types like stop or stemmer
• Not defining synonyms as a list
• Misspelling "synonym" type

3. Given this analyzer configuration, what will be the tokens produced for the text "fast car"?

{
  "analysis": {
    "filter": {
      "synonym_filter": {
        "type": "synonym",
        "synonyms": ["fast,quick"]
      }
    },
    "analyzer": {
      "synonym_analyzer": {
        "tokenizer": "standard",
        "filter": ["lowercase", "synonym_filter"]
      }
    }
  }
}

medium

A. ["fast", "quick", "car", "car"]

B. ["fast", "quick", "car"]

C. ["quick", "car"]

D. ["fast", "car"]

Solution

1. Step 1: Analyze the text with the synonym filter

   The synonym filter maps "fast" to "quick", so both tokens appear for "fast".

2. Step 2: List all tokens after analysis

   Tokens are "fast", "quick" (synonym), and "car" (unchanged).

3. Final Answer:

   ["fast", "quick", "car"] -> Option B

4. Quick Check:

   Synonym adds "quick" token for "fast" [OK]

Hint: Synonym filter adds synonyms as extra tokens [OK]

Common Mistakes:

• Ignoring synonym addition and listing only original tokens
• Replacing original token instead of adding synonym
• Duplicating tokens unnecessarily

4. You defined a synonym filter but your search results do not include synonyms. What is the most likely mistake?

medium

A. You used the synonym filter in the index but not in the search analyzer

B. You forgot to add the synonym filter to the analyzer's filter list

C. You defined synonyms as a string instead of a list

D. You used the synonym filter with the wrong tokenizer

Solution

1. Step 1: Understand how synonym filters affect search

   Synonyms must be applied in the analyzer used during search to affect results.

2. Step 2: Identify common setup mistake

   Often synonyms are applied only at index time, missing search analyzer usage.

3. Final Answer:

   You used the synonym filter in the index but not in the search analyzer -> Option A

4. Quick Check:

   Synonyms must be in search analyzer too [OK]

Hint: Apply synonym filter in both index and search analyzers [OK]

Common Mistakes:

• Adding synonym filter only at index time
• Not including synonym filter in search analyzer
• Misconfiguring synonyms as string instead of list

5. You want to improve search for a product catalog where users may search for "tv", "television", or "smart tv". How should you configure synonyms to handle these terms effectively?

hard

A. Apply synonyms only at search time to avoid changing indexed data

B. Define synonyms only for "tv" and "television" but exclude "smart tv" because it has two words

C. Use a stop filter to remove "smart" and then define synonyms for "tv" and "television"

D. Define synonyms as: "tv, television, smart tv" in a synonym filter and apply it in both index and search analyzers

Solution

1. Step 1: Define all related terms as synonyms

   Include "tv", "television", and "smart tv" together to cover all user queries.

2. Step 2: Apply synonym filter in both index and search analyzers

   This ensures synonyms work during indexing and searching for best results.

3. Final Answer:

   Define synonyms as: "tv, television, smart tv" in a synonym filter and apply it in both index and search analyzers -> Option D

4. Quick Check:

   Synonyms cover all terms and apply at both stages [OK]

Hint: Include all terms and apply synonyms at index and search [OK]

Common Mistakes:

• Ignoring multi-word synonyms like "smart tv"
• Applying synonyms only at search time
• Using stop filter incorrectly to remove words