dataesr/scientific-paragraphs-categorization huggingface dataset:
As described above the creation of the phasefield model is accomplished directly with lbmpy, which forms a convenient prototyping environment since all equations can be stated as symbolic representations. lbmpy does not only produce the compute kernels, but can generate also the pack and unpack information as it is needed for the MPI communication routines. This is again completely automatic, since the symbolic representations expose all field accesses and thus the data that must be kept in the ghost layers. A ghost layer is a single layer of cells around each subdomain used for the communication between neighboring subdomains. Furthermore, also the routines are generated, to implement the boundary conditions. The complete generation process can be configured to produce C-Code or code for GPUs with CUDA and alternatively OpenCL.
These kernels can be directly called as python functions to be run in an interactive environment or combined with the HPC framework WALBERLA. To demonstrate the usage of lbmpy we show how the update rule for the hydrodynamic distribution functions g i is realized. Following  Mitchell et al. (2018b)  equation (  10 ), should be formulated as g(x + e i ∆t, t + ∆t) = M -1 [m -(m eq + 0. 5F m ) S + F m , (25) where m = M g and the forcing is given by F m = ρ -1 0, F x , F y , F z , 0,. This formulation drastically reduces the number for FLOPs needed in each cell compared to (10) where the force is applied in the particle distribution function (PDF) space. Note here that this kind of modification can be implemented in lbmpy in a very simple way. After creating the LB method it contains the moment matrix M , the relaxation matrix S and the moment equilibrium values m eq i.
Conclusion In this work we have shown an implementation of the conservative ACM based on metaprogramming. With this technique we can generate highly efficient C, OpenCL and CUDA kernels which can be integrated in other frameworks for simulating large scale scenarios. For this work we have used the WALBERLA framework to integrate our code. We have measured the efficiency our implementation on single GPUs. Excellent performance results compared to the roofline model could be shown for a Tesla V100 and a Tesla P100 where we could achieve about 85 % of the theoretical peak performance for both architectures. Additionally, we have shown that our code not only performs very well for one configuration but keeps its excellent efficiency even for different stencils and different methods to solve the LBEs.
It is even possible to directly generate 2D cases for testing which also show very good performance results. Through separating our iteration region in an inner and an outer part we could enable communication hiding, relevant for multi-GPU simulations with MPI. With this technique we are able to run large scale simulations with almost perfect scalability. To show this we have run a weak scaling benchmark on the Piz Daint supercomputer on 2048 GPU nodes. We could show that our implementation has a parallel efficiency of almost 98 %. To validate our code form a physical point of view we have measured the terminal shape of single rising air bubble in water under various Eötvös numbers and Reynolds numbers. We could show good agreement with the literature data regarding the terminal shape and the drag coefficient of rising bubbles.
It is desired that one be able to enter the definition formulas and computational steps to be performed (the input, shown in what follows preceded by a prompt >) in a way that resembles as closely as possible their paper and pencil representation, and that the results (the output, computed by the CAS) use easy-to-read, textbook mathematical-physics notation. The Maple Physics package implements such dedicated typesetting. In what follows, within text and in the output, noncommutative objects are displayed using a different color, e. g. H, vectors and tensor indices are displayed in the standard way, as in → L and L q , and commutators are displayed with a minus subscript, e. g. [H, L q ] -. Although the Maple system optionally provides dedicated typesetting also for the input, we preferred to keep visible the Maple input syntax, allowing for comparison with paper and pencil notation and to transmit a more accurate picture of what it is like to work on a real problem using CAS.
A high utility itemset mining problem is the question of recognizing a set of items that have utility values greater than a given user utility threshold. This generalization of the classical problem of frequent itemset mining is a useful and well-known task in data analysis and data mining, since it is used in a wide range of real applications. In this paper, we first propose to use symbolic Artificial Intelligence for computing the set of all closed high utility itemsets from transaction databases. Our approach is based on reduction to enumeration problems of propositional satisfiability. Then, we enhance the efficiency of our SAT-based approach using the weighted clique cover problem. After that, in order to improve scalability, a decomposition technique is applied to derive smaller and independent sub-problems in order to capture all the closed high utility itemsets.
Introduction Data mining is a multi-disciplinary field that employs machine learning, statics and symbolic Artificial Intelligence in order to find novel valid relationships among data. A pivotal task in knowledge discovery process concerns pattern extraction w. r. t. various proprieties such as novelty, usefulness and understandability. The problem of selecting a set of itemsets from the original data has recently gained a lot of attention in the two last decades. Mining High Utility itemsets (HUIM, for short) as one of the major keystone in the discovery of patterns generalizes the problem of frequent itemsets (FIM), since traditional frequent patterns cannot fulfill the requirement of finding the most valuable information that contribute to the major part of the total profits in the retail databases.
HUIM considers item quantities and weights and refers to recognize the set of items that appear together in a given transaction database and having a high importance to the user, measured by a utility function. The utility means the importance/profitability of items to users. Indeed, the utility of items in a transaction depends on the importance of different items, which is called external utility, and the importance of the items in the transaction, called internal utility. Then, the utility of an itemset is defined as the multiplication of the external and the internal utilities. An itemset is called a high utility itemset if its utility is no less than a user The purchase quantity of an item  in a transaction      (𝑎)  The unit profit of an item  (,   ) The utility of an item  in a transaction   (,   ) The utility of an itemset  in a transaction     (𝑋)  The utility of an itemset  in the whole database   (  ) The sum of the utilities of items in a transaction    A predefined minimum high utility threshold    (, ) The transaction-weighted utility of an itemset  in the database  HUI A High Utility Itemset CHUI A Closed High Utility Itemset Prop A set of propositional variables Form A set of propositional formulas  A Boolean interpretation specified threshold value; otherwise, the itemset is called a low utility itemset.
Mining high utility itemsets from transaction databases is an important task and it has a wide range of applications, including website click stream analysis, business promotion in chain hypermarkets, online e-commerce management, mobile commerce environment planning, and biomedical applications  [1] [2] [3]. Generally speaking, existing approaches, usually called specialized approaches, (see related work section) are designed to find particular kinds of itemsets from transaction databases with utilities. In that sense, new additional constraints (i. e. , user preference) cannot be easily integrated in the original algorithm, and they require a re-implementation of the whole application. In recent years, several constraint-based languages for modeling and solving data mining problems have been designed where the data mining task is modeled as a constraint network or a propositional formula whose models correspond to the patterns of interest.
These methods, usually coined as declarative approaches, have then found applications in diverse data mining tasks ranging from frequent itemset mining  [4]  and its concise representations  [5, 6] , sequences  [7]  and association rules  [8, 9]. Clearly, this tight connection between constraint-based languages and pattern discovery allows data mining problems to benefit from several powerful symbolic Artificial Intelligence solving techniques. More interestingly, propositional satisfiability based approaches have gained a considerable audience with the advent of a new generation of solvers able to handle large instances encoding data mining problems  [4, 10, 11]. A bottleneck of the most declarative methods is the encoding size which affect the algorithm efficiency. Thus, the performance of such approaches decreases when the database size grows or the threshold takes low values.
To improve the efficiency of declarative mining algorithms, a decomposition technique could be applied in order to divide the original mining problem to smaller and independent sub-problems. In this paper, we introduce SATCHUIM, a new algorithm that makes an original use of symbolic Artificial Intelligence technique, i. e. , propositional satisfiability, for efficiently enumerating all closed high utility itemsets embedded in a transaction database. Technically, the main contribution consists in developing a method based on propositional satisfiability to model and solve the task of mining a concise and complete representation of HUIs in terms of constraints. Furthermore, we enhance the efficiency of our proposed approach using the weighted clique cover problem. After that, to cope with the scalability issue, which is one of the most important challenge of declarative frameworks, we use a decomposition technique that allows to derive smaller and independent enumeration sub-problems.
The paper is organized as follows. The next section presents a background on which our work relies. Then, we present the state-of-the-art of high utility itemset mining problem in Section 3. Section 4 is devoted to our novel SAT-based framework as well as its decomposition-based version for discovering closed itemsets with highest utilities. Section 5 discusses the results of our experimental evaluation on different real-world datasets to show the efficiency and usefulness of our approach. Finally, we conclude our work in Section 6 with some further perspectives.
High utility itemset mining problem Let  denote a universe of distinct items (or symbols) that occur in the database. A transaction database  = { 1 ,  2 , … ,   } is a set of  transactions or records such that each transaction   is a set of items, i. e. ,   ⊆ , and   has a unique identifier  called its transaction identifier (TID, for short). Each item  ∈  is associated with a positive number   (), called its external utility (e. g. , unit profit). For each transaction   , a positive number   (,   ) is called the internal utility of the item  ∈   (e. g. , purchase quantity). Example 1. Let us consider a transaction database  containing four transactions, given in Table  2 , which will serve as a running example throughout the paper. Each line in Table  2  represents a transaction, where each letter represents an item that is associated to a purchase quantity (i.
e. , internal utility). For instance, the transaction  2 contains items , , and  with an internal utility of 2, 6 and 2, respectively. In addition, Table  3  indicates the external utility of each of these items. In fact, external utility of , , and  are respectively 4, 1 and 3. Then, the utility of the item  in  2 is (,  2 ) = 4 × 2 = 8. Finally, the utility of the itemset {, } in  2 is ({},  2 ) = (,  2 ) + (,  2 ) = 4 × 2 + 1 × 6 = 14. Now, the utility of an itemset  in a transaction database  is defined as the sum of the itemset utilities in all the transactions of  where  appears. More formally: Definition 3 (Utility of an Itemset in a Database). Let  be a transaction database. The utility of an itemset  in , denoted by (), is defined as: Problem Definition. Given a transaction database  and a user-specified minimum utility threshold , the goal of mining (closed) high utility itemsets problem is to find the set of all (closed) itemsets in  with a utility no less than , i.
e. , 𝑢(𝑋) = ∑ (𝑖,𝑇 𝑖 )∈𝐷 | 𝑋⊆𝑇 𝑖 𝑢(𝑋, 𝑇 𝑖 ) (2) 𝐻𝑈 𝐼 = {𝑋 ∶ 𝑢(𝑋) | 𝑋 ⊆ 𝛺, 𝑢(𝑋) ≥ 𝜃} (3) That is, computing closed high utility itemsets is equivalent to finding the itemsets that cover the largest part of the database utility. Example 3. Let us consider again the transaction database given in Example 1. Given a minimum utility threshold  = 20, then the high-utility itemsets with their utility in the database are {, , } ∶ 28, {, , } ∶ 28, {, , , } ∶ 40. In this example, the itemsets {, }, {, }, {, }, {, , }, {, , }, {, , , } and {, , , , } are closed HUIs, with utility values 23, 25, 22, 24, 28, 20 and 24, respectively. Definition 5 (Transaction Utility). Given a transaction database , then the transaction utility of a transaction   in , denoted by   (  ), is the sum of the utility of all items in   , i.
𝑇 𝑈 (𝑇 𝑖 ) = ∑ 𝑎∈𝑇 𝑖 𝑢(𝑎, 𝑇 𝑖 ) (4) Definition 6 (Transaction Weighted Utilization). The transaction weighted utilization of an itemset  in a transaction database , denoted by    (, ), is defined as the sum of the transaction utility of transactions containing , i. e. , 𝑇 𝑊 𝑈 (𝑋) = ∑ (𝑖,𝑇 𝑖 )∈𝐷 | 𝑋⊆𝑇 𝑖 𝑇 𝑈 (𝑇 𝑖 ) (5) Here, the difference between    (, ) and () is that for    (, ), we sum the utilities of the whole transactions containing , while () computes only the utilities of  in the transactions where  appears. We conclude this subsection by pointing out that the transaction weighted utilization measure has three important properties that are used to prune the search space. Overestimation. The TWU of an itemset  is always higher than or equal to the utility of , i. e. ,    (, ) ≥ (). Anti-monotonicity.
e. , whether there exists a model of all clauses in a CNF form. This is known as NP-Complete problem. Interestingly, state-of-the-art SAT solvers have been shown of practical use in solving real-world instances encoding industrial problems up to million of variables and clauses. SAT solving has been exploited in various fields, including planning, bio-informatics, cryptography and more recently data mining and relational databases. In most of these applications, we are mainly interested in identifying the satisfiability of a CNF formula, or in computing an optimal solution in Maximum Satisfiability (Max-SAT, for short). However, in data mining we mainly deal with the computation of all the models of a CNF formula.
Related work Several proposals have been studied to enumerate HUIs (see  [13] [14] [15]  for a survey on the field). A popular approach to solve this problem is to discover the set of high utility itemsets in two phases. This approach commonly adopts the Transaction-Weighted-Downward Closure model to prune the search space. It first generates a set of candidate high-utility itemsets by overestimating their utility in phase 1. Then, in phase 2, it performs an extra database scan to calculate the exact utility of candidates and filter out low-utility itemsets. The two phases based approach is adopted by Two-Phase  [16] , IHUP  [17]  and Up-Growth  [18]  algorithms. While two-phases based approaches are well studied, they remain inefficient because they not only generate too many candidates in the first phase, but they also need to scan, in phase 2, multiple times the database, which can be computationally expensive.
To address these issues, numerous studies have been conducted in order to develop efficient methods for mining high utility itemsets directly using a single phase (called one phase algorithms). To prune the search space, one phase approaches rely on the concept of remaining utility. Among these algorithms HUI-Miner  [19] , D2HUP  [20] , FHM  [21] , EFIM  [22] , mHUIMiner  [23] , and ULB  [24]. According to the comparisons in  [14]  between these various HUIM algorithms, it has been demonstrated that one phase algorithms outperform candidate generation based algorithms such as Two-Phase and Up-Growth, which are impractical for discovering HUIs from transaction databases. Furthermore, the authors in  [14]  demonstrated that the most efficient algorithms (in terms of memory consumption) are EFIM and D2HUP (in running time).
The newest HUIM algorithms, mHUIMiner and ULB-Miner, typically perform between EFIM and d2HUP, but in a few cases, mHUIMiner outperforms both. Rather than mining the entire set of HUIs, some researchers proposed more concise representations that significantly reduce the number of mined patterns (see  [13]  for clear definitions of these representations). The first algorithm to find compact representation of HUIs, called CHUD ( + High Utility Itemset Discovery), was introduced by  [25]. This method aids in resolving the issue of a large number of candidates being generated. Notice that CHUD is an extension of Eclat  [26]  and DCI-Closed  [27]  algorithms. The CHUD algorithm uses a vertical database and computes CHUIs in a depth-first search. In  [28] , the authors proposed EFIM-Closed a lossless and compact representation for high utility itemset mining that is able to provide complete set of closed high-utility itemsets.
SAT encoding of (closed) high utility itemset mining In this section, we introduce our SAT-based formulation that enables us to specify in terms of constraints the task of finding (closed) high utility itemsets over transaction databases. Our main goal is to provide an efficient way to encode and enumerate all closed high utility itemsets with SAT. Without loss of generality, we fix a transaction database  = {(1,  1 ), …, (,   )} and a minimum utility threshold. Our SAT encoding for HUIM that we will consider is based on the use of propositional variables to represent the items and the transaction identifiers in. Specifically, for each item  (resp. transaction identifier ), we associate a propositional variable, denoted as   (resp. ). These propositional variables will be used in 0∕1 linear inequalities to capture all possible itemsets and their covers.
Let us now give the formula expressing that the utility of the candidate itemset has to be larger than the specified utility threshold : 𝑚 ∑ 𝑖=1 ∑ 𝑎∈𝑇 𝑖 𝑢(𝑎, 𝑇 𝑖 ) × (𝑝 𝑎 ∧ 𝑞 𝑖 ) ⩾ 𝜃 (7) Using additional variables, Constraint (7) can be rewritten using the following two formulas: 𝑚 ∑ 𝑖=1 ∑ 𝑎∈𝑇 𝑖 𝑢(𝑎, 𝑇 𝑖 ) × 𝑟 𝑎𝑖 ⩾ 𝜃 (8) 𝑚 ⋀ 𝑖=1 ⋀ 𝑎∈𝑇 𝑖 (𝑟 𝑎𝑖 ↔ 𝑝 𝑎 ∧ 𝑞 𝑖 ) (9) In the sequel, we use  ℎ to denote the CNF encoding that corresponds to the conjunction of Eqs. (  6 ),  (8) , and (9). Proposition 1. Given a transaction database  = {(1,  1 ), …, (,   )} and a minimum utility threshold. Then, the CNF formula  ℎ models the problem of mining high utility itemsets from. Proof. It is straightforward to see that there exists a mapping between the set of models of  ℎ and the high utility itemsets. Example 5.
We consider the transaction database given in Example 1. Then, the formula that encodes the problem of enumerating all high utility itemsets in  with  = 20 can be written as follows: ¬𝑞 1 ↔ (𝑝 𝑏 ∨ 𝑝 𝑒 ) ¬𝑞 2 ↔ (𝑝 𝑏 ∨ 𝑝 𝑑 ) ¬𝑞 3 ↔ ⊥ ¬𝑞 4 ↔ 𝑝 𝑎 𝑟 𝑎1 ↔ 𝑝 𝑎 ∧ 𝑞 1 𝑟 𝑐1 ↔ 𝑝 𝑐 ∧ 𝑞 1 𝑟 𝑑1 ↔ 𝑝 𝑑 ∧ 𝑞 1 𝑟 𝑎2 ↔ 𝑝 𝑎 ∧ 𝑞 2 𝑟 𝑐2 ↔ 𝑝 𝑐 ∧ 𝑞 2 𝑟 𝑒2 ↔ 𝑝 𝑒 ∧ 𝑞 2 𝑟 𝑎3 ↔ 𝑝 𝑎 ∧ 𝑞 3 𝑟 𝑏3 ↔ 𝑝 𝑏 ∧ 𝑞 3 𝑟 𝑐3 ↔ 𝑝 𝑐 ∧ 𝑞 3 𝑟 𝑑3 ↔ 𝑝 𝑑 ∧ 𝑞 3 𝑟 𝑒3 ↔ 𝑝 𝑒 ∧ 𝑞 3 𝑟 𝑏4 ↔ 𝑝 𝑏 ∧ 𝑞 4 𝑟 𝑐4 ↔ 𝑝 𝑐 ∧ 𝑞 4 𝑟 𝑑4 ↔ 𝑝 𝑑 ∧ 𝑞 4 𝑟 𝑒4 ↔ 𝑝 𝑒 ∧ 𝑞 4 4𝑟 𝑎1 + 𝑟 𝑐1 + 2𝑟 𝑑1 + 8𝑟 𝑎2 + 6𝑟 𝑐2 + 6𝑟 𝑒2 + 4𝑟 𝑎3 + 4𝑟 𝑏3 + 𝑟 𝑐3 + 12𝑟 𝑑3 + 3𝑟 𝑒3 + 8𝑟 𝑏4 +3𝑟 𝑐4 + 6𝑟 𝑑4 + 3𝑟 𝑒4 ≥ 20 Once the CNF formula  ℎ is constructed, we systematically use a SAT solver to enumerate all its models. Obviously, each found model of  ℎ corresponds to a high utility itemset in the original transaction database.
Pruning strategy The basic version of our algorithm performs a backtrack search similarly to the TWU measure in order to prune the search space. Now, a useful extension to perform better pruning in the search tree consists to add a new constraint to the previous  ℎ encoding. Notice that this constraint is derived from In Eq. (  8 ) using the weighted clique cover problem  [31]. Our main idea is to identify the subsets of variables   which cannot be true simultaneously. Next, we show how this new constraint can be derived in a suitable way in order to make our pruning strategy more efficient. To do this, let us first introduce a graphical representation of the original transaction database as follows. Definition 7. Let  = { 1 ,  2 , … ,   } be a transaction database. Then, the graph associated to  is an undirected graph   = ( , ) such that each item in each transaction represents a vertex in   , i.
e. ,   is the vertex associated to the item  in the transaction  with 1 ≤  ≤. In addition, an edge (  ,   ′  ) ∈  iff the transaction  contains  but not  ′. Example 6. Given the transaction database of Example 1. Then, the graph   associated to this database is depicted in Fig. 1. Definition 7 ensures that each edge of   connects two items of  that cannot belong simultaneously to the same high utility itemset. For instance, in the database of Example 1, the item  in the transaction  1 cannot appear with  in  3. Now, our aim is to partition the graph   into overlapping sets. To do this, we will use the notion of clique cover defined as follows.
Let  = { 1 ,  2 , … ,   } be a transaction database and   the graph associated to. If  = { 1 , … ,   } is a clique cover of   , then the following constraint holds : ∑ 1≤𝑖≤𝑘 𝑚𝑎𝑥 𝑣 𝑎𝑗 ∈𝐶 𝑖 𝑢(𝑎, 𝑇 𝑗 )( ⋁ 𝑣 𝑎𝑗 ∈𝐶 𝑖 𝑟 𝑎𝑗 ) ≥ 𝜃 (11) Additional variables   (1 ≤  ≤ ) can be used to simplify Constraint  (11)  in the following way: Note that the weighted clique cover problem is NP-hard and the number of solutions can be very large. Our aim here is to minimize ∑  =1   with   =    ∈  (,   ). The goal is then to obtain large cliques with maximum weight. To avoid the NP-Hardness of the related problem, we next consider a greedy approach to find a possible cover. To do this, we proceed by growing the current clique one vertex at a time by looping through the remaining adjacent vertices with high weight values in the current graph.
A decomposition-based encoding for mining CHUIs In this subsection, we present a decomposition-based paradigm that splits the original transaction database into smaller and independent subsets in order to avoid encoding the whole base. Our decomposition is motivated by the fact that encoding the whole database into propositional logic can lead to very large formulas, that is the solving can be unfeasible. In fact, given the set of items  = { 1 , … ,   } of , the set of high utility itemsets can be partitioned into  1 , … ,   where  1 is the subset of itemsets containing  1 ,  2 of those not containing  1 but  2 , and so on until   of those do not involving  1 , … ,  -1 but. From the encoding point of view, the subset   is obtained by enumerating the models of   resulting from  by propagating    to false for all 1 ≤  <  and    to true.
Formally, this yields to the next formula: 𝛷 𝑖 = 𝛷 ∧ 𝑝 𝑎 𝑖 ∧ ⋀ 1≤𝑘<𝑖 ¬𝑝 𝑎 𝑘 Intuitively,   is based on a recursive split of the formula  w. r. t. its positive and negative literals. As expressed, the formula   enforces    to be true. Consequently, the encoding can be restricted to transactions containing the item. Also, the literal    for all 1 ≤  <  assigned false allows to exclude the item   to be in the candidate itemset. Thus, this allows to avoid encoding the entire original database and without causing too large formulas as well as the associated memory problems. Clearly, the splitting of  generates a set of independent sub-formulas that encode subsets of a specific set of transactions in the original database. Example 9. The partitioning tree of the transaction database of Example 1 is depicted in Fig.