LNRE Methods in Estimating Impressions in Search Engine Results

• Activity Number: 248
• Type: Contributed
• Date/Time: Monday, August 2, 2010 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Carrie Grimes and Meeyoung Park*+
• Companies: Google and Google
• Keywords: LNRE ; MLE ; Good-Turing estimator ; sparse data ; impressions

Abstract

Mining historical data to predict future appearances or "impressions" of a web page in search engine results is important for improving search engine efficiency. However, because the population of documents is extremely large, historical data about impressions may be very sparse. Here we use sampled query traffic to show that even for very large samples, the number of single-frequency pages continues to increase as the data collection time window expands. We introduce a novel approach to impression frequency estimation by using LNRE (Large Number of Rare Events) methods that have traditionally been used in modeling the occurrence of unique words in a text. Using the Good-Turing method, we obtain more accurate predictions than with the Maximum Likelihood Estimator. We show that this improved accuracy translates to substantive benefits in designing a multi-tiered web search index.