Source-linked AI summary
Query expansion techniques for information retrieval: A survey
Hiteshwar Kumar Azad, Akshay Deepak
TL;DR
Web search must handle exponentially growing information while users continue submitting short or ambiguous queries, causing vocabulary mismatch and reduced retrieval quality. This survey reviews QE research from 1960 to 2017 across techniques, data sources, methodologies, user participation, and applications, finding reported improvements in both precision and recall. It also highlights personalized QE as an important future direction.
Problem
Exponential information growth, short queries, ambiguity, and vocabulary mismatch make retrieving relevant web information difficult and can reduce precision and recall.
Method
The paper surveys QE research from 1960 to 2017 and classifies approaches by data sources, working methodology, applications, and core approaches, including manual, automatic, and interactive methods.
Results
Experimental studies report improved retrieval effectiveness in both precision and recall, while adding expansion terms has been reported to improve effectiveness by 7% to 25%.
Takeaways & Limitations
Personalized QE based on user preferences and profiles is identified as an important future direction for reflecting users’ interests and intent.
Takeaways & Limitations
Synonym replacement can change the meaning of idiomatic phrases because their meanings are non-compositional.
Abstract
from arXiv · showhide
With the ever increasing size of the web, relevant information extraction on the Internet with a query formed by a few keywords has become a big challenge. Query Expansion (QE) plays a crucial role in improving searches on the Internet. Here, the user's initial query is reformulated by adding additional meaningful terms with similar significance. QE -- as part of information retrieval (IR) -- has long attracted researchers' attention. It has become very influential in the field of personalized social document, question answering, cross-language IR, information filtering and multimedia IR. Research in QE has gained further prominence because of IR dedicated conferences such as TREC (Text Information Retrieval Conference) and CLEF (Conference and Labs of the Evaluation Forum). This paper surveys QE techniques in IR from 1960 to 2017 with respect to core techniques, data sources used, weighting and ranking methodologies, user participation and applications -- bringing out similarities and differences.
1 Introduction
Web search faces a growing vocabulary and precision problem because users submit short, ambiguous queries against exponentially expanding collections. The survey motivates query expansion as a response and positions its broader review of QE research.
- Exponential web growth increased the gap between available information and technologies for extracting relevant results.
- Synonymy and polysemy create term mismatch between user queries and indexes, reducing both recall and precision.
- QE addresses the vocabulary problem by adding related terms, selectively retaining original terms, and reformulating queries for retrieval.
- Search engines increased recall but reduced precision as web data expanded while users continued submitting short queries.
- Most queries contain one to three words, increasing ambiguity and vocabulary mismatch as web pages multiply.
- This survey extends earlier reviews by covering automatic, manual, and interactive QE across data sources, applications, methodology, and core approaches.
2 Query Expansion
Query expansion reformulates an initial query by adding meaningful terms from selected data sources and possibly removing terms. Its workflow combines term extraction, weighting and ranking, selection, and reformulation, with user involvement ranging from none to collaborative interaction.
- QE adds meaningful terms from data sources to the original query while optionally removing terms such as stop words.
- The key QE research choices are how to compute expansion terms and which data sources to use.
- Manual, automatic, and interactive QE differ in how users and systems jointly determine query reformulation.
- The QE workflow comprises preprocessing and term extraction, weighting and ranking, term selection, and query reformulation.
2.1 Preprocessing of Data Sources and Term Extraction
QE preprocessing extracts candidate terms from diverse data sources before weighting and selecting expansions. The survey compares retrieval documents, hand-built resources, external collections, and hybrid sources, including their reported strengths and limitations.
- Preprocessing: Preprocessing extracts terms through text extraction, tokenization, stop-word removal, and stemming before combining processed sources with the user query.
- Data sources: QE data sources fall into retrieval documents, hand-built knowledge resources, external text collections, and hybrid sources.
- Documents Used in Retrieval Process: Corpus-based approaches use term or document clustering and co-occurrence to identify similar terms for query expansion.
- Hand-built Knowledge Resources: Hand-built resources include dictionaries, thesauri, ontologies, Wikipedia, and linked-data resources for extracting semantic relations.
- Hand-built Knowledge Resources: Hand-built resources are often domain specific, omit proper nouns, require updating, and may help poorly constructed queries more than well-formulated ones.
- External Text Collections and Resources: External collections include the web, anchor text, query logs, and corpora, with query-log expansion based on correlations between query and document terms.
- External Text Collections and Resources: Query logs are widely used, but may be unavailable or insufficient for customized, personalized, enterprise, or infrequent-search settings.
- Hybrid Data Sources: Hybrid sources combine multiple resources and are widely used because they capture query features unavailable from individual sources.
2.2 Weighting and Ranking of Query Expansion Terms
The survey organizes expansion-term weighting and ranking around association, document-feature, and query-language-modeling approaches. It reviews how these methods use query terms, retrieved documents, and statistical models to select expansion terms.
- Overview: Weighting and ranking assign expansion-term relevance scores used to rank retrieved documents.The input combines the user query with texts extracted from selected data sources.
- Approach categories: The main categories are one-to-one association, one-to-many association, top-ranked-document feature distributions, and query language modeling.Query language modeling selects expansion terms with the highest probability.
- One-to-One Association: One-to-one association commonly links each expansion term to at least one query term using linguistic relations, thesauri, and similarity scores.WordNet can map query terms to synonyms, after which only high-scoring terms are retained.
- One-to-Many Association: One-to-many association evaluates an expansion term against multiple query terms or the query as a whole, helping preserve context.This approach addresses cases where association with one query term does not represent the complete query meaning.
- One-to-Many Association: Phrase-based expansion becomes more effective when combined with pseudo-relevance feedback rather than used alone.The combined approach improves phrase-based QE results.
- Results and comparisons: Experimental studies report marked improvements from term-scoring approaches, while ranking-method choice often has limited influence on overall system efficiency.The survey also notes that relevance models have been reported as efficient for selecting expansion terms.
- Query Language Modeling: Some methods combine query-topic and collection language models to distinguish relevant from irrelevant information in top-ranked documents.The mixture model integrates p(t|θQ) with p(t|C).
2.3 Selection of Query Expansion Terms
Selecting expansion terms requires balancing term quantity, term quality, and ranking strategy. Studies generally favor selective, query-relevant terms, but report no universal optimum number.
- Using too many expansion terms can reduce effectiveness because a smaller set usually reduces retrieval noise.
- Expansion-term effectiveness generally improves with selective additions, but the recommended quantity ranges from a few terms to several hundred.Reported recommendations include five to ten, 20–30, 30–40, and hundreds of terms; one study reports improvements of 7% to 25%.
- Term quality and type may matter more than the number of expansion terms selected.
- More informed selection of relevant terms can outperform choosing an optimum term count.
- Term-ranking approaches exploit multiple ranking functions, alternative feedback models, or reconsidered corpus documents to select expansion terms and reduce noise.
- Most QE research emphasizes indexing and document optimization, while some recent work also supports optimizing the re-ranking score.
2.4 Query Reformulation
Query reformulation reweights the expanded query before retrieval, balancing original and added terms. The survey describes feedback-based, probabilistic, and language-modeling approaches, alongside normalization and parameter-selection concerns.
- Query reformulation assigns weights to terms in the expanded query so it can retrieve more relevant documents.
- Salton and Buckley’s method balances the contribution of original query terms and expansion terms with a weighting parameter.
- Rocchio-based reweighting relates the expanded query to pseudo-relevant documents and lowers weights for expansion terms with low collection relevance.
- Reweighting combines scores with different measurement units, so normalization is required before combining original and expansion-term weights.
- The weighting parameter λ should be adjusted appropriately; one common choice gives initial query terms more significance than expansion terms.
- Language-modeling reformulation favors documents that reduce Kullback–Leibler divergence between document and query language models.
- Language-model and mixture-model approaches estimate query or document models, but short queries can make query-topic estimation difficult.
- Probabilistic query reweighting interpolates the original query model with an expanded query model, although reweighting is not mandatory for QE.
3.1 Importance of Query Expansion
Query expansion helps retrieve information missed by short or ambiguous original queries, but expanding terms creates a recall–precision trade-off that requires ranking or Boolean controls.
- Query expansion adds meaningful related terms to an original query to improve retrieval of information that the initial query may miss.The expanded query can also selectively retain terms from the original query.
- Recall can increase after expansion while precision decreases because initially relevant documents may rank lower.This trade-off is reported experimentally and motivates methods for controlling expanded-query ranking.
- AND operators favor precision but reduce recall, whereas OR operators favor recall but reduce precision.Expanded queries may use Boolean operators or combinations of them before retrieval.
- Query expansion can also improve precision by disambiguating the user query.Table 6 summarizes techniques addressing precision and recall.
3.2 Application of Query Expansion
Query expansion extends information retrieval beyond ordinary web search into personalized, question-answering, cross-language, filtering, and multimedia settings. Across these applications, it addresses mismatches between user queries and the representations used for retrieval.
- Social and personalized search: Social tagging and bookmarking support personalized query expansion by representing relationships among users, documents, and tags.Reported systems use these relationships or social tagging to improve matching between user interests and search results.
- Question Answering: Question-answering systems use query expansion to transform natural-language questions into retrieval queries that target documents containing answers.FAQ data has been used for this transformation.
- Cross-Language Information Retrieval: In cross-language retrieval, query expansion can be applied before or after translation to address translation errors and improve retrieval output.The survey reports better results for pre-translation expansion than post-translation expansion, while both outperform no expansion.
- Information Filtering: Information filtering uses query expansion to reflect users’ interests and needs when delivering relevant results from large datasets.Approaches combine relevance feedback with user queries, master queries, profiles, and other user information.
- Multimedia Information Retrieval: Multimedia retrieval applies query expansion to audio, video, and image searches, including transcription, visual descriptions, lexical features, and query logs.These methods compensate for limitations of text metadata or connect expanded text queries with multimedia representations.
- Other applications: Other reported applications include plagiarism detection, event search, text classification, patent retrieval, biomedical retrieval, enterprise search, code search, and Twitter search.The survey also lists applications in IoT, e-commerce classification, parallel computing in IR, and related areas.
4 Classification of Query Expansion Approaches
Query expansion approaches are classified by the data sources used to reformulate the initial query. The survey divides them into global analysis and local analysis, with four and two subclasses respectively.
- Data-source-based query expansion is organized into two main groups: global analysis and local analysis.Figure 5 presents the resulting classification and its subclasses.
4.1 Global Analysis
Global analysis selects expansion terms from hand-built knowledge resources or large corpora, generally treating query terms individually and assigning weights to expansion terms. The survey covers linguistic, corpus-based, search-log, and web-based sources within this classification.
- Global analysis: Global analysis selects semantically similar expansion terms from knowledge resources or large corpora and may assign them lower weights than original terms.It considers individual query terms when reformulating the initial query.
- Linguistic-based Approaches: Linguistic-based approaches use lexical, morphological, semantic, and syntactic relationships from resources such as thesauruses, dictionaries, ontologies, WordNet, and ConceptNet.Stemming reduces inflected words to root forms, while syntactic analysis uses statistical term dependencies such as co-occurrence.
- Linguistic-based Approaches: Semantic resources can improve query expansion, but WordNet-based methods face difficulties with ambiguous senses, proper nouns, and multiple synset mappings.Word sense disambiguation is described as difficult, and WordNet is most beneficial when query words are unambiguous.
- Corpus-based Approaches: Corpus-based approaches identify expansion features from whole-corpus term co-occurrence and organize terms through strategies such as clustering.They are among the earliest statistical approaches to query expansion.
- Search log-based Approaches: Search-log approaches derive related terms from user queries, URLs, and query relationships, implicitly incorporating relevance feedback.Reported experiments found search-log expansion better than pseudo-relevance feedback, although implicit measurements vary across users and tasks.
- Web-based Approaches: Web-based approaches use anchor text, Wikipedia articles, titles, hyperlinks, and FAQs as expansion sources.Anchor text can summarize linked-page content, while Wikipedia’s updated articles and links make it a prominent knowledge source.
4.2 Local Analysis
Local analysis expands queries using documents retrieved for the initial query, either through user relevance feedback or automated pseudo-relevance feedback. The survey compares these approaches with broader corpus, linguistic, and interactive methods, emphasizing query-specific effectiveness, robustness, and practical trade-offs.
- Local analysis: Local analysis selects expansion terms from documents retrieved for the user’s initial query, assuming those documents and their terms are relevant.
- Relevance feedback: Relevance feedback reformulates the query from documents that users explicitly or implicitly identify as relevant.
- Pseudo-relevance feedback: Pseudo-relevance feedback automates feedback collection by using top-ranked documents or snippets without obtaining explicit or implicit user judgments.
- Comparative analysis: Corpus-based approaches are considered more effective than linguistic approaches, while local statistical analysis seems to perform better because its extracted features are query specific.
- Comparative analysis: Hybrid techniques combining multiple approaches are reported as most effective across diverse users, queries, and document collections.
- User participation: Interactive expansion may achieve higher performance than automatic expansion, but users may find it difficult to filter terms representing relevant documents.
5 DISCUSSION AND CONCLUSIONS
The survey synthesizes query expansion research through a classification based on data sources and analytical approaches, covering methods, applications, and research trends. It concludes that QE has matured and that its applicability depends on query, data, retrieval-system, and efficiency characteristics.
- Classification: The survey classifies QE into global and local analysis according to data-source characteristics.Global analysis includes linguistic, corpus-based, search-log-based, and Web-based approaches; local analysis includes relevance feedback and pseudo-relevance feedback.
- Scope: The review analyzes QE across data sources, working methodology, importance and applications, and core approaches based on data-source features.
- Motivation: QE addresses vocabulary mismatch by adding expansion terms to the initial query to reduce query-document mismatch and improve retrieval performance.
- Findings: Manual, automatic, and interactive approaches select expansion strategies according to query features and available data sources, with studies reporting improvements in both precision and recall.
- Future directions: Personalized QE uses user profiles to reflect interests and intent, and the survey identifies personalized web search as an important future research direction.
- Applications: QE is applied beyond core IR in personalized social documents, question answering, cross-language retrieval, information filtering, multimedia retrieval, plagiarism detection, and other areas.
- Conclusion: The survey concludes that QE has matured greatly after decades of research, although challenges remain and state-of-the-art techniques are used in real-life applications.