Abstract: A new method for online data cleaning is presented.First, each clean record in the reference table is mapped as a point in a high-dimensional metric space measured by Manhattan distance.Next, all the points in the space are partitioned by clustering and indexed with B+ tree.In this way, the search in highdimensional space can be translated into search in one-dimensional space.To find the KNN (K nearest neighbors) in reference table for each incoming record, the search method of branch and bound is employed. The top K records that best match the incoming record are then identified.Theory and experiment show that it is an effective approach for online data cleaning.

Key words: B+tree, data cleaning, branch and bound