Random sampling from a search engine's index

ABSTRACT

We revisit a problem introduced by Bharat and Broder almost a decade ago: how to sample random pages from a search engine's index using only the search engine's public interface? Such a primitive is particularly useful in creating objective benchmarks for search engines.The technique of Bharat and Broder suffers from two well recorded biases: it favors long documents and highly ranked documents. In this paper we introduce two novel sampling techniques: a lexicon-based technique and a random walk technique. Our methods produce biased sample documents, but each sample is accompanied by a corresponding "weight", which represents the probability of this document to be selected in the sample. The samples, in conjunction with the weights, are then used to simulate near-uniform samples. To this end, we resort to three well known Monte Carlo simulation methods: rejection sampling, importance sampling and the Metropolis-Hastings algorithm.We analyze our methods rigorously and prove that under plausible assumptions, our techniques are guaranteed to produce near-uniform samples from the search engine's index. 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 or highly ranked documents. We use our algorithms to collect fresh data about the relative sizes of Google, MSN Search, and Yahoo!.

REFERENCES

• 1: Aris Anagnostopoulos , Andrei Z. Broder , David Carmel, Sampling search-engine results, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060784]
• 2: Ziv Bar-Yossef , Alexander Berg , Steve Chien , Jittat Fakcharoenphol , Dror Weitz, Approximating Aggregate Queries about Web Pages via Random Walks, Proceedings of the 26th International Conference on Very Large Data Bases, p.535-544, September 10-14, 2000
• 3: J. Battelle. John Battelle's searchblog. battellemedia.com/archives/001889.php, 2005.
• 4: Krishna Bharat , Andrei Broder, A technique for measuring the relative size and overlap of public Web search engines, Proceedings of the seventh international conference on World Wide Web 7, p.379-388, April 1998, Brisbane, Australia
• 5: Eric T. Bradlow , David C. Schmittlein, The Little Engines That Could: Modeling the Performance of World Wide Web Search Engines, Marketing Science, v.19 n.1, p.43-62, January 2000 [doi>10.1287/mksc.19.1.43.15180]
• 6: Fazli Can , Rabia Nuray , Ayisigi B. Sevdik, Automatic performance evaluation of web search engines, Information Processing and Management: an International Journal, v.40 n.3, p.495-514, January 2004 [doi>10.1016/S0306-4573(03)00040-2]
• 7: M. Cheney and M. Perry. A comparison of the size of the Yahoo! and Google indices. vburton.ncsa.uiuc.edu/indexsize.html, 2005.
• 8: P. Diaconis , L. Saloff-Coste, What do we know about the metropolis algorithm?, Journal of Computer and System Sciences, v.57 n.1, p.20-36, Aug. 1998 [doi>10.1006/jcss.1998.1576]
• 9: dmoz. The open directory project. dmoz.org.
• 10: A. Dobra and S. Fienberg. How large is the World Wide Web? Web Dynamics, pages 23--44, 2004.
• 11: Michael Gordon , Praveen Pathak, Finding information on the World Wide Web: the retrieval effectiveness of search engines, Information Processing and Management: an International Journal, v.35 n.2, p.141-180, March 1999 [doi>10.1016/S0306-4573(98)00041-7]
• 12: A. Gulli , A. Signorini, The indexable web is more than 11.5 billion pages, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062789]
• 13: W. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1):97--109, 1970.
• 14: David Hawking , Nick Craswell , Peter Bailey , Kathleen Griffihs, Measuring Search Engine Quality, Information Retrieval, v.4 n.1, p.33-59, April 2001 [doi>10.1023/A:1011468107287]
• 15: Monika R. Henzinger , Allan Heydon , Michael Mitzenmacher , Marc Najork, Measuring index quality using random walks on the Web, Proceeding of the eighth international conference on World Wide Web, p.1291-1303, May 1999, Toronto, Canada
• 16: Monika R. Henzinger , Allan Heydon , Michael Mitzenmacher , Marc Najork, On near-uniform URL sampling, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.295-308, June 2000, Amsterdam, The Netherlands
• 17: S. Lawrence and C. Giles. Searching the World Wide Web. Science, 5360(280):98, 1998.
• 18: S. Lawrence and C. Giles. Accessibility of information on the Web. Nature, 400:107--109, 1999.
• 19: J. S. Liu. Monte Carlo Strategies in Scientific Computing. Springer, 2001.
• 20: T. Mayer. Our blog is growing up and so has our index. www.ysearchblog.com/archives/000172.html.
• 21: N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller. Equations of state calculations by fast computing machines. J. of Chemical Physics, 21:1087--1091, 1953.
• 22: G. Price. More on the total database size battle and Googlewhacking with Yahoo. blog.searchenginewatch.com/blog/050811-231448, 2005.
• 23: P. Rusmevichientong, D. Pennock, S. Lawrence, and C. Lee Giles. Methods for sampling pages uniformly from the World Wide Web. In AAAI Fall Symp., 2001.
• 24: J.von Neumann. Various techniques used in connection with random digits. In John von Neumann, Collected Works, volume V. Oxford, 1963.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Measurement

Keywords:
benchmarks, sampling, search engines, size estimation