Establishing value mappings using statistical models and user feedback

ABSTRACT

In this paper, we present a "value mapping" algorithm that does not rely on syntactic similarity or semantic interpretation of the values. The algorithm first constructs a statistical model (e.g., co-occurrence frequency or entropy vector) that captures the unique characteristics of values and their co-occurrence. It then finds the matching values by computing the distances between the models while refining the models using user feedback through iterations. Our experimental results suggest that our approach successfully establishes value mappings even in the presence of opaque data values and thus can be a useful addition to the existing data integration techniques.

REFERENCES

• 1: R. Ananthakrishna, S. Chaudhuri, and V. Ganti. "Eliminating Fuzzy Duplicates in Data Warehouses". In VLDB, 2002.
• 2: Periklis Andritsos , Renée J. Miller , Panayiotis Tsaparas, Information-theoretic tools for mining database structure from large data sets, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007650]
• 3: Mikhail Bilenko , Raymond J. Mooney, Adaptive duplicate detection using learnable string similarity measures, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956759]
• 4: Surajit Chaudhuri , Kris Ganjam , Venkatesh Ganti , Rajeev Motwani, Robust and efficient fuzzy match for online data cleaning, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872796]
• 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: S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. Harshman. "Indexing by Latent Semantic Analysis". J. of the American Society of Information Science, 41(6):391--407, 1990.
• 7: Robin Dhamankar , Yoonkyong Lee , AnHai Doan , Alon Halevy , Pedro Domingos, iMAP: discovering complex semantic matches between database schemas, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007612]
• 8: 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
• 9: 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
• 10: A. Doan, Y. Lu, Y. Lee, and J. Han. "Object Matching for Data Integration: A Profile-Based Approach". In Workshop on Info. Integration on the Web, 2003.
• 11: I. P. Fellegi and A. B. Sunter. "A Theory for Record Linkage". J. of the American Statistical Society, 64:1183--1210, 1969.
• 12: H. Galhardas, D. Florescu, D. Shasha, and E. Simon. "An Extensible Framework for Data Cleaning". In IEEE ICDE, 2000.
• 13: L. Gravano, P. G. Ipeirotis, N. Koudas, and D. Srivastava. "Text Joins for Data Cleansing and Integration in an RDBMS". In IEEE ICDE, 2003.
• 14: Mauricio A. Hernández , Renée J. Miller , Laura M. Haas, Clio: a semi-automatic tool for schema mapping, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.607, May 21-24, 2001, Santa Barbara, California, United States
• 15: Mauricio A. Hernández , Salvatore J. Stolfo, The merge/purge problem for large databases, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.127-138, May 22-25, 1995, San Jose, California, United States
• 16: 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]
• 17: W.-S. Li and C. Clifton. "SEMINT: A Tool for Identifying Attribute Correspondences in Heterogeneous Databases using Neural Networks". VLDB J., 10(4), Dec. 2001.
• 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: Andrew McCallum , Kamal Nigam , Lyle H. Ungar, Efficient clustering of high-dimensional data sets with application to reference matching, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.169-178, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347123]
• 20: S. Melnik, H. Garcia-Molina, and E. Rahm. "Similarity Flooding: A Versatile Graph Matching Algorithm and Its Application to Schema Matching". In IEEE ICDE, 2002.
• 21: 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
• 22: Alvaro Edmundo Monge, Adaptive detection of approximately duplicate database records and the database integration approach to information discovery, University of California at San Diego, La Jolla, CA, 1998
• 23: D. S. Moore and G. P. McCabe. "Introduction to the Practice of Statistics". From Book News, Inc., 1998.
• 24: H. Pasula, B. Marthi, B. Milch, S. Russell, and I. Shpitser. "Identity Uncertainty and Citation Matching". In Advances in Neural Information Processing Systems. MIT Press, 2003.
• 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: S. Sarawagi and A. Bhamidipaty. "Interactive Deduplication using Active Learning". In ACM SIGMOD, 2002.
• 27: Claude E. Shannon , Warren Weaver, A Mathematical Theory of Communication, University of Illinois Press, Champaign, IL, 1963
• 28: W. E. Winkler. "The State of Record Linkage and Current Research Problems". Technical report, US Bureau of the Census, Apr. 1999.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.5 Heterogeneous Databases

General Terms:
Algorithms, Management

Keywords:
semantic correspondences, statistical model, user feedback, value mapping