Estimating corpus size via queries

ABSTRACT

We consider the problem of estimating the size of a collection of documents using only a standard query interface. Our main idea is to construct an unbiased and low-variance estimator that can closely approximate the size of any set of documents defined by certain conditions, including that each document in the set must match at least one query from a uniformly sampleable query pool of known size, fixed in advance.Using this basic estimator, we propose two approaches to estimating corpus size. The first approach requires a uniform random sample of documents from the corpus. The second approach avoids this notoriously difficult sample generation problem, and instead uses two fairly uncorrelated sets of terms as query pools; the accuracy of the second approach depends on the degree of correlation among the two sets of terms.Experiments on a large TREC collection and on three major search engines demonstrates the effectiveness of our algorithms.

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: J. Bar-Ilan. Size of the web, search engine coverage and overlap - methodological issues. Unpublished, 2006.
• 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, Random sampling from a search engine's index, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135833]
• 5: Krishna Bharat , Andrei Broder, Mirror, mirror on the Web: a study of host pairs with replicated content, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1579-1590, May 17, 1999
• 6: Krishna Bharat , Andrei Broder, A technique for measuring the relative size and overlap of public Web search engines, Computer Networks and ISDN Systems, v.30 n.1-7, p.379-388, April 1, 1998
• 7: Krishna Bharat , Andrei Broder , Jeffrey Dean , Monika R. Henzinger, A comparison of techniques to find mirrored hosts on the WWW, Journal of the American Society for Information Science, v.51 n.12, p.1114-1122, Oct. 2000 [doi>10.1002/1097-4571(2000)9999:9999<::AID-ASI1025>3.0.CO;2-0]
• 8: A. Z. Broder. Web measurements via random queries. Presentation at the Workshop on Web Measurement, Metrics, and Mathematical Models (WWW10 Conference), 2000.
• 9: Jamie Callan , Margaret Connell, Query-based sampling of text databases, ACM Transactions on Information Systems (TOIS), v.19 n.2, p.97-130, April 2001 [doi>10.1145/382979.383040]
• 10: 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]
• 11: Monika R. Henzinger , Allan Heydon , Michael Mitzenmacher , Marc Najork, On near-uniform URL sampling, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.295-308, June 2000
• 12: Steve Lawrence , C. Lee Giles, Accessibility of information on the Web, intelligence, v.11 n.1, p.32-39, Spring 2000 [doi>10.1145/333175.333181]
• 13: S. Lawrence and C. L. Giles. Searching the world wide web. Science, 280(5360):98--100, 1998.
• 14: King-Lup Liu , Clement Yu , Weiyi Meng, Discovering the representative of a search engine, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584909]
• 15: P. Rusmevichientong, D. M. Pennock, S. Lawrence, and C. L. Giles. Methods for sampling pages uniformly from the world wide web. In AAAI Fall Symposium on Using Uncertainty Within Computation, pages 121--128, 2001.
• 16: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 17: S. Wu, F. Gibb, and F. Crestani. Experiments with document archive size detection. In Proc. 25th European Conference on IR Research, volume 2633 of Lecture Notes in Computer Science, pages 294--304. Springer, 2003.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
corpus size, estimator, random sampling