Article,
Random sampling from a search engine's index
J. ACM, 55 (5): 24:1--24:74 (November 2008)
DOI: 10.1145/1411509.1411514
Abstract
We revisit a problem introduced by Bharat and Broder almost a decade ago: How to sample random pages from the corpus of documents indexed by a search engine, using only the search engine's public interface? Such a primitive is particularly useful in creating objective benchmarks for search engines.</p> <p>The technique of Bharat and Broder suffers from a well-recorded bias: it favors long documents. In this article we introduce two novel sampling algorithms: a lexicon-based algorithm and a random walk algorithm. Our algorithms produce <i>biased</i> samples, but each sample is accompanied by a <i>weight</i>, which represents its bias. The samples, in conjunction with the weights, are then used to <i>simulate</i> near-uniform samples. To this end, we resort to four well-known Monte Carlo simulation methods: <i>rejection sampling</i>, <i>importance sampling</i>, the <i>Metropolis--Hastings</i> algorithm, and the <i>Maximum Degree</i> method.</p> <p>The limited access to search engines force our algorithms to use bias weights that are only “approximate”. We characterize analytically the effect of approximate bias weights on Monte Carlo methods and conclude that our algorithms are <i>guaranteed</i> to produce near-uniform samples from the search engine's corpus. Our study of approximate Monte Carlo methods could be of independent interest.</p> <p>Experiments on a corpus of 2.4 million documents substantiate our analytical findings and show that our algorithms do not have significant bias towards long documents. We use our algorithms to collect comparative statistics about the corpora of the Google, MSN Search, and Yahoo! search engines.
