A heuristic approach for the continuous error localization problem in data cleaning

The Error Localization Problem concerns finding the minimum number of fields in a record such that by modifying the values in these fields the new record satisfies a given set of rules. This problem is of great interest to statistical agencies in as far as cleaning microdata is concerned. It has been shown to be NP-hard, and exact methods in literature only succeed in solving small instances. This article presents a new heuristic algorithm based on a descending search approach to obtain near-optimal solutions. Some procedures of this descending search make use of Farkas' Lemma in Linear Programming to drastically reduce the search space in one of the proposed neighborhoods. Computational experience on randomly generated instances shows that the approach can deal with instances of up to 1000 fields and 400 edits.