Probe, count, and classify: categorizing hidden web databases

ABSTRACT

The contents of many valuable web-accessible databases are only accessible through search interfaces and are hence invisible to traditional web “crawlers.” Recent studies have estimated the size of this “hidden web” to be 500 billion pages, while the size of the “crawlable” web is only an estimated two billion pages. Recently, commercial web sites have started to manually organize web-accessible databases into Yahoo!-like hierarchical classification schemes. In this paper, we introduce a method for automating this classification process by using a small number of query probes. To classify a database, our algorithm 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 our technique over collections of real documents, including 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: 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]
• 2: 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
• 3: C. W. Cleverdon and J. Mills. The testing of index language devices. Aslib Proceedings, 15(4):106-130, 1963.
• 4: W. W. Cohen. Learning trees and rules with set-valued features. In Proceedings of AAAI'96, IAAI'96, volume 1, pages 709-716. AAAI, 1996.
• 5: 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]
• 6: The Deep Web: Surfacing Hidden Value. Accessible at http://www.completeplanet.com/Tutorials/DeepWeb/index.asp.
• 7: 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]
• 8: S. Gauch, G. Wang, and M. Gomez. Profusion*: Intelligent fusion from multiple, distributed search engines. The Journal of Universal Computer Science, 2(9):637-649, Sept. 1996.
• 9: 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]
• 10: G. Grefenstette and J. Nioche. Estimation of English and non-English language use on the WWW. In RIAO 2000, 2000.
• 11: 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]
• 12: Panagiotis G. Ipeirotis , Luis Gravano , Mehran Sahami, Automatic Classification of Text Databases Through Query Probing, Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.245-255, May 18-19, 2000
• 13: 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
• 14: R. L. Johnston. Gershgorin theorems for partitioned matrices. Linear Algebra and its Applications, 4:205-220, 1971.
• 15: D. Koller and M. Sahami. Toward optimal feature selection. In Machine Learning, Proceedings of the Thirteenth International Conference (ICML '96), pages 284-292, 1996.
• 16: 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
• 17: 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]
• 18: A. McCallum and K. Nigam. A comparison of event models for naive bayes text classification. In Learning for Text Categorization: Papers from the 1998 AAAI Workshop, 1998.
• 19: 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
• 20: 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
• 21: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 22: 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]
• 23: J. J. Rocchio. Relevance feedback in information retrieval. In G. Salton, editor, The SMART Information Retrieval System, pages 313-323. Prentice Hall, Englewood Cliffs, NJ, 1971.
• 24: 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]
• 25: G. Salton , M. J. McGill, The SMART and SIRE experimental retrieval systems, Readings in information retrieval, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 26: 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]
• 27: 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
• 28: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 29: 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
• 30: 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]
• 31: 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]
• 32: G. K. Zipf. Human Behavior and the Principle of Least Effort. Addison-Wesley, 1949.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.5 On-line Information Services
          Subjects: Web-based services
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.3 Group and Organization Interfaces
          Subjects: Web-based interaction

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory