Integrating web query results: holistic schema matching

ABSTRACT

The emergence of numerous data sources online has presented a pressing need for more automatic yet accurate data integration techniques. For the data returned from querying such sources, most works focus on how to extract the embedded structured data more accurately. However, to eventually provide an integrated access to these query results, a last but not least step is to combine the extracted data coming from different sources. A critical task is finding the correspondence of the data fields between the sources - a problem well known as schema matching. Query results are a small and biased sample set of instances obtained from sources; the obtained schema information is thus very implicit and incomplete, which often prevents existing schema matching approaches from performing effectively. In this paper, we develop a novel framework for understanding and effectively supporting schema matching on such instance-based data, especially for integrating multiple sources. We view discovering matching as constructing a more complete domain schema that best describes the input data. With this conceptual view, we can leverage various data instances and observed regularities seamlessly with holistic, multiple-source schema matching to achieve more accurate matching results. Our experiments show that our framework consistently outperforms baseline pairwise and clustering-based approaches (raising F-measure from 50-89% to 89-94%) and works uniformly well for the surveyed domains.

REFERENCES

• 1: Arvind Arasu , Hector Garcia-Molina , Stanford University, Extracting structured data from Web pages, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872799]
• 2: L. Arlotta, V. Crescenzi, G. Mecca, and P. Merialdo. Automatic annotation of data extracted from large web sites. In Proc. of WebDB, 2003.
• 3: Alexander Bilke , Felix Naumann, Schema Matching Using Duplicates, Proceedings of the 21st International Conference on Data Engineering, p.69-80, April 05-08, 2005 [doi>10.1109/ICDE.2005.126]
• 4: Shui-Lung Chuang , Kevin Chen-Chuan Chang , ChengXiang Zhai, Context-aware wrapping: synchronized data extraction, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 5: 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
• 6: Hong-Hai Do , Erhard Rahm, COMA: a system for flexible combination of schema matching approaches, Proceedings of the 28th international conference on Very Large Data Bases, p.610-621, August 20-23, 2002, Hong Kong, China
• 7: Hong Hai Do , Sergey Melnik , Erhard Rahm, Comparison of Schema Matching Evaluations, Revised Papers from the NODe 2002 Web and Database-Related Workshops on Web, Web-Services, and Database Systems, p.221-237, October 07-10, 2002
• 8: AnHai Doan , Pedro Domingos , Alon Y. Halevy, Reconciling schemas of disparate data sources: a machine-learning approach, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.509-520, May 21-24, 2001, Santa Barbara, California, United States
• 9: Eduard Dragut , Wensheng Wu , Prasad Sistla , Clement Yu , Weiyi Meng, Merging Source Query Interfaces onWeb Databases, Proceedings of the 22nd International Conference on Data Engineering, p.46, April 03-07, 2006 [doi>10.1109/ICDE.2006.91]
• 10: 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]
• 11: Jaewoo Kang , Jeffrey F. Naughton, On schema matching with opaque column names and data values, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872783]
• 12: Wen-Syan Li , Chris Clifton, SEMINT: a tool for identifying attribute correspondences in heterogeneous databases using neural networks, Data & Knowledge Engineering, v.33 n.1, p.49-84, April 2000 [doi>10.1016/S0169-023X(99)00044-0]
• 13: Jayant Madhavan , Philip A. Bernstein , AnHai Doan , Alon Halevy, Corpus-Based Schema Matching, Proceedings of the 21st International Conference on Data Engineering, p.57-68, April 05-08, 2005 [doi>10.1109/ICDE.2005.39]
• 14: Jayant Madhavan , Philip A. Bernstein , Erhard Rahm, Generic Schema Matching with Cupid, Proceedings of the 27th International Conference on Very Large Data Bases, p.49-58, September 11-14, 2001
• 15: Similarity Flooding: A Versatile Graph Matching Algorithm and Its Application to Schema Matching, Proceedings of the 18th International Conference on Data Engineering, p.117, February 26-March 01, 2002
• 16: Tova Milo , Sagit Zohar, Using Schema Matching to Simplify Heterogeneous Data Translation, Proceedings of the 24rd International Conference on Very Large Data Bases, p.122-133, August 24-27, 1998
• 17: L. R. Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. Proceedings of the IEEE, 77:257---286, 1989.
• 18: Erhard Rahm , Philip A. Bernstein, A survey of approaches to automatic schema matching, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.334-350, December 2001 [doi>10.1007/s007780100057]
• 19: Jiying Wang , Ji-Rong Wen , Fred Lochovsky , Wei-Ying Ma, Instance-based schema matching for web databases by domain-specific query probing, Proceedings of the Thirtieth international conference on Very large data bases, p.408-419, August 31-September 03, 2004, Toronto, Canada
• 20: Wensheng Wu , Clement Yu , AnHai Doan , Weiyi Meng, An interactive clustering-based approach to integrating source query interfaces on the deep Web, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007582]
• 21: Zhen Zhang , Bin He , Kevin Chen-Chuan Chang, Light-weight domain-based form assistant: querying web databases on the fly, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
data integration, holistic schema matching, web query results