Classification-aware hidden-web text database selection

ABSTRACT

Many valuable text databases on the web have noncrawlable contents that are “hidden” behind search interfaces. Metasearchers are helpful tools for searching over multiple such “hidden-web” text databases at once through a unified query interface. An important step in the metasearching process is database selection, or determining which databases are the most relevant for a given user query. The state-of-the-art database selection techniques rely on statistical summaries of the database contents, generally including the database vocabulary and associated word frequencies. Unfortunately, hidden-web text databases typically do not export such summaries, so previous research has developed algorithms for constructing approximate content summaries from document samples extracted from the databases via querying. We present a novel “focused-probing” sampling algorithm that detects the topics covered in a database and adaptively extracts documents that are representative of the topic coverage of the database. Our algorithm is the first to construct content summaries that include the frequencies of the words in the database. Unfortunately, Zipf's law practically guarantees that for any relatively large database, content summaries built from moderately sized document samples will fail to cover many low-frequency words; in turn, incomplete content summaries might negatively affect the database selection process, especially for short queries with infrequent words. To enhance the sparse document samples and improve the database selection decisions, we exploit the fact that topically similar databases tend to have similar vocabularies, so samples extracted from databases with a similar topical focus can complement each other. We have developed two database selection algorithms that exploit this observation. The first algorithm proceeds hierarchically and selects the best categories for a query, and then sends the query to the appropriate databases in the chosen categories. The second algorithm uses “shrinkage,” a statistical technique for improving parameter estimation in the face of sparse data, to enhance the database content summaries with category-specific words. We describe how to modify existing database selection algorithms to adaptively decide (at runtime) whether shrinkage is beneficial for a query. A thorough evaluation over a variety of databases, including 315 real web databases as well as TREC data, suggests that the proposed sampling methods generate high-quality content summaries and that the database selection algorithms produce significantly more relevant database selection decisions and overall search results than existing algorithms.

REFERENCES

