A strategy for allowing meaningful and comparable scores in approximate matching

ABSTRACT

The goal of approximate data matching is to assess whether two distinct data instances represent the same real world object. This is usually achieved through the use of a similarity function, which returns a score that defines how similar two data instances are. If this score surpasses a given threshold, both data instances are considered as representing the same real world object. The score values returned by a similarity function depend on the algorithm that implements the function and have no meaning to the user (apart from the fact that a higher similarity value means that two data instances are more similar). In this paper, we propose that instead of defining the threshold in terms of the scores returned by a similarity function, the user specifies the precision that is expected from the matching process. Precision is a well known quality measure and has a clear interpretation from the user's point of view. Our approach relies on mapping between similarity scores and precision values based on a training data set. Experimental results show the training may be executed against a representative data set, and reused for other databases from the same domain.

REFERENCES

• 1: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 2: Mikhail Bilenko , Raymond Mooney , William Cohen , Pradeep Ravikumar , Stephen Fienberg, Adaptive Name Matching in Information Integration, IEEE Intelligent Systems, v.18 n.5, p.16-23, September 2003 [doi>10.1109/MIS.2003.1234765]
• 3: Nicolas Bruno , Surajit Chaudhuri , Luis Gravano, Top-k selection queries over relational databases: Mapping strategies and performance evaluation, ACM Transactions on Database Systems (TODS), v.27 n.2, p.153-187, June 2002 [doi>10.1145/568518.568519]
• 4: Chris Buckley , Ellen M. Voorhees, Evaluating evaluation measure stability, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.33-40, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345543]
• 5: 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]
• 6: P. Christen, T. Churches, and M. Hegland. Febrl - a parallel open source data linkage system. In PAKDD 2004 (LNAI 3056), pages 638--647. Springer, 2004.
• 7: W. W. Cohen, P. Ravikumar, and S. E. Fienberg. A comparison of string distance metrics for name-matching tasks. In IJCAI-03 Workshop on Information Integration on the Web (IIWeb-03), August 9-10, 2003, Acapulco, Mexico, pages 73--78, 2003.
• 8: R. da Silva, R. K. Stasiu, V. M. Orengo, and C. A. Heuser. Measuring quality of similarity functions in approximate data matching. Journal of Informetrics, 1(1):35--46, January 2007.
• 9: Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, Proceedings of the Thirtieth international conference on Very large data bases, p.864-875, August 31-September 03, 2004, Toronto, Canada
• 10: AnHai Doan , Ying Lu , Yoonkyong Lee , Jiawei Han, Profile-Based Object Matching for Information Integration, IEEE Intelligent Systems, v.18 n.5, p.54-59, September 2003 [doi>10.1109/MIS.2003.1234770]
• 11: Carina F. Dorneles , Carlos A. Heuser , Andrei E. N. Lima , Altigran Soares da Silva , Edleno Silva de Moura, Measuring similarity between collection of values, Proceedings of the 6th annual ACM international workshop on Web information and data management, November 12-13, 2004, Washington DC, USA [doi>10.1145/1031453.1031465]
• 12: I. P. Fellegi and A. B. Sunter. A theory for record linkage. Journal of the American Statistical Society, 64:1183--1210, 1969.
• 13: Luis Gravano , Panagiotis G. Ipeirotis , Nick Koudas , Divesh Srivastava, Text joins in an RDBMS for web data integration, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775166]
• 14: Sudipto Guha , Nick Koudas , Amit Marathe , Divesh Srivastava, Merging the results of approximate match operations, Proceedings of the Thirtieth international conference on Very large data bases, p.636-647, August 31-September 03, 2004, Toronto, Canada
• 15: Sudipto Guha , Nick Koudas , Divesh Srivastava , Xiaohui Yu, Reasoning About Approximate Match Query Results, Proceedings of the 22nd International Conference on Data Engineering, p.8, April 03-07, 2006 [doi>10.1109/ICDE.2006.128]
• 16: Nick Koudas , Amit Marathe , Divesh Srivastava, Flexible string matching against large databases in practice, Proceedings of the Thirtieth international conference on Very large data bases, p.1078-1086, August 31-September 03, 2004, Toronto, Canada
• 17: L. Lee. On the effectiveness of the skew divergence of statistical language analysis. Artificial Intelligence and Statistics, pages 65--72, 2001.
• 18: Amihai Motro, VAGUE: a user interface to relational databases that permits vague queries, ACM Transactions on Information Systems (TOIS), v.6 n.3, p.187-214, July 1988 [doi>10.1145/45945.48027]
• 19: Eric Sven Ristad , Peter N. Yianilos, Learning String-Edit Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.5, p.522-532, May 1998 [doi>10.1109/34.682181]
• 20: SecondString. Carnegie Mellon University. Project Page, http://secondstring.sourceforge.net/.
• 21: R. K. Stasiu, C. A. Heuser, and R. Silva. Estimating recall and precision for vague queries in databases. In CAISE 2005, Lecture Notes in Computer Science, pages 187--200. Springer Verlag, 2005.
• 22: 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]

INDEX TERMS

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

General Terms:
Experimentation, Measurement

Keywords:
data cleaning, data integration, similarity querying