Statistical schema matching across web query interfaces

ABSTRACT

Schema matching is a critical problem for integrating heterogeneous information sources. Traditionally, the problem of matching multiple schemas has essentially relied on finding pairwise-attribute correspondence. This paper proposes a different approach, motivated by integrating large numbers of data sources on the Internet. On this "deep Web," we observe two distinguishing characteristics that offer a new view for considering schema matching: First, as the Web scales, there are ample sources that provide structured information in the same domains (e.g., books and automobiles). Second, while sources proliferate, their aggregate schema vocabulary tends to converge at a relatively small size. Motivated by these observations, we propose a new paradigm, statistical schema matching: Unlike traditional approaches using pairwise-attribute correspondence, we take a holistic approach to match all input schemas by finding an underlying generative schema model. We propose a general statistical framework MGS for such hidden model discovery, which consists of hypothesis modeling, generation, and selection. Further, we specialize the general framework to develop Algorithm MGS_sd, targeting at synonym discovery, a canonical problem of schema matching, by designing and discovering a model that specifically captures synonym attributes. We demonstrate our approach over hundreds of real Web sources in four domains and the results show good accuracy.

REFERENCES

• 1: C. Batini , M. Lenzerini , S. B. Navathe, A comparative analysis of methodologies for database schema integration, ACM Computing Surveys (CSUR), v.18 n.4, p.323-364, Dec. 1986 [doi>10.1145/27633.27634]
• 2: M. K. Bergman. The deep web: Surfacing hidden value. Technical report, BrightPlanet LLC, Dec. 2000.
• 3: P. Bickel and K. Doksum. Mathematical Statistics: Basic Ideas and Selected Topics. Prentice Hall, 2001.
• 4: K. C.-C. Chang, B. He, C. Li, and Z. Zhang. Structured databases on the web: Observations and implications. Report UIUCDCS-R-2003-2321, Dept. of Computer Science, UIUC, Feb. 2003.
• 5: William W. Cohen, Integration of heterogeneous databases without common domains using queries based on textual similarity, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.201-212, June 01-04, 1998, Seattle, Washington, United States
• 6: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 7: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum-likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society Series B, 39:1--38, 1977.
• 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: A. Halevy, O. Etzioni, A. Doan, Z. Ives, J. Madhavan, L. McDowell, and I. Tatarinov. Crossing the structure chasm. Conf. on Innovative Database Research, 2003.
• 10: B. He, T. Tao, C. Li, and K. C.-C. Chang. Clustering structured web sources: A schema-based, model-differentiation approach. Report UIUCDCS-R-2003-2322, Dept. of Computer Science, UIUC, Feb. 2003.
• 11: 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]
• 12: C. J. Lloyd. Statistical Analysis of Categorical Data. Wiley, 1999.
• 13: 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
• 14: Shamkant B. Navathe , Suresh G. Gadgil, A Methodology for View Inegration in Logical Database Design, Proceedings of the 8th International Conference on Very Large Data Bases, p.142-164, September 08-10, 1982
• 15: Jay M. Ponte , W. Bruce Croft, A language modeling approach to information retrieval, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.275-281, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291008]
• 16: 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]
• 17: L. Seligman, A. Rosenthal, P. Lehner, and A. Smith. Data integration: Where does the time go? Bulletin of the Tech. Committee on Data Engr., 25(3), 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

General Terms:
Algorithms, Design, Experimentation, Performance