Given a database, a language and an anti-monotone predicate (with respect to a partial order on the set of sentences of the language), the problem we are interested in is the following: ``discovering the positive border of sentences verifying the predicate against the database'', i.e. the sentences whose all specialisations do not verify the predicate.
This problem is a general task in the data mining area with many applications, such as the discovery of maximal frequent itemsets or inclusion dependencies (IND).
Many approaches have been proposed recently in the KDD community to deal with such kind of problems, among which we quote the levelwise strategy and the ``Dualize and Advance'' algorithm.
For levelwise algorithms, the exploration of sentences from most general (smallest) to most specific (largest) does not work whenever large sentences have to be discovered. The ``Dualize and Advance'' offers a nice setting to cope with such limitations. Our contribution is in this spirit: we propose an adaptive strategy whose key features are :
An implementation of this strategy has been done for IND inference. Due to the cost of each database access, it turns out to be more efficient in all configurations, even when the positive border to be discovered in not too far from the most generalized IND (the bottom).
Among other things, we are working on the adaptation of this strategy for discovering maximal frequent itemsets and we are studying the complexity issue of such kind of algorithms.