Distributed query sampling: a quality-conscious approach

ABSTRACT

We present an adaptive distributed query-sampling framework that is quality-conscious for extracting high-quality text database samples. The framework divides the query-based sampling process into an initial seed sampling phase and a quality-aware iterative sampling phase. In the second phase the sampling process is dynamically scheduled based on estimated database size and quality parameters derived during the previous sampling process. The unique characteristic of our adaptive query-based sampling framework is its self-learning and self-configuring ability based on the overall quality of all text databases under consideration. We introduce three quality-conscious sampling schemes for estimating database quality, and our initial results show that the proposed framework supports higher-quality document sampling than existing approaches.

REFERENCES

• 1: E. Agichtein, P. Ipeirotis, and L. Gravano. Modeling query-based access to text databases. In WebDB, 2003.
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: 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]
• 4: Jamie Callan , Margaret Connell , Aiqun Du, Automatic discovery of language models for text databases, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.479-490, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 5: J. Callan et al. The effects of query-based sampling on automatic database selection algorithms. Technical Report CMU-LTI-00-162, CMU, 2000.
• 6: James P. Callan , Zhihong Lu , W. Bruce Croft, Searching distributed collections with inference networks, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.21-28, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215328]
• 7: W. W. Cohen and Y. Singer. Learning to query the Web. In AAAI Workshop on Internet-Based Info. Systems. 1996.
• 8: Nick Craswell , Peter Bailey , David Hawking, Server selection on the World Wide Web, Proceedings of the fifth ACM conference on Digital libraries, p.37-46, June 02-07, 2000, San Antonio, Texas, United States [doi>10.1145/336597.336628]
• 9: James C. French , Allison L. Powell , Jamie Callan , Charles L. Viles , Travis Emmitt , Kevin J. Prey , Yun Mou, Comparing the performance of database selection algorithms, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.238-245, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312684]
• 10: Norbert Fuhr, A decision-theoretic approach to database selection in networked IR, ACM Transactions on Information Systems (TOIS), v.17 n.3, p.229-249, July 1999 [doi>10.1145/314516.314517]
• 11: Luis Gravano , Hector Garcia-Molina, Generalizing GlOSS to Vector-Space Databases and Broker Hierarchies, Proceedings of the 21th International Conference on Very Large Data Bases, p.78-89, September 11-15, 1995
• 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: Panagiotis G. Ipeirotis , Alexandros Ntoulas , Junghoo Cho , Luis Gravano, Modeling and Managing Content Changes in Text Databases, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.606-617, April 05-08, 2005 [doi>10.1109/ICDE.2005.91]
• 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, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.67-78, May 21-24, 2001, Santa Barbara, California, United States
• 16: J. Lin. Divergence measures based on the shannon entropy. IEEE Trans. on Inf. Theory, 37(1):145--151, 1991.
• 17: King-Lup Liu , Adrain Santoso , Clement Yu , Weiyi Meng, Discovering the representative of a search engine, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502696]
• 18: Jie Lu , Jamie Callan, Merging retrieval results in hierarchical peer-to-peer networks, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009076]
• 19: Weiyi Meng , Clement Yu , King-Lup Liu, Detection of Heterogeneities in a Multiple Text Database Environment, Proceedings of the Fourth IECIS International Conference on Cooperative Information Systems, p.22, September 02-04, 1999
• 20: Henrik Nottelmann , Norbert Fuhr, Evaluating different methods of estimating retrieval quality 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.860489]
• 21: Alexandros Ntoulas , Petros Zerfos , Junghoo Cho, Downloading textual hidden web content through keyword queries, Proceedings of the 5th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2005, Denver, CO, USA [doi>10.1145/1065385.1065407]
• 22: M. F. Porter. An algorithm for suffix stripping. Program, 14(3):130--137, 1980.
• 23: Allison L. Powell , James C. French , Jamie Callan , Margaret Connell , Charles L. Viles, The impact of database selection on distributed searching, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.232-239, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345584]
• 24: Sriram Raghavan , Hector Garcia-Molina, Crawling the Hidden Web, Proceedings of the 27th International Conference on Very Large Data Bases, p.129-138, September 11-14, 2001
• 25: Luo Si , Jamie Callan, Using sampled data and regression to merge search engine results, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564382]
• 26: 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]
• 27: Wenxian Wang , Weiyi Meng , Clement Yu, Concept Hierarchy Based Text Database Categorization in a Metasearch Engine Environment, Proceedings of the First International Conference on Web Information Systems Engineering (WISE'00)-Volume 1, p.283, June 19-20, 2000
• 28: Jinxi Xu , Jamie Callan, Effective retrieval with distributed collections, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.112-120, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290974]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

General Terms:
Algorithms, Experimentation

Keywords:
adaptive, distributed IR, quality, sampling