An interactive clustering-based approach to integrating source query interfaces on the deep Web

ABSTRACT

An increasing number of data sources now become available on the Web, but often their contents are only accessible through query interfaces. For a domain of interest, there often exist many such sources with varied coverage or querying capabilities. As an important step to the integration of these sources, we consider the integration of their query interfaces. More specifically, we focus on the crucial step of the integration: accurately matching the interfaces. While the integration of query interfaces has received more attentions recently, current approaches are not sufficiently general: (a) they all model interfaces with flat schemas; (b) most of them only consider 1:1 mappings of fields over the interfaces; (c) they all perform the integration in a blackbox-like fashion and the whole process has to be restarted from scratch if anything goes wrong; and (d) they often require laborious parameter tuning. In this paper, we propose an interactive, clustering-based approach to matching query interfaces. The hierarchical nature of interfaces is captured with ordered trees. Varied types of complex mappings of fields are examined and several approaches are proposed to effectively identify these mappings. We put the human integrator back in the loop and propose several novel approaches to the interactive learning of parameters and the resolution of uncertain mappings. Extensive experiments are conducted and results show that our approach is highly effective.

REFERENCES

• 1: IceQ project: http://hanoi.cs.uiuc.edu/iceq/.
• 2: http://metaquerier.cs.uiuc.edu/repository/.
• 3: M. Bergman. The Deep Web: Surfacing the hidden value. BrightPlanet.com, 2000.
• 4: William W. Cohen, Data integration using similarity joins and a word-based information representation language, ACM Transactions on Information Systems (TOIS), v.18 n.3, p.288-321, July 2000 [doi>10.1145/352595.352598]
• 5: L. Dice. Measures of the amount of ecologic association between species. Ecology, 26(3), 1945.
• 6: H. Do and E. Rahm. Coma - a system for flexible combination of schema matching approaches. In VLDB, 2002.
• 7: 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
• 8: C. Fellbaum, editor. WordNet: An On-Line Lexical Database and Some of its Applications. MIT Press, Cambridge, MA, 1998.
• 9: A. Halevy and J. Madhavan. Corpus-based knowledge representation. In Int. Joint Conf. on AI, 2003.
• 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: H. He, W. Meng, C. Yu, and Z. Wu. Wise-integrator: an automatic integrator of Web search interfaces for e-commerce. In VLDB, 2003.
• 12: A. Hess and N. Kushmerick. Automatically attaching semantic metadata to Web services. In IJCAI Workshop on Information Integration on the Web, 2003.
• 13: L. Kaufman and P. Rousseeuw. Finding Groups in Data: an Introduction to Cluster Analysis. John Wiley & Sons, 1990.
• 14: J. A. Larson , S. B. Navathe , R. Elmasri, A Theory of Attributed Equivalence in Databases with Application to Schema Integration, IEEE Transactions on Software Engineering, v.15 n.4, p.449-463, April 1989 [doi>10.1109/32.16605]
• 15: S. Lawrence and C. Giles. Accessibility of information on the Web. Nature, 400, 1999.
• 16: 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]
• 17: L. Lovasz, Matching Theory (North-Holland mathematics studies), Elsevier Science Ltd, 1986
• 18: 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
• 19: S. Melnik, H. Garcia-Molina, and E. Rahm. Similarity flooding: A versatile graph matching algorithm and its application to schema matching. In ICDE, 2002.
• 20: Renée J. Miller , Laura M. Haas , Mauricio A. Hernández, Schema Mapping as Query Discovery, Proceedings of the 26th International Conference on Very Large Data Bases, p.77-88, September 10-14, 2000
• 21: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 22: M. Porter. An algorithm for suffix stripping. Program, 14(3), 1980.
• 23: R. Pottinger and P. Bernstein. Merging models based on given correspondences. In VLDB, 2003.
• 24: 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
• 25: 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]
• 26: Vijayshankar Raman , Joseph M. Hellerstein, Potter's Wheel: An Interactive Data Cleaning System, Proceedings of the 27th International Conference on Very Large Data Bases, p.381-390, September 11-14, 2001
• 27: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 28: Sunita Sarawagi , Anuradha Bhamidipaty, Interactive deduplication using active learning, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775087]
• 29: Amit P. Sheth , James A. Larson, Federated database systems for managing distributed, heterogeneous, and autonomous databases, ACM Computing Surveys (CSUR), v.22 n.3, p.183-236, Sept. 1990 [doi>10.1145/96602.96604]
• 30: Sheila Tejada , Craig A. Knoblock , Steven Minton, Learning object identification rules for information integration, Information Systems, v.26 n.8, p.607-633, December 2001 [doi>10.1016/S0306-4379(01)00042-4]
• 31: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 32: Sarah Zelikovitz , Haym Hirsh, Improving Short-Text Classification using Unlabeled Data for Classification Problems, Proceedings of the Seventeenth International Conference on Machine Learning, p.1191-1198, June 29-July 02, 2000