Structured databases on the web: observations and implications

ABSTRACT

The Web has been rapidly "deepened" by the prevalence of databases online. With the potentially unlimited information hidden behind their query interfaces, this "deep Web" of searchable databses is clearly an important frontier for data access. This paper surveys this relatively unexplored frontier, measuring characteristics pertinent to both exploring and integrating structured Web sources. On one hand, our "macro" study surveys the deep Web at large, in April 2004, adopting the random IP-sampling approach, with one million samples. (How large is the deep Web? How is it covered by current directory services?) On the other hand, our "micro" study surveys source-specific characteristics over 441 sources in eight representative domains, in December 2002. (How "hidden" are deep-Web sources? How do search engines cover their data? How complex and expressive are query forms?) We report our observations and publish the resulting datasets to the research community. We conclude with several implications (of our own) which, while necessarily subjective, might help shape research directions and solutions.

REFERENCES

• 1: BrightPlanet.com. The deep web: Surfacing hidden value. Accessible at http://brightplanet.com, July 2000.
• 2: Steve Lawrence and C. Lee Giles. Accessibility of information on the web. Nature, 400(6740):107--109, 1999.
• 3: Ed O'Neill, Brian Lavoie, and Rick Bennett. Web characterization. Accessible at "http://wcp.oclc.org".
• 4: GNU. wget. Accessible at "http://www.gnu.org/software/wget/wget.html".
• 5: Kevin Chen-Chuan Chang, Bin He, Chengkai Li, and Zhen Zhang. The UIUC web integration repository. Computer Science Department, University of Illinois at Urbana-Champaign. http://metaquerier.cs.uiuc.edu/repository, 2003.
• 6: G. K. Zipf. Human Behavior and the Principle of Least Effort. Addison-Wesley, Cambridge, Massachusetts, 1949.
• 7: William W. Cohen. Some practical observations on integration of web information. In WebDB (Informal Proceedings), pages 55--60, 1999.
• 8: Marti A. Hearst, Information Integration, IEEE Intelligent Systems, v.13 n.5, p.12-24, September 1998 [doi>10.1109/5254.722342]
• 9: Daniela Florescu , Alon Levy , Alberto Mendelzon, Database techniques for the World-Wide Web: a survey, ACM SIGMOD Record, v.27 n.3, p.59-74, Sept. 1, 1998 [doi>10.1145/290593.290605]
• 10: 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
• 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: 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]
• 13: 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
• 14: 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
• 15: Jeffrey D. Ullman, Information Integration Using Logical Views, Proceedings of the 6th International Conference on Database Theory, p.19-40, January 08-10, 1997
• 16: Zhen Zhang , Bin He , Kevin Chen-Chuan Chang, Understanding Web query interfaces: best-effort parsing with hidden syntax, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007583]
• 17: Bin He , Kevin Chen-Chuan Chang, Statistical schema matching across web query interfaces, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872784]
• 18: Bin He , Kevin Chen-Chuan Chang , Jiawei Han, Discovering complex matchings across web query interfaces: a correlation mining approach, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014071]
• 19: Alon Y. Levy , Anand Rajaraman , Joann J. Ordille, Querying Heterogeneous Information Sources Using Source Descriptions, Proceedings of the 22th International Conference on Very Large Data Bases, p.251-262, September 03-06, 1996
• 20: Yannis Papakonstantinou , Hector Garcia-Molina , Jeffrey D. Ullman, MedMaker: A Mediation System Based on Declarative Specifications, Proceedings of the Twelfth International Conference on Data Engineering, p.132-141, February 26-March 01, 1996
• 21: Renée J. Miller , Mauricio A. Hernández , Laura M. Haas , Lingling Yan , C. T. Howard Ho , Ronald Fagin , Lucian Popa, The Clio project: managing heterogeneity, ACM SIGMOD Record, v.30 n.1, p.78-83, March 2001 [doi>10.1145/373626.373713]
• 22: Luis Gravano, Chen-Chuan K. Chang, Héctor García-Molina, and Andreas Paepcke. STARTS: Stanford protocol proposal for internet retrieval and search. Accessible at http://www-db.stanford.edu/~gravano/starts.html, August 1996.
• 23: Luis Gravano , Hector Garcia-Molina, Merging Ranks from Heterogeneous Internet Sources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.196-205, August 25-29, 1997
• 24: Bertram Ludäscher , Amarnath Gupta, Modeling Interactive Web Sources for Information Mediation, Proceedings of the Workshops on Evolution and Change in Data Management, Reverse Engineering in Information Systems, and the World Wide Web and Conceptual Modeling, p.225-238, November 15-18, 1999
• 25: 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
• 26: James Caverlee , Ling Liu , David Buttler, Probe, Cluster, and Discover: Focused Extraction of QA-Pagelets from the Deep Web, Proceedings of the 20th International Conference on Data Engineering, p.103, March 30-April 02, 2004
• 27: Valter Crescenzi , Giansalvatore Mecca , Paolo Merialdo, RoadRunner: Towards Automatic Data Extraction from Large Web Sites, Proceedings of the 27th International Conference on Very Large Data Bases, p.109-118, September 11-14, 2001
• 28: D. W. Embley , Y. Jiang , Y.-K. Ng, Record-boundary discovery in Web documents, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.467-478, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States