Data Cleaning Techniques by means of Entity Resolution

Open Access
On, Byung-Won
Graduate Program:
Computer Science and Engineering
Doctor of Philosophy
Document Type:
Date of Defense:
May 01, 2007
Committee Members:
  • Dongwon Lee, Committee Chair
  • C Lee Giles, Committee Member
  • Sandeep Purao, Committee Member
  • Wang Chien Lee, Committee Member
  • Piotr Berman, Committee Member
  • Reka Z Albert, Committee Member
  • Data Mining
  • Clustering Algorithms
  • Graph Algorithms
Real data are ``dirty.' Despite active research on integrity constraints enforcement and data cleaning, real data in real database applications are still dirty. To make matters worse, both diverse formats/usages of modern data and demands for large-scale data handling make this problem even harder. In particular, to surmount the challenges for which conventional solutions against this problem no longer work, we focus on one type of problems known as the Entity Resolution (ER) -- the process of identifying and merging duplicate entities determined to represent the same real-world object. Despite the fact that the problem has been studied extensively, it is still not trivial to de-duplicate complex entities among a large number of candidates. In this thesis, we have studied three specialized types of ER problems: (1) the Split Entity Resolution (SER) problem, in which instances of the same entity type mistakenly appear under different name variants; (2) the Mixed Entity Resolution (MER) problem, in which instances of different entities appear together for their homonymous names; and (3) the Grouped Entity Resolution (GER) problem, in which instances of entities do not carry any name or description by which ER techniques can be utilized, and thus the contents of entities are exploited as a group of elements. For each type of problems, we have developed a novel scalable solution. Especially, for the GER problem, we have developed two graph theoretic algorithms - one based on Quasi-Clique and the other based on Bipartite Matching, and experimentally validated the superiority of the proposed solutions.