QProber: A system for automatic classification of hidden-Web databases

ABSTRACT

The contents of many valuable Web-accessible databases are only available through search interfaces and are hence invisible to traditional Web "crawlers." Recently, commercial Web sites have started to manually organize Web-accessible databases into Yahoo!-like hierarchical classification schemes. Here we introduce QProber, a modular system that automates this classification process by using a small number of query probes, generated by document classifiers. QProber can use a variety of types of classifiers to generate the probes. To classify a database, QProber does not retrieve or inspect any documents or pages from the database, but rather just exploits the number of matches that each query probe generates at the database in question. We have conducted an extensive experimental evaluation of QProber over collections of real documents, experimenting with different types of document classifiers and retrieval models. We have also tested our system with over one hundred Web-accessible databases. Our experiments show that our system has low overhead and achieves high classification accuracy across a variety of databases.

REFERENCES

• 1: 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]
• 2: Agichtein, E. and Gravano, L. 2003. Querying text databases for efficient information extraction. In Proceedings of the Nineteenth IEEE International Conference on Data Engineering (ICDE 2003).
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 4: Chidanand Apté , Fred Damerau , Sholom M. Weiss, Automated learning of decision rules for text categorization, ACM Transactions on Information Systems (TOIS), v.12 n.3, p.233-251, July 1994 [doi>10.1145/183422.183423]
• 5: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555]
• 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: 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
• 8: Cleverdon, C. W. and Mills, J. 1963. The testing of index language devices. Aslib Proc. 15, 4, 106--130.
• 9: Cohen, W. and Singer, Y. 1996. Learning to query the Web. In AAAI Workshop on Internet-Based Information Systems, 16--25.
• 10: Cohen, W. W. 1996. Learning trees and rules with set-valued features. In Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI-96) Eighth Conference on Innovative Applications of Artificial Intelligence (IAAI-96), 709--716.
• 11: 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]
• 12: Mark William Craven , Jude W. Shavlik, Extracting comprehensible models from trained neural networks, 1996
• 13: Deerwester, S. C., Dumais, S. T., Landauer, T. K., Furnas, G. W., and Harshman, R. A. 1990. Indexing by latent semantic analysis. J. Amer. Soc. Inf. Sci. 41, 6, 391--407.
• 14: R. Dolin , D. Agrawal , E. El Abbadi, Scalable collection summarization and selection, Proceedings of the fourth ACM conference on Digital libraries, p.49-58, August 11-14, 1999, Berkeley, California, United States [doi>10.1145/313238.313257]
• 15: Duda, R. O. and Hart, P. E. 1973. Pattern Classification and Scene Analysis. Wiley, New York.
• 16: Susan Dumais , John Platt , David Heckerman , Mehran Sahami, Inductive learning algorithms and representations for text categorization, Proceedings of the seventh international conference on Information and knowledge management, p.148-155, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288651]
• 17: 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]
• 18: Gauch, S., Wang, G., and Gomez, M. 1996. ProFusion*: Intelligent fusion from multiple, distributed search engines. J. Univ. Comput. Sci. 2, 9 (Sept.), 637--649.
• 19: 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]
• 20: 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]
• 21: Gravano, L., Ipeirotis, P. G., and Sahami, M. 2002. Query- vs. crawling-based classification of searchable web databases. IEEE Data Eng. Bull. 25, 1 (Mar.), 43--50.
• 22: 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 2000).
• 23: 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]
• 24: Ipeirotis, P. G. and Gravano, L. 2002. Distributed search over the hidden Web: Hierarchical database sampling and selection. In Proceedings of the 28th International Conference on Very Large Databases (VLDB 2002).
• 25: Panagiotis G. Ipeirotis , Luis Gravano , Mehran Sahami, PERSIVAL demo: categorizing hidden-web resources, Proceedings of the 1st ACM/IEEE-CS joint conference on Digital libraries, p.454, January 2001, Roanoke, Virginia, United States [doi>10.1145/379437.379782]
• 26: 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
• 27: 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
• 28: Johnston, R. 1971. Gershgorin theorems for partitioned matrices. Lin. Algeb. Appl. 4, 3 (July), 205--220.
• 29: Ron Kohavi , George H. John, Wrappers for feature subset selection, Artificial Intelligence, v.97 n.1-2, p.273-324, Dec. 1997 [doi>10.1016/S0004-3702(97)00043-X]
• 30: Glossary of Terms, Machine Learning, v.30 n.2-3, p.271-274, Feb./ March, 1998
• 31: Koller, D. and Sahami, M. 1996. Toward optimal feature selection. In Proceedings of the Thirteenth International Conference on Machine Learning (ICML'96), 284--292.
• 32: Daphne Koller , Mehran Sahami, Hierarchically Classifying Documents Using Very Few Words, Proceedings of the Fourteenth International Conference on Machine Learning, p.170-178, July 08-12, 1997
• 33: Koster, M. 2002. Robots exclusion standard. Available at http://www.robotstxt.org/.
• 34: David D. Lewis , Robert E. Schapire , James P. Callan , Ron Papka, Training algorithms for linear text classifiers, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.298-306, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243277]
• 35: McCallum, A. and Nigam, K. 1998. A comparison of event models for naive Bayes text classification. In Learning for Text Categorization: Papers from the 1998 AAAI Workshop, 41--48.
• 36: 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
• 37: 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
• 38: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 39: Nils J. Nilsson, The mathematical foundations of learning machines, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 40: 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]
• 41: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 42: 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
• 43: Rocchio, J. 1971. Relevance feedback in information retrieval. In The SMART Information Retrieval System. Prentice-Hall, Englewood Cliffs, NJ, 313--323.
• 44: Mehran Sahami , Daphne Koller, Using machine learning to improve information access, 1999
• 45: Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0]
• 46: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 47: G. Salton , M. J. McGill, The SMART and SIRE experimental retrieval systems, Readings in information retrieval, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 48: Hinrich Schütze , David A. Hull , Jan O. Pedersen, A comparison of classifiers and document representations for the routing problem, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.229-237, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215365]
• 49: 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
• 50: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 51: 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
• 52: 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]
• 53: Yiming Yang , Xin Liu, A re-examination of text categorization methods, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.42-49, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312647]
• 54: Yangarber, R. and Grishman, R. 1998. NYU: Description of the Proteus/PET system as used for MUC-7. In Proceedings of the Seventh Message Understanding Conference (MUC-7).
• 55: Zipf, G. K. 1949. Human Behavior and the Principle of Least Effort. Addison-Wesley, Reading, MA.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Textual databases; Distributed databases
      H.2.5 Heterogeneous Databases
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering; Clustering; Search process; Selection process
      H.3.4 Systems and Software
      H.3.5 On-line Information Services
          Subjects: Web-based services
      H.3.7 Digital Libraries

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Database classification, Web databases, hidden Web