• 1: Adamic, L. A. 2002. Zipf, power-laws, and Pareto---A ranking tutorial. http://ginger.hpl.hp.com/shl/papers/ranking/ranking.html.
• 2: Eugene Agichtein , Luis Gravano, Snowball: extracting relations from large plain-text collections, Proceedings of the fifth ACM conference on Digital libraries, p.85-94, June 02-07, 2000, San Antonio, Texas, United States [doi>10.1145/336597.336644]
• 3: Agichtein, E. and Gravano, L. 2003. Querying text databases for efficient information extraction. In Proceedings of the 19th IEEE International Conference on Data Engineering (ICDE).
• 4: Baayen, R. H. 2006. Word Frequency Distributions. Springer.
• 5: Christoph Baumgarten, A probabilistic solution to the selection and fusion problem in distributed information retrieval, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.246-253, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312685]
• 6: Christoph Baumgarten, A probabilistic model for distributed information retrieval, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.258-266, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 7: Bergholz, A. and Chidlovskii, B. 2004. Using query probing to identify query language features on the Web. In Proceedings of the Distributed Multimedia Information Retrieval, SIGIR 2003 Workshop on Distributed Information Retrieval, Revised Selected and Invited Papers. Lecture Notes in Computer Science, vol. 2924, Springer, 21--30.
• 8: Bergman, M. K. 2001. The deep Web: Surfacing hidden value. J. Electron. Publ. 7, 1 (Aug.).
• 9: Berners-Lee, T., Hendler, J., and Lassila, O. 2001. The semantic Web. Sci. Amer. 284, 5 (May), 34--43.
• 10: 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]
• 11: 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
• 12: 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]
• 13: Anil S. Chakravarthy , Kenneth B. Haase, NetSerf: using semantic knowledge to find Internet information archives, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.4-11, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215326]
• 14: Yong S. Choi , Suk I. Yoo, Text Database Discovery on the Web: Neural Net Based Approach, Journal of Intelligent Information Systems, v.16 n.1, p.5-20, Jan. 2001 [doi>10.1023/A:1008708725988]
• 15: Cohen, W. W. 1996. Learning trees and rules with set-valued features. In Proceedings of the 13th National Conference on Artificial Intelligence (AAAI), 8th Conference on Innovative Applications of Artificial Intelligence (IAAI), 709--716.
• 16: Cohen, W. W. and Singer, Y. 1996. Learning to query the Web. In Proceedings of the AAAI Workshop on Internet-Based Information Systems, 16--25.
• 17: 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]
• 18: W. Bruce Croft , John Lafferty, Language Modeling for Information Retrieval, Kluwer Academic Publishers, Norwell, MA, 2003
• 19: Dempster, A. P., Laird, N. M., and Rubin, D. B. 1977. Maximum likelihood from incomplete data via the EM algorithm. J. Royal Statis. Soc. B, 39, 1--38.
• 20: Ron A. Dolin , Divyakant Agrawal , Amr El Abbadi, Pharos: a scalable distributed architecture for locating heterogeneous information sources, University of California, Santa Barbara, 1998
• 21: Daniel Dreilinger , Adele E. Howe, Experiences with selecting search engines using metasearch, ACM Transactions on Information Systems (TOIS), v.15 n.3, p.195-222, July 1997 [doi>10.1145/256163.256164]
• 22: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 23: Fellbaum, C. 1998. WordNet: An Electronic Lexical Database. MIT Press.
• 24: Gary W. Flake , Eric J. Glover , Steve Lawrence , C. Lee Giles, Extracting query modifications from nonlinear SVMs, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511488]
• 25: 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]
• 26: James C. French , Allison L. Powell , Charles L. Viles , Travis Emmitt , Kevin J. Prey, Evaluating database selection techniques: a testbed and experiment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.121-129, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290976]
• 27: 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]
• 28: Gauch, S., Wang, G., and Gomez, M. 1996. ProFusion*: Intelligent fusion from multiple, distributed search engines. J. Universal Comput. Sci. 2, 9 (Sept.), 637--649.
• 29: Rayid Ghani , Rosie Jones , Dunja Mladenić, Mining the web to create minority language corpora, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502633]
• 30: 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]
• 31: Luis Gravano , Héctor García-Molina , Anthony Tomasic, GlOSS: text-source discovery over the Internet, ACM Transactions on Database Systems (TODS), v.24 n.2, p.229-264, June 1999 [doi>10.1145/320248.320252]
• 32: Luis Gravano , Chen-Chuan K. Chang , Héctor García-Molina , Andreas Paepcke, STARTS: Stanford proposal for Internet meta-searching, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.207-218, May 11-15, 1997, Tucson, Arizona, United States
• 33: Grefenstette, G. and Nioche, J. 2000. Estimation of English and non-English language use on the WWW. In Recherche d'Information Assistée par Ordinateur (RIAO).
• 34: Harman, D. 1996. Overview of the Fourth Text REtrieval Conference (TREC-4). In NIST Special Publication 500-236: The 4th Text REtrieval Conference (TREC-4), 1--24.
• 35: Hastie, T., Tibshirani, R., and Friedman, J. H. 2001. The Elements of Statistical Learning. Springer.
• 36: 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]
• 37: David Hawking , Paul Thistlewaite, Methods for information server selection, ACM Transactions on Information Systems (TOIS), v.17 n.1, p.40-76, Jan. 1999 [doi>10.1145/297117.297123]
• 38: 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]
• 39: Panagiotis G. Ipeirotis , Luis Gravano, Distributed search over the hidden web: hierarchical database sampling and selection, Proceedings of the 28th international conference on Very Large Data Bases, p.394-405, August 20-23, 2002, Hong Kong, China
• 40: Frederick Jelinek, Statistical methods for speech recognition, MIT Press, Cambridge, MA, 1998
• 41: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 42: Brewster Kahle , Harry Morris , Jonathan Goldman , Thomas Erickson , John Curran, Interfaces for distributed systems of information servers, Journal of the American Society for Information Science, v.44 n.8, p.453-467, Sept. 1993 [doi>10.1002/(SICI)1097-4571(199309)44:8<453::AID-ASI4>3.0.CO;2-E]
• 43: Leah S. Larkey , Margaret E. Connell , Jamie Callan, Collection selection and results merging with topically organized U.S. patents and TREC data, Proceedings of the ninth international conference on Information and knowledge management, p.282-289, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354830]
• 44: Zhenyu Liu , Chang Luo , Junghoo Cho , Wesley W. Chu, A Probabilistic Approach to Metasearching with Adaptive Probing, Proceedings of the 20th International Conference on Data Engineering, p.547, March 30-April 02, 2004
• 45: Udi Manber , Peter A. Bigot, The search broker, Proceedings of the USENIX Symposium on Internet Technologies and Systems on USENIX Symposium on Internet Technologies and Systems, p.21-21, December 08-11, 1997, Monterey, California
• 46: Mandelbrot, B. B. 1988. Fractal Geometry of Nature. W. H. Freeman.
• 47: Marques De Sá, J. P. 2003. Applied Statistics. Springer.
• 48: Andrew McCallum , Ronald Rosenfeld , Tom M. Mitchell , Andrew Y. Ng, Improving Text Classification by Shrinkage in a Hierarchy of Classes, Proceedings of the Fifteenth International Conference on Machine Learning, p.359-367, July 24-27, 1998
• 49: 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
• 50: Weiyi Meng , King-Lup Liu , Clement T. Yu , Xiaodong Wang , Yuhsi Chang , Naphtali Rishe, Determining Text Databases to Search in the Internet, Proceedings of the 24rd International Conference on Very Large Data Bases, p.14-25, August 24-27, 1998
• 51: G. Monroe , J. French , A. Powell, Obtaining Language Models of Web Collections Using Query-Based Sampling Techniques, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 3, p.67.2, January 07-10, 2002
• 52: Mike Perkowitz , Robert B. Doorenbos , Oren Etzioni , Daniel S. Weld, Learning to Understand Information on the Internet: AnExample-Based Approach, Journal of Intelligent Information Systems, v.8 n.2, p.133-153, March/April 1997 [doi>10.1023/A:1008672508721]
• 53: 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]
• 54: 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]
• 55: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 56: 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
• 57: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 58: Mark A. Sheldon, Content routing: a scalable architecture for network-based information discovery, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 59: Shokouhi, M. 2007. Central-Rank-Based collection selection in uncooperative distributed information retrieval. In Proceedings of the 29th European Conference on IR Research (ECIR).
• 60: Luo Si , Jamie Callan, Modeling search engine effectiveness for federated 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.1076051]
• 61: 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]
• 62: Si, L. and Callan, J. P. 2004b. The effect of database size distribution on resource selection algorithms. In Proceedings of the Distributed Multimedia Information Retrieval, SIGIR 2003 Workshop on Distributed Information Retrieval, Revised Selected and Invited Papers. Lecture Notes in Computer Science, vol. 2924, Springer, 31--42.
• 63: 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]
• 64: 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]
• 65: Atsushi Sugiura , Oren Etzioni, Query routing for Web search engines: architectures and experiments, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.417-429, June 2000, Amsterdam, The Netherlands
• 66: Ellen M. Voorhees , Narendra K. Gupta , Ben Johnson-Laird, Learning collection fusion strategies, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.172-179, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215357]
• 67: Voorhees, E. M. and Harman, D. 1998. Overview of the Sixth Text REtrieval Conference (TREC-6). In NIST Special Publication 500-240: The 6th Text REtrieval Conference (TREC-6), 1--24.
• 68: 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]
• 69: Jinxi Xu , W. Bruce Croft, Cluster-based language models for distributed retrieval, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.254-261, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312687]
• 70: Yangarber, R. and Grishman, R. 1998. NYU: Description of the Proteus/PET system as used for MUC-7. In Proceedings of the 7th Message Understanding Conference (MUC).
• 71: Clement Yu , Weiyi Meng , Wensheng Wu , King-Lup Liu, Efficient and effective metasearch for text databases incorporating linkages among documents, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.187-198, May 21-24, 2001, Santa Barbara, California, United States
• 72: Clement Yu , Weiyi Meng , King-Lup Liu , Wensheng Wu , Naphtali Rishe, Efficient and effective metasearch for a large number of text databases, Proceedings of the eighth international conference on Information and knowledge management, p.217-224, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/319950.320005]
• 73: Budi Yuwono , Dik Lun Lee, Server Ranking for Distributed Text Retrieval Systems on the Internet, Proceedings of the Fifth International Conference on Database Systems for Advanced Applications (DASFAA), p.41-50, April 01-04, 1997
• 74: Chengxiang Zhai , John Lafferty, A study of smoothing methods for language models applied to information retrieval, ACM Transactions on Information Systems (TOIS), v.22 n.2, p.179-214, April 2004 [doi>10.1145/984321.984322]
• 75: ChengXiang Zhai , John Lafferty, Two-stage language models for information retrieval, 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.564387]
• 76: Chengxiang Zhai , John Lafferty, A study of smoothing methods for language models applied to Ad Hoc information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.334-342, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384019]
• 77: Zipf, G. K. 1949. Human Behavior and the Principle of Least Effort. Addison-Wesley.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Abstracting methods

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases; Textual databases
      H.2.5 Heterogeneous Databases
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.3 Information Search and Retrieval
          Subjects: Search process; Selection process
      H.3.4 Systems and Software
          Subjects: Information networks; Performance evaluation (efficiency and effectiveness)
      H.3.5 On-line Information Services
          Subjects: Web-based services
      H.3.6 Library Automation
          Subjects: Large text archives
      H.3.7 Digital Libraries

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
Distributed information retrieval, database selection, web search