A Study of "Churn" in Tweets and Real-Time Search Queries

Jimmy Lin, Gilad Mishne

TL;DR

This paper investigates "churn" – the rapid change in term popularity – in Twitter's real-time data and search queries. Understanding this churn is crucial for building effective real-time search systems, as traditional methods rely on stable term statistics that don't hold up in dynamic environments like Twitter.

What Problem Does This Paper Address?

Real-time search engines, especially those dealing with fast-paced platforms like Twitter, face a significant challenge: the underlying data distributions change incredibly quickly. Traditional search algorithms heavily rely on term frequency (TF) and document frequency (DF) to rank results. However, on Twitter, the most popular terms in one hour can be completely different in the next. This phenomenon, termed "churn," means that static term statistics quickly become outdated, potentially leading to poor search relevance. The paper aims to characterize this churn in both tweets and user search queries on Twitter to inform the design of more robust real-time search systems.

Methods

The authors quantify churn using two primary metrics:

  • Churn Rate at Rank r: This measures the proportion of the top r most frequent terms in one time interval that are not present in the top r terms of another time interval. A churn rate of 0 means the top r terms are identical, while a rate of 1 means none overlap.
  • Out-of-Vocabulary (OOV) Rate at Rank r: This measures the proportion of the top r terms from one interval that were not observed in the top r terms of another interval. This highlights terms that are new to the top ranks and might not have existing statistics in a search index.

To capture more nuanced changes in term distributions, they also employ Kullback-Leibler (KL) Divergence. This metric quantifies the difference between two probability distributions (in this case, term distributions at different times). They use Bayesian smoothing with Dirichlet priors to handle zero probabilities (e.g., for terms not seen in a particular interval).

Analyses were performed on both interval-over-interval changes (e.g., hour 1 vs. hour 2) and changes relative to a fixed reference point (e.g., hour 1 vs. hour 5).

Datasets

The study uses data collected from Twitter during October 2011. This includes:

  • All tweets created during the month.
  • All search queries submitted to twitter.com during the month.

For comparison, they also briefly mention using the AOL query set (from 2006), but caution that it's dated and not ideal for direct comparison.

Key Insights and Ideas

  • Twitter's churn is significantly faster than web search: Even after filtering out "trending topics" (which are artificially boosted), real-time queries on Twitter exhibit much higher churn rates than web searches. This means search systems need to adapt much more rapidly to changes in user interest.
  • "Trending topics" artificially reduce churn: Removing trending topics from the analysis actually increases KL divergence for hourly query data. This suggests that trending topics, while volatile, tend to persist for longer than a typical hour, masking the underlying churn of other terms.
  • Hourly cycles are pronounced: The hour-over-hour analysis reveals strong daily cyclic patterns in tweets and queries, driven by user activity rhythms and global time zone differences.
  • Major events dramatically increase churn: During significant events (like the death of Steve Jobs), query churn can spike dramatically, changing minute-by-minute. This necessitates very frequent updates to collection statistics (potentially every 5 minutes or less).
  • Simple decay models might not be enough: The diverse patterns of query frequency changes during events suggest that basic decay functions might not adequately capture the dynamics of term popularity.

Key Results

  • Day-over-day churn: For queries (excluding trends), churn rates at rank 1000 are around 0.3166, significantly higher than web queries (0.0313).
  • Hour-over-hour churn: This shows even more pronounced churn, with rates for queries (excluding trends) at rank 1000 around 0.3059.
  • OOV rates: Day-over-day OOV rates at rank 1000 for queries (including trends) are around 0.0732, indicating a substantial fraction of terms appearing in top queries are new. Removing trends reduces this significantly.
  • Event impact: During the Steve Jobs event, KL divergence dropped sharply as the query stream focused on the event, then converged back towards the previous day's pattern, but with slightly lower divergence.
  • Tweet churn vs. Query churn: Tweet churn appears more predictable and cyclic (e.g., weekend effects), while query churn is more heavily influenced by unpredictable news events.

Limitations and Future Work

Limitations:

  • Absolute KL divergence values are less meaningful: Due to the arbitrary setting of the smoothing hyperparameter (µ=10,000), absolute KL divergence values are less important than relative comparisons across different settings.
  • OOV rates on sampled data are unreliable: The authors caution that OOV rates on sampled data (like the AOL set) are particularly unreliable.
  • Comparison to web search is limited: While they mention the AOL dataset, its limitations (age, sampling, market position) make direct comparisons difficult.

Future Work:

The authors explicitly state that this paper is a first step towards answering the question of how to correctly compute term statistics in real-time. They plan to:

  • Evaluate techniques for handling the volatility of the real-time search stream.
  • Develop methods for dealing with the limited collection statistics available for new queries.
  • Explore how to address the rapid changes in term distributions for ranking in real-time search systems.

Summary updated

Abstract

The real-time nature of Twitter means that term distributions in tweets and in search queries change rapidly: the most frequent terms in one hour may look very different from those in the next. Informally, we call this phenomenon "churn". Our interest in analyzing churn stems from the perspective of real-time search. How do we "correctly" compute term statistics, considering that the underlying distributions change rapidly? In this paper, we present an analysis of tweet and query churn on Twitter, as a first step to answering this question. Analyses reveal interesting insights on the temporal dynamics of term distributions on Twitter and hold implications for the design of search systems.
BibTeX
@inproceedings{lin2021study,
  author = {Jimmy Lin and Gilad Mishne},
  title = {{A Study of "Churn" in Tweets and Real-Time Search Queries}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/icwsm.v6i1.14297},
}

Loading related content...

Figure