A heuristic approach for the continuous error localization problem in data cleaning [An article from: Computers and Operations Research]

This digital document is a journal article from Computers and Operations Research, published by Elsevier in 2007. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.

Description:
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.