A grammar-based entity representation framework for data cleaning

ABSTRACT

Fundamental to data cleaning is the need to account for multiple data representations. We propose a formal framework that can be used to reason about and manipulate data representations. The framework is declarative and combines elements of a generative grammar with database querying. It also incorporates actions in the spirit of programming language compilers. This framework has multiple applications such as parsing and data normalization. Data normalization is interesting in its own right in preparing data for analysis as well as in pre-processing data for further cleansing. We empirically study the utility of the framework over several real-world data cleaning scenarios and find that with the right normalization, often the need for further cleansing is minimized.

REFERENCES

• 1: Alfred V. Aho , Monica S. Lam , Ravi Sethi , Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools (2nd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
• 2: Arvind Arasu , Surajit Chaudhuri , Raghav Kaushik, Transformation-based Framework for Record Matching, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.40-49, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497412]
• 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: Vinayak Borkar , Kaustubh Deshmukh , Sunita Sarawagi, Automatic segmentation of text into structured records, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.175-186, May 21-24, 2001, Santa Barbara, California, United States
• 5: Kaushik Chakrabarti , Surajit Chaudhuri , Venkatesh Ganti , Dong Xin, An efficient filter for approximate membership checking, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376697]
• 6: Amit Chandel , Oktie Hassanzadeh , Nick Koudas , Mohammad Sadoghi , Divesh Srivastava, Benchmarking declarative approximate selection predicates, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247521]
• 7: 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]
• 8: 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]
• 9: William W. Cohen , Sunita Sarawagi, Exploiting dictionaries in named entity extraction: combining semi-Markov extraction processes and data integration methods, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014065]
• 10: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 11: ]]S. Cucerzan. Large scale named entity disambiguation based on wikipedia data. In EMNLP-CoNLL Joint Conf., pages 708--716, June 2007.
• 12: ]]DBLP. http://www.informatik.uni-trier.de/~ley/db/index.html.
• 13: Ahmed K. Elmagarmid , Panagiotis G. Ipeirotis , Vassilios S. Verykios, Duplicate Record Detection: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.19 n.1, p.1-16, January 2007 [doi>10.1109/TKDE.2007.9]
• 14: ]]Freebase. http://www.freebase.com/.
• 15: ]]A. Y. Halevy, M. J. Franklin, and D. Maier. Dataspaces: A new abstraction for information management. In DASFAA, pages 1--2, Apr. 2006.
• 16: Nick Koudas , Sunita Sarawagi , Divesh Srivastava, Record linkage: similarity measures and algorithms, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142599]
• 17: ]]J. Madhavan, S. Cohen, X. L. Dong, et al. Web-scale data integration: You can afford to pay as you go. In CIDR, pages 342--350, Jan. 2007.
• 18: ]]RIDDLE: Repository of information on duplicate detection, record linkage, and identity uncertainty. http://www.cs.utexas.edu/users/ml/riddle/.
• 19: ]]E. A. Rundensteiner. Special issue editor. IEEE Data Engineering Bulletin, 22(1), 1999.
• 20: ]]S. Sarawagi and W. W. Cohen. Semi-markov conditional random fields for information extraction. In NIPS, Dec. 2004.
• 21: Fabian M. Suchanek , Gjergji Kasneci , Gerhard Weikum, YAGO: A Large Ontology from Wikipedia and WordNet, Web Semantics: Science, Services and Agents on the World Wide Web, v.6 n.3, p.203-217, September, 2008 [doi>10.1016/j.websem.2008.06.001]
• 22: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 23: ]]U.S. census bureau. http://www.census.gov/genealogy/names/.
• 24: Paul Viola , Mukund Narasimhan, Learning to extract information from semi-structured text using a discriminative context free grammar, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076091]
• 25: ]]Wiktionary. http://www.wiktionary.org/.
• 26: Fei Wu , Daniel S. Weld, Automatically refining the wikipedia infobox ontology, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367583]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms, Design, Experimentation

Keywords:
data cleaning, deduplication, entity resolution