Data Cleaning Techniques by means of Entity Resolution
Open Access
- Author:
- On, Byung-Won
- Graduate Program:
- Computer Science and Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- May 01, 2007
- Committee Members:
- Dongwon Lee, Committee Chair/Co-Chair
C Lee Giles, Committee Member
Sandeep Purao, Committee Member
Wang Chien Lee, Committee Member
Piotr Berman, Committee Member
Reka Z Albert, Committee Member - Keywords:
- Data Mining
Clustering Algorithms
Graph Algorithms - Abstract:
- 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.