Date of Award

4-4-2017

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Information Science

First Advisor

John Talburt

Abstract

Entity resolution (ER) is an O(n2) problem where n is the number of records to be processed. The pair-wise nature of ER makes it impractical to perform on large datasets without the use of a technique called blocking. In blocking the records are separated into groups (called blocks) in such a way the records most likely to match are within the same block. The ER system only compares pairs of records within the same block, thus reducing the total number of pairs to match. Traditionally, blocking algorithms build inverted indices in memory to quickly locate potential matches. With the advent of Big Data, processing has moved to a distributed environment of multiple processors to exploit the power of parallel processing. However, by design, distributed processing environments do not have a single, shared memory space. The design science research in this dissertation describes the design, verification, and validation of three new blocking strategies to support ER processes running in the Hadoop distributed processing environment. The three blocking strategies I designed and validated are 1. Pre-Resolution Transitive Closure of Match Keys, 2. Post-Resolution Transitive Closure of Cluster Identifiers, and 3. Incremental Transitive Closure of Cluster Identifier-Match Key Pairs. The research also describes the relative efficiency of the three approaches, and identifies the strengths and weaknesses of each approach with respect to different characteristics of the input data.

Download

Share

COinS