Name
Abstract | ||
|---|---|---|
In this paper, we introduce a new problem, called Top-k SAT, that consists in enumerating the Top-k models of a propositional formula. A Top-k model is defined as a model with less than k models preferred to it with respect to a preference relation. We show that Top-k SAT generalizes two well-known problems: the Partial MAX-SAT problem and the problem of computing minimal models. Moreover, we propose a general algorithm for Top-k SAT. Then, we give an application of our declarative framework in data mining, namely, the problem of mining Top-k motifs in the transaction databases and in the sequences. In the case of mining sequence data, we introduce a new mining task by considering the sequences of itemsets. Thanks to the flexibility and to the declarative aspects of our SAT-based approach, an encoding of this task is obtained by a very slight modification of mining motifs in the sequences of items. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.artint.2015.11.003 | Artificial Intelligence |
Keywords | Field | DocType |
Boolean satisfiability,Data mining,Modeling,Top-k motifs | Discrete mathematics,Preference relation,Minimal models,General algorithm,Boolean satisfiability problem,Data sequences,Mathematics,Propositional formula,Encoding (memory) | Journal |
Volume | Issue | ISSN |
244 | 1 | 0004-3702 |
Citations | PageRank | References |
1 | 0.35 | 42 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Saïd Jabbour | 1 | 175 | 12.44 |
| Lakhdar Sais | 2 | 859 | 65.57 |
| Yakoub Salhi | 3 | 137 | 22.77 |