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

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 biased samples, but each sample is accompanied by a weight, which represents its bias. The samples, in conjunction with the weights, are then used to simulate near-uniform samples. To this end, we resort to four well-known Monte Carlo simulation methods: rejection sampling, importance sampling, the Metropolis--Hastings algorithm, and the Maximum Degree method.

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 guaranteed to produce near-uniform samples from the search engine's corpus. Our study of approximate Monte Carlo methods could be of independent interest.

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.

REFERENCES

• 1: Aldous, D. 1987. On the Markov chain simulation method for uniform combinatorial distributed and simulated annealing. Prob. Eng. Inf. Sci. 1, 33--46.
• 2: 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]
• 3: 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
• 4: Ziv Bar-Yossef , Maxim Gurevich, Efficient search engine measurements, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242627]
• 5: Battelle, J. 2005. John Battelle's searchblog. http://battellemedia.com/archives/001889.php.
• 6: 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
• 7: Bondar, S. 2006. Search engine indexing limits: Where do the bots stop? (Available at http://www.sitepoint.com/article/indexing-limits-where-bots-stop.)
• 8: Stephen Boyd , Persi Diaconis , Lin Xiao, Fastest Mixing Markov Chain on a Graph, SIAM Review, v.46 n.4, p.667-689, 2004 [doi>10.1137/S0036144503423264]
• 9: 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]
• 10: Andrei Broder , Marcus Fontura , Vanja Josifovski , Ravi Kumar , Rajeev Motwani , Shubha Nabar , Rina Panigrahy , Andrew Tomkins , Ying Xu, Estimating corpus size via queries, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183699]
• 11: 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]
• 12: Cheney, M., and Perry, M. 2005. A comparison of the size of the Yahoo! and Google indices. Available at http://vburton.ncsa.uiuc.edu/indexsize.html.
• 13: Davison, B. D. 2004. The potential of the metasearch engine. In Proceedings of the Annual Meeting of the American Society for Information Science and Technology (ASIST). Vol. 41. 393--402.
• 14: 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]
• 15: Dobra, A., and Fienberg, S. E. 2004. How large is the World Wide Web? Web Dyn. 23--44.
• 16: David Gillman, A Chernoff Bound for Random Walks on Expander Graphs, SIAM Journal on Computing, v.27 n.4, p.1203-1220, Aug. 1998 [doi>10.1137/S0097539794268765]
• 17: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 18: 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]
• 19: 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]
• 20: Hastings, W. K. 1970. Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57, 1, 97--109.
• 21: 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]
• 22: Monika R. Henzinger , Allan Heydon , Michael Mitzenmacher , Marc Najork, Measuring index quality using random walks on the Web, Proceedings of the eighth international conference on World Wide Web, p.1291-1303, May 1999, Toronto, Canada
• 23: 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
• 24: Hesterberg, T. C. 1988. Advances in importance sampling. Ph.D. dissertation, Stanford University.
• 25: Nabil Kahale, Large Deviation Bounds for Markov Chains, Combinatorics, Probability and Computing, v.6 n.4, p.465-474, December 1997 [doi>10.1017/S0963548397003209]
• 26: Lawrence, S., and Giles, C. L. 1998. Searching the World Wide Web. Science 5360, 280, 98.
• 27: Lawrence, S., and Giles, C. L. 1999. Accessibility of information on the Web. Nature 400, 107--109.
• 28: Liu, J. S. 1996. Metropolized independent sampling with comparisons to rejection sampling and importance sampling. Stat. Comput. 6, 113--119.
• 29: Liu, J. S. 2001. Monte Carlo Strategies in Scientific Computing. Springer-Verlag, New York.
• 30: Marshal, A. 1956. The use of multi-stage sampling schemes in Monte Carlo computations. In Proceedings of the Symposium on Monte Carlo Methods, M. Meyer, Ed. Vol. 21. Wiley, New York, 123--140.
• 31: Mayer, T. 2005. Our blog is growing up - and so has our index. Available at http://www.ysearchblog.com/archives/000172.html.
• 32: Frank McCown , Michael L. Nelson, Agreeing to disagree: search engines and their public interfaces, Proceedings of the 7th ACM/IEEE-CS joint conference on Digital libraries, June 18-23, 2007, Vancouver, BC, Canada [doi>10.1145/1255175.1255237]
• 33: Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., and Teller, E. 1953. Equations of state calculations by fast computing machines. J. Chem. Phys. 21, 1087--1091.
• 34: Price, G. 2005. More on the total database size battle and Googlewhacking with Yahoo. Available at http://blog.searchenginewatch.com/blog/050811-231448.
• 35: Rusmevichientong, P., Pennock, D., Lawrence, S., and Giles, C. L. 2001. Methods for sampling pages uniformly from the World Wide Web. In Proceedings of AAAI Fall Symposium on Using Uncertainty within Computation.
• 36: Siegmund, D. 1985. Sequential Analysis - Tests and Confidence Intervals. Springer-Verlag, New York.
• 37: Alistair Sinclair, Algorithms for random generation and counting: a Markov chain approach, Birkhauser Verlag, Basel, Switzerland, 1993
• 38: Stuart, A. and Ord, J.-K. 1994. Kendall's Advanced Theory of Statistics. Vol. 1, Distribution Theory. Haddon Arnold, London, UK.
• 39: Sullivan, D. 2005. Search engine sizes. http://searchenginewatch.com/showPage.html?page=2156481.
• 40: Véronis, J. 2005. Yahoo: Missing pages? (2). http://aixtal.blogspot.com/2005/08/yahoo-missing-pages-2.html.
• 41: von Neumann, J. 1963. Various techniques used in connection with random digits. In John von Neumann, Collected Works. Vol. V. Oxford.

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