Algorithms for Error Localization of Discrete Data

摘要

A self-contained derivation and evaluation of the three principal algorithms for error localization of discrete data are provided: (1) generation of a sufficient set of edits by single-sweep with fathoming (suggested by the original work by Fellegi and Holt), and (2) sequential row generation (developed by Garfinkel), and (3) modifications of the Chernikova algorithm (suggested by work of Rubin and Sande). The first two approaches can be characterized as Boolean-based, whereas the last is a nonpivoting extremal ray search. The background to the Boolean approaches to data editing is provided, as are Burger's results on extremal rays, Chernikova's original algorithm, and Rubin's modifications. For selected results, new elementary proofs are given in the appendix. For the Chernikova algorithm, novel use is made of the problem structure of localization to minimize the undesirable tendency to generate excessively large matrices. (ERA citation 09:037021)