This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Adomavicius, G. Articles by Tuzhilin, A. Search for Related Content

Validation Sequence Optimization: A Theoretical Approach

Department of Information and Decision Sciences, Carlson School of Management, University of Minnesota, 321 19th Avenue South, Minneapolis, Minnesota 55455, USA
Department of Information, Operations, and Management Sciences, Stern School of Business, New York University, 44 West Fourth Street, New York, New York 10012, USA
gedas{at}umn.edu
atuzhili{at}stern.nyu.edu

The need to validate large amounts of data with the help of the domain expert arises naturally in many data-intensive applications, including data mining, data stream, and database-related applications. This paper presents a general validation approach that generalizes different expert-driven validation methods developed for specialized validation problems. In particular, we model the validation process as a sequence of validation operators, explore various properties of such sequences, and present theoretical results that provide for better understanding of the validation process. We also address the problem of selecting the best validation sequence among the class of equivalent sequence permutations. We demonstrate that this optimization problem is NP-hard and present two heuristic algorithms for improving validation sequences.

Key words: validation; validation operators; validation sequences; sequence optimization; computational complexity; heuristic algorithms; dynamic programming; data mining
History: received June 2003; revised October 2004; accepted May 2005.