Capturing collection size for distributed non-cooperative retrieval

ABSTRACT

Modern distributed information retrieval techniques require accurate knowledge of collection size. In non-cooperative environments, where detailed collection statistics are not available, the size of the underlying collections must be estimated. While several approaches for the estimation of collection size have been proposed, their accuracy has not been thoroughly evaluated. An empirical analysis of past estimation approaches across a variety of collections demonstrates that their prediction accuracy is low. Motivated by ecological techniques for the estimation of animal populations, we propose two new approaches for the estimation of collection size. We show that our approaches are significantly more accurate that previous methods, and are more efficient in use of resources required to perform the estimation.

REFERENCES

• 1: Agichtein, E., Ipeirotis, P. G., and Gravano, L. (2003). Modeling query-based access to text databases. In International Workshop on Web and Databases, pages 87--92, San Diego, California.
• 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: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 4: Peter Bailey , Nick Craswell , David Hawking, Engineering a multi-purpose test collection for web retrieval experiments, Information Processing and Management: an International Journal, v.39 n.6, p.853-871, November 2003 [doi>10.1016/S0306-4573(02)00084-5]
• 5: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 6: 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]
• 7: Craswell, N. and Hawking, D. (2002). Overview of the TREC-2002 Web Track. In Proceedings of TREC-2002, Gaithersburg, Maryland.
• 8: Nick Craswell , David Hawking , Stephen Robertson, Effective site finding using link anchor information, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.250-257, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383999]
• 9: Daryl D'Souza , James A. Thom , Justin Zobel, Collection selection for managed distributed document databases, Information Processing and Management: an International Journal, v.40 n.3, p.527-546, January 2004 [doi>10.1016/S0306-4573(03)00008-6]
• 10: Steven Garcia , Hugh E. Williams , Adam Cannane, Access-ordered indexes, Proceedings of the 27th Australasian conference on Computer science, p.7-14, January 01, 2004, Dunedin, New Zealand
• 11: Luis Gravano , Panagiotis G. Ipeirotis , Mehran Sahami, QProber: A system for automatic classification of hidden-Web databases, ACM Transactions on Information Systems (TOIS), v.21 n.1, p.1-41, January 2003 [doi>10.1145/635484.635485]
• 12: David Hawking , Paul Thomas, Server selection methods in hybrid portal search, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076050]
• 13: Ipeirotis, P. G. and Gravano, L. (2002). Distributed search over the hidden Web: Hierarchical database sampling and selection. In Proceedings of 28th International Conference on Very Large Data Bases, pages 394--405, Hong Kong, China.
• 14: Panagiotis G. Ipeirotis , Luis Gravano, When one sample is not enough: improving text database selection using shrinkage, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007655]
• 15: Panagiotis G. Ipeirotis , Luis Gravano , Mehran Sahami, Probe, count, and classify: categorizing hidden web databases, ACM SIGMOD Record, v.30 n.2, p.67-78, June 2001
• 16: Bernard J. Jansen , Amanda Spink , Tefko Saracevic, Real life, real users, and real needs: a study and analysis of user queries on the web, Information Processing and Management: an International Journal, v.36 n.2, p.207-227, Jan.1.2000 [doi>10.1016/S0306-4573(99)00056-4]
• 17: Karnatapu, S., Ramachandran, K., Wu, Z., Shah, B., Raghavan, V., and Benton, R. (2004). Estimating size of search engines in an uncooperative environment. In Workshop on Web-based Support Systems, pages 81--87, Beijing, China.
• 18: 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]
• 19: Allison L. Powell , James C. French, Comparing the performance of collection selection algorithms, ACM Transactions on Information Systems (TOIS), v.21 n.4, p.412-456, October 2003 [doi>10.1145/944012.944016]
• 20: Schumacher, F. X. and Eschmeyer, R. W. (1943). The estimation of fish populations in lakes and ponds. Journal of the Tennesse Academy of Science, 18:228--249.
• 21: Si, L. and Callan, J. (2003a). The effect of database size distribution on resource selection algorithms. In Proeedings of SIGIR 2003 Workshop on Distributed Information Retrieval, pages 31--42, Toronto, Canada.
• 22: Luo Si , Jamie Callan, Relevant document distribution estimation method for resource selection, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860490]
• 23: Luo Si , Jamie Callan, Unified utility maximization framework for resource selection, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031180]
• 24: Luo Si , Rong Jin , Jamie Callan , Paul Ogilvie, A language modeling framework for resource selection and results merging, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584856]
• 25: Sutherland, W. J. (1996). Ecological Census Techniques. Cambridge University Press.
• 26: Ellen M. Voorhees , Donna Harman, Overview of the sixth text REtrieval conference (TREC-6), Information Processing and Management: an International Journal, v.36 n.1, p.3-35, Jan. 2000 [doi>10.1016/S0306-4573(99)00043-6]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems
      H.3.7 Digital Libraries
          Subjects: Collection

General Terms:
Algorithms

Keywords:
capture-history, capture-recapture, collection size estimation, sample-resample