Semantic similarity between search engine queries using temporal correlation

Steve Chien, Nicole Immorlica

Introduction

Modern search engines frequently encounter short, ambiguous queries that are difficult to interpret through text alone. For instance, a query like "apple" could refer to the fruit or the technology company. Traditionally, search engines address this by mining large text corpora or analyzing user click-through data. However, these methods often fail to capture the shifting context of searches.

This paper proposes a novel approach: identifying semantically related queries by analyzing their temporal correlation—the degree to which their popularity fluctuates in sync over time. By treating query frequencies as time-series data, the authors demonstrate that search engines can discover highly relevant refinements (e.g., linking "IRS" to "income tax") without requiring linguistic understanding of the terms.

Methodology

The core of the proposed system is a robust mathematical measure of similarity between query frequency functions.

  1. Frequency Density: To avoid false correlations caused by general fluctuations in web traffic (e.g., higher volume during the day than at night), the authors use query density. This is defined as the number of times a specific query $q$ appears divided by the total number of all queries within a given time window.
  2. Pearson Correlation: The standard Pearson correlation coefficient is used to compare these density functions. A coefficient near 1 indicates that two queries rise and fall in popularity almost perfectly in tandem.
  3. Efficient Computation via LSH: Comparing every query pair in a massive dataset is computationally prohibitive. The authors implement a technique inspired by Locality-Sensitive Hashing (LSH). High-dimensional frequency vectors are projected onto random hyperplanes to create 128-bit signatures. Queries with similar temporal "pulses" produce similar signatures, allowing for real-time similarity lookups via simple bitwise comparisons.

Temporal Correlation Patterns

The system effectively identifies two primary types of relationships:

  • Event-Driven Correlation: This occurs when queries spike simultaneously due to a specific external event. For example, tax-related queries show a massive, synchronized peak around the April 15th deadline in the United States.
  • Periodic Correlation: This occurs when queries follow recurring human cycles, such as weekly shopping habits. Retailers like Walmart and Target exhibit nearly identical weekly rhythms, even in the absence of major news events.
Figure 3: Event-driven correlation for tax-related queries, showing a sharp synchronized spike leading up to the April 15th deadline.

Experimental Evaluation

The authors tested their approach using two massive datasets from the MSN search engine (2004):

  • Dataset 1: 33.9 million distinct queries (5 billion total searches) aggregated daily over seven months.
  • Dataset 2: 15.2 million distinct queries (1 billion total searches) with exact timestamps, allowing for finer time resolutions (e.g., 3-hour windows).

Key Insights

  • Implicit Context: Temporal correlation captures real-world relationships without a dictionary. It correctly identifies that "Scott Peterson" (a high-profile trial subject) is related to the "Modesto Bee" (a local newspaper) because their search volumes spiked together during the trial proceedings.
  • Scalability: By reducing time-series data to 128-bit signatures, the system could store similarity data for 15 million queries in just 240 MB of RAM, achieving a 776x speedup over naive linear scanning.
Figure 5: A comparison of periodic correlation (top: Walmart vs. Sears) and event-driven correlation (bottom: Scott Peterson vs. Modesto Bee).

Results and Conclusion

The results demonstrate high precision; for the most popular queries, 70% of the top ten results with a correlation of 0.9 or higher were judged to be truly semantically related. The system successfully grouped competitors (e.g., Delta and Southwest airlines) and related services based solely on shared temporal rhythms.

While highly effective for high-volume queries, the method struggles with the "long tail" of rare searches where data is too sparse to build a reliable frequency function. Future work may involve combining temporal analysis with traditional text-mining and incorporating geographic data to uncover localized correlations.

Summary updated

Abstract

We investigate the idea of finding semantically related search engine queries based on their temporal correlation; in other words, we infer that two queries are related if their popularities behave similarly over time. To this end, we first define a new measure of the temporal correlation of two queries based on the correlation coefficient of their frequency functions. We then conduct extensive experiments using our measure on two massive query streams from the MSN search engine, revealing that this technique can discover a wide range of semantically similar queries. Finally, we develop a method of efficiently finding the highest correlated queries for a given input query using far less space and time than the naive approach, making real-time implementation possible.
BibTeX
@inproceedings{chien2005semantic,
  author = {Steve Chien and Nicole Immorlica},
  title = {{Semantic similarity between search engine queries using temporal correlation}},
  booktitle = {The Web Conference},
  year = {2005},
  doi = {10.1145/1060745.1060752},
}
Figure