Accelerated algorithm for pattern detection in logical analysis of data

Sets of "positive" and "negative" points (observations) in n-dimensional discrete space given along with their non-negative integer multiplicities are analyzed from the perspective of the Logical Analysis of Data (LAD). A set of observations satisfying upper and/or lower bounds imposed on certain components is called a positive pattern if it contains some positive observations and no negative one. The number of variables on which such restrictions are imposed is called the degree of the pattern. A total polynomial algorithm is proposed for the enumeration of all patterns of limited degree, and special efficient variants of it for the enumeration of all patterns with certain "sign" and "coverage" requirements are presented and evaluated on a publicly available collection of benchmark datasets. (c) 2005 Elsevier B.V. All rights reserved.