Pattern sampling has emerged as a promising approach for information discovery in large databases, allowing analysts to focus on a manageable subset of patterns. In this approach, patterns are randomly drawn based on an interestingness measure, such as frequency or hyper-volume. This paper presents the first sampling approach designed to handle interval patterns in numerical databases. This approach, named Fips , samples interval patterns proportionally to their frequency. It uses a multi-step sampling procedure and addresses a key challenge in numerical data: accurately determining the number of interval patterns that cover each object. We extend this work with HFips , which samples interval patterns proportionally to both their frequency and hyper-volume. These methods efficiently tackle the well-known long-tail phenomenon in pattern sampling. We formally prove that Fips and HFips sample interval patterns in proportion to their frequency and the product of hyper-volume and frequency, respectively. Through experiments on several databases, we demonstrate the quality of the obtained patterns and their robustness against the long-tail phenomenon.

The pioneering work of Belohlavek et al. established a compelling connection between Boolean matrix factorization (BMF) and formal concept analysis (FCA), demonstrating that formal concepts serve as optimal factors for decomposing binary matrices. However, identifying the size-optimal decomposition remains an NP-hard problem, posing significant computational challenges. In this paper, we present a novel reformulation of the Boolean rank computation problem using hypergraph theory. Specifically, we show that the Boolean rank of a matrix corresponds to the size of the minimum transversal of the hypergraph constructed from the intervals of its formal concepts. This reformulation provides a theoretical foundation for understanding the structure of optimal factorizations and offers a new perspective on the problem. To validate our approach, we conducted an extensive experimental study to evaluate the characteristics of the solutions computed by our algorithm. The results demonstrated that our method not only achieved optimal factorizations but also exhibited favorable properties in terms of stability and separation.

Graphical models factorize a global probability distribution/energy function as the product/ sum of local functions. A major inference task, known as MAP in Markov Random Fields and MPE in Bayesian Networks, is to find a global assignment of all the variables with maximum a posteriori probability/minimum energy. A usual distinction on MAP solving methods is complete/incomplete, i.e. the ability to prove optimality or not. Most complete methods rely on tree search, while incomplete methods rely on local search. Among them, we study Variable Neighborhood Search (VNS) for graphical models. In this paper, we propose an iterative approach above VNS that uses (partial) tree search inside its local neighborhood exploration. The proposed approach performs several neighborhood explorations of increasing search complexity, by controlling two parameters, the discrepancy limit and the neighborhood size. Thus, optimality of the obtained solutions can be proven when the neighborhood size is maximal and with unbounded tree search. We further propose a parallel version of our method improving its anytime behavior on difficult instances coming from a large graphical model benchmark. Last we experiment on the challenging minimum energy problem found in Computational Protein Design, showing the practical benefit of our parallel version. A solver is available at https://github.com/toulbar2/toulbar2.