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.
- 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.
- 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.
- 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.
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.
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