Zhi Tao

Brice Le Borgne

Tayeb Mohammed-Brahim

Emmanuel Jacques

Maxime Harnois

Spreading and Drying Impact on Printed Pattern Accuracy Due to Phase Separation of a Colloidal Ink

Keywords: Inkjet Printing, Printed Patterns Accuracy, Colloidal Ink, Phase Separation, Ink Drying

Drop-on-demand inkjet printing relies on the dispensing and precise positioning of very small amount of liquid on substrate before its transformation to a solid. Consequently, many steps are involved during inkjet printing process that must be understood to fabricate accurate patterns. In this work, multicomponent colloidal mixture spreading and drying is investigated. A systematic study has been performed to explain the impact of the jetting frequency, the drop spacing and the substrate exposure to UV ozone on a colloidal silver ink behavior. It is demonstrated that phase separation between stabilizing agent and colloids can occur during the spreading step. This phenomenon is described and appears to be related to the colloidal nature of the ink. It is shown that it can have a negative impact on patterns accuracy and several routes are given to overcome these issues.

Introduction

Additive Manufacturing (AM) has gained a growing interest throughout the past decades in new application fields such as optoelectronics, [1][2][3][4] ceramics, [5,6] biotechnology, [6,7] organic light emitting devices, [6,8] field effect transistors, [6,9,10,11] solar cells, [6,12] , flexible and stretchable interconnects. [13,14] It is now well-established that AM technology such as inkjet printing, provides a breakthrough compared to the existent subtractive technologies. [6,15,16] One of the inkjet printing techniques, called drop-on-demand (DoD) printing, relies on the coalescence of adjacent droplets that are expelled from nozzles onto a substrate. [17,18,19] Picoliters droplets volume are now easily A c c e p t e d m a n u s c r i p t printed using commercial printers and many functional inks are on the shelves. [9,20] Indeed, many materials such as nano-objects, [9,21,22,23] polymers, [24,25,26] organic/inorganic semiconductors [27,28] have been solubilized in order to design conductive, insulating or semi-conductive inks, respectively, leading to active or passive devices fabrication. [29] Inkjet printing process is composed of three main steps: i) droplet generation, ii) droplet spreading onto an arbitrary substrate and iii) droplet drying. Each step have to be fully understood in order to fabricate accurate patterns. [9] Consequently, literature is replete of work dealing with each step optimization. Concerning droplet generation, recent works have demonstrated the exploitation of a jettable window (i.e., using Ca-We space) to adjust the rheology of nanoparticle ink [20] or polymeric ink [13] to allow the design of a jettable ink. Using such methodology, nozzle clogging, long-lived filament, and satellite droplets can be suppressed improving pattern accuracy. [30,31,32] However, the patterns generation behavior remains complex to understand because many experimental parameters play a crucial role during ink spreading and drying, due to its interaction with the substrate. For instance, lines can show uniform, bulged, scalloped, stacked or separated patterns as function of jetting frequency and drop spacing. [33,34] After the drying step, droplets often show non-uniform profile that is frequently attributed to the so-called coffee stain effect, firstly described by Deegan. [35] Moreover, several works proposed strategies to suppress such undesirable behavior. [9,36,37] Consequently, patterns profile can be optimized from smooth to periodically wave-shaped film depending on application requirements. [9,36,38] On the one hand, new inks designs are more and more complex and multicomponent mixtures are usually required to obtain jettable inks fitting desired properties (e.g., high conductivity for colloidal ink). [39] On the other hand, literature dealing with multicomponent mixture reports more complex droplets drying behavior than in the work of Deegan. [40,41,42] Indeed, these works that mainly dealt with isolated drop-casted microliters droplets, have shown the presence of phase separation during spreading and drying. In our work, this behavior has been verified on picoliters printed droplets as function of substrate wettability. Moreover in the second part of this work, ink phase separation impact on patterns formation such as lines or squares is studied. Indeed, in the field of printed electronics, lines or squares are required to fabricate interconnects or electrodes for instance.

A c c e p t e d m a n u s c r i p t

Results and discussion

A commercial colloidal based silver ink (ANP 40LT15C) has been used as received. Note that, this ink is frequently used for numerous printed electronics applications. Its chemical composition has been kept constant for all the study. The wetting behavior of substrates has been controlled using UV-ozone treatment. Droplets of silver based ink have been printed on 400 nm thick polymeric film (epoxy photoresist: Su8 2002 Microchem) using spin coating technique. Su8 films offer high chemical resistance and structural stability. [43] Moreover, it allows the fabrication of electronic devices. [44] Jetting parameters have been optimized to respect the jetting criteria (e.g., no satellite droplets…) described in experimental section. The inkjet printing parameters such as: velocity, firing voltage, substrate temperature have been kept constant and equal 3m.s -1 , 65V and 50°C, respectively.

Jetting behavior of silver ink is shown in supplementary video S1. This crucial step is prerequisite in order to study the accuracy of the printed pattern.

a. Droplet spreading

The effect of the substrate surface wetting properties on the droplets drying behavior has been studied as function of its UV ozone exposure time (see in figure 1). The substrate has been exposed to UV ozone time ranging from 0 to 10 minutes and printing has been performed immediately after UV ozone treatment. As shown in figure S1, surface treatment has increased Su8 surface hydrophilicity. Indeed, water contact angle values have varied over a wide range, from hydrophobic (water contact angle equals at least 90°) to hydrophilic behavior (water contact angle value is less than 40°). Consequently, Su8 film has been chosen to deeply highlight the impact of UV ozone exposure effect. Figure 1a shows three optical pictures, highlighting the effect of UV ozone onto droplets drying behavior. Aggregated silver nanoparticles are highlighted by a light yellow region delimited by the mark: "Inner ring". As expected, UV ozone exposure time has a strong impact on the silver nanoparticles spreading. The more the surface has been exposed to UV ozone, the more the droplet has spread and consequently the more the region covered with nanoparticles is large. Surprisingly, two different droplet drying behaviors can be distinguished as function of UV ozone exposure time. At low UV exposure time (1 minute), only the inner ring can be observed. At higher UV ozone exposure times (6 and 10 minutes) another ring, marked "outer ring", was observed. Such phenomena will be discussed in the next section. Moreover, UV ozone exposure time has also an impact on the two dimensional profile of dried droplet. Figure 1b shows A c c e p t e d m a n u s c r i p t these dried droplets morphologies as function of UV ozone exposure time in order to highlight the evolution of their two dimensional profiles. Figure 1c shows corresponding diameters values extracted from figure 1b.

After 4 minutes UV ozone exposure time, both diameters (inner and outer ring) have no significant evolution. Outer ring cannot be observed before 4 minutes UV exposure time whereas inner ring diameter increases. Moreover, UV ozone exposure time have a strong impact on colloids layer thickness and morphology. Indeed, 10 minutes UV ozone exposure time divides the average thickness by more than 2 and exacerbates the well-known coffee stain effect. [35] Moreover, outer diameter is thicker and larger for 10 minutes of UV exposure time than for 6 minutes.

In conclusion, at low UV ozone exposure time (less than 4 minutes) the behavior of colloidal drying can be described, in first approximation, using Deegan's work. [35] This phenomenon, known as "coffee stain", is due to the solvent evaporation rate which is greater at the surroundings of the so-called "triple contact line". Consequently, when the contact line is pinned, solute transport from the center to the edge is induced by replenish flow, leading to inhomogeneous films after complete evaporation. However, as previously described, droplets drying behavior is different when the surface becomes highly hydrophilic (i.e., at higher UV ozone exposure time).

In this case, Deegan's theory cannot fully explained the drying behavior.

A relevant study has reported the creation of a hydrophobic layer that surrounds (i.e., outer ring) printed patterns (e.g., isolated droplets) on a hydrophilic substrate. [45] This study showed that upon the impact, the droplet spreads at it maximum value before receding to its equilibrium state.

Consequently, during triple contact line receding step, the desorbed stabilizing agent (hexadecylamine, in their case) was deposited leading to a hydrophobic boundary around the printed patterns. Note that, in this study, no observations was performed to confirm this hypothesis.

However, this interesting work has shown that the surrounding layer impacts patterns creation.

In our study, another hypothesis will be drawn to explain such phenomenon. It is based on other works that have studied the drying behavior of a complex mixture. [37,40] Indeed, it has been proved that multicomponent mixtures are submitted to more complex internal flow than these ones studied in the work of Deegan, for instance (i.e., diluted colloids in a solvent). In our work, three components composed the silver based ink (see in experimental section: "materials"): i) hard silver nanoparticles, ii) solvent and iii) Polyvinylpyrrolidone, (PVP). Indeed, it has ever been demonstrated that the commercial ink (DGP 40LT15C) used in this study, reveals the presence of A c c e p t e d m a n u s c r i p t carbonyl groups (FT-IR experiments), suggesting that a polymer ligand such as PVP, has been used. [46,47] Moreover, it is well-known that PVP is commonly used in nanoparticles based ink as surface stabilizer, growth modifier, nanoparticle dispersant, and reducing agent. The PVP avoids large sized nanoparticles agglomerations which can occur due to Van Der Waals or Coulomb's forces. [37,40,41] Indeed, nanoparticles agglomeration is a major drawback for inkjet printing because it drastically increases nozzles clogging and must be avoided. [21] Furthermore, as for the work dealing with hexadeylamine as stabilizing agent, we suggest that an amount of PVP adhered to silver thanks to carbonyl silver bound and another amount is free (desorbed).

Taking into consideration ink composition and the previously mentioned works dealing with multicomponent mixtures drying, an hypothesis can be drawn: during spreading and drying steps, the droplets show a formation of an inner "cap" and an outer "foot" (see in figure 3a), as described in other works. [40,42] A phase separation can occur leading to a colloid rich and a polymer rich region located in the center and at the periphery of the droplet, respectively. We suggest that the polymer rich region is mainly composed of desorbed (free) PVP. In that case, colloidal particles that are confined in the central region, also called "gelation region", form a "solid-like particle gel" which resists to droplet internal flow. [40] Indeed, as the solvent evaporates, concentration of nanoparticles increases and consequently they approach each other until they aggregates due to strong van der Waals interactions. [40] Due to phase separation, polymer which are confined in the foot pinned the droplet and is accumulated at the contact line due to internal flow in the foot. Such that two phases exist in the droplet. Importantly, this observation highlights that the foot area is formed immediately after the droplet deposition and continually expands until the contact line is pinned (i.e, during the spreading step). Note that the dark area corresponds to a region rich in colloids. Colloids show replenish movement and never go outside this region that can suggest the existence of a gelation region. Upon drying, an iridescent region occurs in the foot area. Such observed behavior can highlight a gradient of material thickness. Taking into consideration previous observations, such region could be relative to polymer rich thin films. When spreading reaches it maximum, the triple contact line (first front) is pinned before it recedes letting the residue (figures 3f and 3e). Colloids rich region that has also been pinned (see figures 3g and 3h), dries at last step occurring a classical coffee stain. Consequently, the resulting dried profile (i.e., two rings) is obtained because of a stick-slip motion of the contact line. Indeed, contact line is mainly pinned two times during its receding phase and consequently lets residues of materials where it has been pinned. Note that the observation of the wetting and the drying behavior highlights that the residue is due to a combination of several physical phenomena, which is mainly due to phase separation occurring during droplet spreading and not only the stick-slip motion of the contact line. Note that, additional experiments could be performed to deeply analyze the outer ring regions using in situ X-rays as already shown by Riekel at al. [48,49,50] The results presented in this section have shown that due to the presence of PVP molecules a residue remains at the periphery of the droplet triple contact line whereas colloids are confined in the central region. We have demonstrated that the control of the surface wetting properties is an easy way to drastically reduce such unexpected behavior. Note that, other ink composition using another stabilizer agent have also shown the existence of a surrounding layer. Moreover, it has also been shown that such a layer can have a strong impact on the pattern formation. That's why, in the following, deeper investigations will be performed on more complicated patterns (conductive lines and square shaped patterns) to understand the effect of such residue as function of the substrates wetting and the jetting frequency.

b. Patterns formation i. Lines behaviors

DoD printing technique relies on the coalescence of adjacent droplets in order to form patterns. However, the substrate wettability control is a key parameter to obtain well-defined patterns.

A c c e p t e d m a n u s c r i p t

Indeed, when triple contact line is not firmly pinned patterns can split during drying due to fluid instability as shown in supplementary figure S3. Thus, it is well-known that surface treatment (e.g., UV ozone) is necessary to solve this drawback. As previously highlighted, such a treatment will promote polymeric residue that could have an impact on pattern accuracy. Note that, numerous works report on printed lines drying behaviors. However, at our knowledge, no works have focused on the printed lines formations when a residue is accumulated at the triple line (outer ring). Figure 4 shows the printed lines formation as function of surface wetting behavior and drop spacing (distance between the centers of two adjacent droplets).

Figures (4a, 4b, 4c, and4d) show line formation behavior at low UV ozone exposure time (2 minutes). As expected, when the gap between droplets centers (drop spacing) is: higher than the droplets diameters, close to droplets diameters, well-adjusted or too close, it leads to isolated droplets, scalloped lines, well-defined lines or bulged lines, respectively. The origin of this phenomenon has ever been reported in literature and will not be detailed here. For UV exposure time equals 10 minutes (figures 4e, 4f, 4g, 4h), the same phenomenon occurs for isolated droplets (figure 4e) and scalloped lines (figure 4f). Well-defined lines can also be printed (figure 4g).

However, even if drop spacing is drastically reduced (figure 4h), line does not show bulges. It seems that due to surface hydrophilicity (i.e., low water contact angle), inks spreads and consequently even if drop spacing is reduced, not enough materials is added to obtain bulges instabilities. [33,34] Moreover, zoom in red hatched inset shows that outer ring is formed around the line independently of drop spacing value. This phenomenon can be explained as follows: a line is formed when at least two droplets coalesce. Indeed, a droplet falls down and begins to dry. Another one lands and merges with the first one. At high UV exposure time, the separation phase occurs when droplets dry. Consequently, PVP residue that remains at the triple contact when the first droplet is printed can be dissolved when the second one is printed. The same mechanism occurs until the last droplet of the line is printed. The case shown in figure 4f, well describes the phenomena. Indeed, when inter-droplet distance is higher than inner ring diameter but lower than outer ring diameter only the morphology of the outer ring is impacted during drying. In order to mimic this phenomena, two droplets have been successively drop casted using micropipette. Top view optical images acquired during droplet spreading and drying confirms the previously mentioned explanations (see in figure S4).

A c c e p t e d m a n u s c r i p t

In conclusion, the same drying mechanism observed in the first section at droplet scale, also occurs when line dries. However, it does not drastically impact lines formation but PVP residue remains at periphery of the inner lines. In the next section, deeper investigations will be performed on square shaped patterns to highlight the impact of PVP residue on more complex patterns formation.

ii. Square shaped behaviors

Systematic study

Optical pictures in figure 5 shows the impact of drop spacing, jetting frequency and UV ozone exposure time on printing accuracy of the printed square patterns. The squares are fabricated as follows: droplets are successively printed along x axis (from left to right) and coalesce to form a line. This printing scenario is repeated when the printhead has shifted along y axis, toward the top of the pictures. Consequently, lines coalesce and form the squares (for more details, see the 3D scheme in supplementary figure S5). Importantly, in this set of experiments each square are printed from the bottom left to the top right. The accuracy criterion is that patterns shape have to be a square (1mm×1mm) fully filled with silver. This systematic study shows experimental parameters impact on printing accuracy. The jetting frequency, the drop spacing, the UV ozone exposure time have been varied. As shown in figure 5, whatever UV ozone exposure time is, three behaviors can be clearly distinguished: i) isolated droplets, ii) partially collapsed droplets and iii) merged droplets. Note that the drop spacing values have been carefully adjusted to highlight such well-known behaviors.

When UV ozone exposure time increases the patterns accuracy decreases independently of the jetting frequency or the drop spacing. Nevertheless, whatever UV ozone exposure time was, the patterns could be fully filled with ink (i.e., no fluidic instability). However, patterns are not welldefined even in the wide tested range of drop spacing and jetting frequency. This unexpected behavior needs to be clarified. In order to explain this behavior, deeper investigations on these two parameters influences have been performed.

Drop spacing study

The first row (figures 6a, 6b and 6c) shows independent droplets (i.e., drop spacing is higher than droplet diameter). The second row (figures 6d, 6e and 6c) shows partially merged droplets (i.e., drop spacing value is close to the droplet diameter). The third row (figures 6g, 6h and 6i) shows As previously mentioned, film formation at low UV exposure time (first column) shows different behavior compared to the others columns due to PVP residue ("outer ring") remaining when surface is highly hydrophilic. However, the first line residue impacts the second printed line. Such a phenomena is in good agreement with the supplementary figure S4 where the phenomena has been observed in real time under microscope. It is exacerbated when the drop spacing value decreases for the following reasons.

At high drop spacing (first row), in each cases, the three first printed lines show different spreading and drying behavior. In figure 6a, isolated droplets are observed because outer ring does not occur. Indeed, as already observed in figures 1b and c and discussed in previous sections, when UV ozone exposure time is lower than 4 minutes, the outer ring does not occur.

In figure 6b and 6c, PVP residue is observed but outer ring of each droplets that form a lines has collapsed but has no impact on inner ring of each droplets. In this case, PVP residue does not influence droplets shapes. However squares are not totally filled with ink.

In the second row, when the drop spacing is equal or slightly inferior to the droplets diameters (inner diameter), the outer ring of the previously printed droplets has not enough time to dry and to pin before its neighbour droplet has landed (figure 6e). This behavior occurs for all the droplet that form a line. However, when printing the second lines, the PVP residue of the first line is firmly pinned and consequently, induces deformation of the second line due to it 2 dimensional profile (see figures 6e and 6f). In this case, PVP residue does not influence the first printed lines but the others ones are impacted. Consequently, the square is not well-defined. Note that, the printing parameters that have been fixed in figure 6e are optimum to highlight such hypothesis. In the first line, droplets show circular shape partially collapsed, whereras, in the second line, droplets also collapsed but show semicircular shape. Note that the flat droplets vertex of the second line faces the first printed line, clearly showing the negative impact of PVP residue.

When drop spacing is inferior to droplet diameters (third row), the aforementioned phenomena occurs. Indeed, as inner ring of each droplets overlap square is more filled. However, as shown in figures 6h and 6i, PVP residue remains leading to square deformation. Such assertion is in good As highlighted in this section, the PVP residue influence on patterns formation occurs when such residue have enough time to be pinned. Consequently, could the increase of printing velocity (i.e. the increase of jetting frequency) pave the way to overcome this drawback?

Jetting frequency study

Experiments have been performed to highlight the impact of jetting frequency on square patterns formation. Figure 7a and 7b show optical pictures of squares using the following experimental parameters. For both figures, drop spacing and UV exposure time are fixed and equals 180µm and 10 minutes, respectively. Jetting frequencies varied and equal 20Hz and 3340Hz as shown in figure 7a and7b, respectively. At low jetting frequency (figure 7a), outer ring is formed around each line as usual. Interestingly, when printing frequency increases, as shown in figure 7b, outer ring is observed around the square but cannot be observed around each printed lines. In this case, outer ring formed around each lines has not enough time to be pinned. Consequently, the shape of each droplets inner ring are not impacted. Finally, PVP residue remains at the periphery of the square. Obviously, in this drop spacing conditions, square is not fully filled with ink. When the drop spacing is reduced (see figure 7c), the same phenomena occurs. Patterns accuracy are better when printing at high velocity (figure 7d) compare with those printed at lower frequency (figure 6i for instance). However, in these conditions holes remain. Such a phenomena could be due to a largest amount of PVP induced when printing at lower drop spacing. A way to solve this problem could be to increase printing velocity, however it was not possible with the printer used in this study.

Conclusion

On the basis of previously reported works dealing with multicomponent mixture, microliters scale drop can show phase separation when a multicomponent mixture is used. [40,42] This work highlights that this phenomena can occur when PVP is used as stabilizer in colloidal based ink. It has been demonstrated that printed picoliters droplets and dropcasted microliters drops show the same morphology after drying. Indeed, an inner colloidal rich region and an outer polymer rich A c c e p t e d m a n u s c r i p t region can be distinguished independently of deposition techniques. Moreover, the optical observation of the spreading and drying behavior confirm that a phase separation occurs. The new results observed in this work gave an alternative explanation of the phenomena already observed for another ink containing another kind of stabilizing agent. [45] This complementary work gives more information for ink designer and experimenter involved in the field of printed electronics. Indeed, in the second part of this work, it has been demonstrated that PVP residue has a negative impact onto printed pattern accuracy, especially when the substrate became highly hydrophilic. Moreover, this work has highlighted one of the experimental condition (i.e., substrates wetting behavior) that exacerbates the phase separation of a complex mixture made of colloids and polymer ligand. This study could pave the to other dealing with a systematical study of other experimental conditions such as: ligand kind of material, surface materials and or roughness. It should help to fully understand the phase separation that occurs during inkjet printing of colloids droplets.

Materials and methods

a. Materials

400nm thick Su8 2002 films were obtained using spin-coating (Velocity = 3000 rpm; Acceleration = 3000rpm.s -1 , time = 60 seconds) on glass substrates. Su8 films were baked at 95°C and exposed to UV before the final baking at 110 during at 20 minutes. Jetlight equipment (UVO-Cleaner ® 42) was used for UV ozone exposure. For SEM experiments, Su8 was spin coating following the same process. Silicon substrates was used and 5nm gold was deposited after inkjet printing step (silver based ink). Such protocol was used in order to reduce charging effect during SEM observations. All the experiments have been performed with the same Silver based ink that has been purchased from ANP and used as received. Ink reference is: ANP 40LT15C which is composed of Silver nanopowder, <100 nm particle size and contains PVP as dispersant (Sigma Aldrich). TGME (C8H18O4) is used as main solvent. The metal content, the surface tension, the viscosity and the density equal 30.18wt%, 36.8mN/m, 14.16cps, 1.45g/mL respectively.

b. Jetting experiments:

• Jetting criteria A c c e p t e d m a n u s c r i p t 1 mm (acceptable working distance for the printer equipment: CERADROP Xseries). Satellite droplets or tail must be reabsorbed by the nozzle and jettability must be stable for a long time with low droplet misalignment on the substrate (∆x < 5 µm). The stroboscopic vision system was used to determine droplet volume and velocity of three ink dilutions.

• Jetting at low frequency

For all the experiments, results obtained using 20Hz as jetting frequency show deformed printed patterns. In this case, jetting frequency is closed to the lowest printing velocity of the printer.

Consequently, authors suggest that patterns deformations are only due to the printer.

c. Characterization

Scanning electron microscope images were obtained using a JEOL 7100 FEG microscope. Water contact angle measurements were obtained using Kruss DSA30 equipment. Data are an average value of 10 measurements. Profilometry measurements were performed using TENCOR KLA P6 equipment. Optical microscope images were obtained using a Leica microscope equipped with a digital camera. Optical images in figure 5 were obtained using digital camera of CERADROP Xseries equipement.

FIGURES

A c c e p t e d m a n u s c r i p t Discussion: Zoom in SEM optical observations performed at the border between the cap and the foot (Z1) and inside the cap (Z2) provide deeper information about microscopic structure of colloids after drying. In Z1, two regions can be clearly distinguished. "G mark" shows a region where colloids are densely packed. This region forms a band at the periphery of the cap. Inside the cap (region marked C), colloids show less densely packed structure. We suggest that during drying a gel band is formed where there is no flow. In the C region, radial circulation flow occurs however colloids can't go through the gel band towards the foot. Consequently, coffee stain occurs inside the C regions (see in figures 2c and 2f). Such hypothesis is in good agreement with literature. [40] A c c e p t e d m a n u s c r i p t Overdrop is relative to droplets spacing that coalesce to form a line. Overline is relative to line spacing parameters in order to form square shaped patterns. Note that "Drop after Drop" and "line after line" are relative to X axis displacement and Y axis displacement, respectively. Note that the black circle does not highlight materials such as silver colloids, but the three-phase contact line of a dried droplet.

Videos

a

  behavior leads to the final residue as shown in figure 2. Furthermore, figure S2 (see in supplementary information) give more information about drying behavior inside the cap. Equipment used to perform inkjet printing experiments does not allow to acquire top view images immediately when droplets land on substrate surface to verify this hypothesis. Moreover, due to the small droplet volume (fast evaporation) it is not possible to take the substrate out of the equipment in order to fully analyze spreading and drying behavior. Consequently, spreading and drying analyze have been performed on 0.1 µL droplet deposited using micropipettes under microscope to mimic the phenomena. Top view optical pictures acquired as function of time are shown in figure 3. Images in figures 3a to 3e show the spreading behavior of the droplet onto Su8 surfaces exposed to 6 minutes of UV-ozone. During droplets spreading, materials are not uniformly distributed and two advancing fronts can be observed: the first one is relative to the triple contact line and the second one corresponds to the perimeter of the dark area. It confirms A c c e p t e d m a n u s c r i p t

  s c r i p t merged droplets (i.e., drop spacing value is lower than droplet diameter). Each column corresponds to a different UV ozone exposure time (2, 6 or 10 minutes from left to right).

A

  c c e p t e d m a n u s c r i p t agreement with the optical picture of figure 6g. Indeed, when no PVP residue occurs patterns are well-defined.

Figure 1 :

 1 Figure 1: Morphological evolution of dried droplet as function of UV ozone effect. a) top view optical pictures of dried droplet as function of UV ozone time. UV ozone exposure time equals 1, 6 and 10 minutes (from left to right); b) Two dimensional profiles extracted along the diameter of a dried droplet as function of UV Ozone exposure time. UV ozone exposure time equals: 1, 3, 6 and 10 minutes; c) inner droplet diameter and outer droplet diameter as function of UV ozone exposure time.

  A c c e p t e d m a n u s c r i p t

Figure 2 :

 2 Figure 2: Drying behavior of droplet. a) 3D schematic of droplet at the beginning of drying step. A foot and a cap area occurs. b) 3D profiles showing outer and inner ring of a dried droplet on polymeric surface exposed to UV ozone (10 minutes). c) SEM picture showing dried droplet.

Figure 3 :

 3 Figure 3: Optical images of silver ink drop-casted on Su8 surface exposed to 6 minutes UV-ozone. Images a to d show the drying behavior of the droplet as function of time. Images a) to h) have been captured respectively 3s, 10s, 60s, 90s, 2min, 4min, 6min and 30min, after the droplet deposition. From a) to d), two advancing fronts could be observed showing the separation phase when the droplet spreads. In figure f) the droplet contact line has been pinned and is beginning to recede. In figure g) the solvent has evaporated in the foot area and colloids area remains to dry. In figure h) the droplet is fully dry.

  A c c e p t e d m a n u s c r i p t

Figure 4 :

 4 Figure 4: Lines formation mechanism as function of drop spacing and UV ozone exposure time. Jetting frequency equals 1 kHz. Hatched marks show zoom on lines. UV ozone time equals 2 minutes and drop spacing equals: a) 80µm leading to isolated droplets, b) 60µm leading to scalloped line, c) 40µm leading to well defined lines, d) 25µm leading to bulged line.UV ozone times equals 10 minutes and drop spacing equals: e) 200µm leading to isolated droplets, f) 130µm leading to scalloped lines, g) 70µm leading to well defined line, h) 60µm leading to well defined line.

  A c c e p t e d m a n u s c r i p t

Figure 5 :

 5 Figure 5: Square shaped patterns (approximately 1*1mm) varying drop spacing, jetting frequency and UV ozone exposure time; a) UV ozone exposure time equal 2 minutes; drop spacing varies from 80 to 45µm and jetting frequency varies from 3340 to 20Hz; b) UV ozone exposure time equals 6 minutes; drop spacing varies from 180 to 80µm and jetting frequency varies from 2480 to 20Hz; c) UV ozone exposure time equal 10 minutes; drop spacing varies from 200 to 100µm and jetting frequency varies from 2500 to 20Hz.

  A c c e p t e d m a n u s c r i p t

Figure 6 :

 6 Figure 6: Optical pictures of square shaped patterns (approximately 1×1mm) printed at fixed jetting frequency equals 100Hz and varying: i) UV ozone exposure time equals: 2, 6 and 10 minutes shown in column 1, 2 and 3, respectively; ii) drop spacing in order to print: isolated droplets matrix, partially merged droplets, continues patterns shown in row 1, 2 and 3, respectively. Drop spacing experimental values equals: a) 75µm; b) 160µm; c) 160µm; d) 60µm; e) 140µm; f ) 130µm; g) 45 µm; h) 80 µm; i)100µm .

Figure 7 :

 7 Figure 7: Optical pictures of square shaped patterns (approximately 1×1mm) printed at fixed UV ozone exposure time equals 10 minutes and varying: i) Jetting frequency equals: 20Hz and 3340Hz, shown in column 1 and 2, respectively; Note that, these values corresponds to the lowest and highest available printing velocities. ii) drop spacing in order to print: isolated droplets matrix and, continues patterns shown in row 1 and 2, respectively. Drop spacing experimental values equals: a) 180µm; b) 180µm; c) 100µm; d) 100µm.

Figure S1 :

 S1 Figure S1: Spreading and wetting behavior of the droplets a) Water contact angle and silver based

Figure S2 :

 S2 Figure S2: SEM pictures showing: a) dried droplet, b) A zoom Z1 showing the border between

Figure S3 :

 S3 Figure S3: Square shaped patterns printed on polymeric surface (Su8 2000.5 MicroChem) without UV ozone treatment. Jetting frequency equals 1KHz and drop spacing equals: a) 100 µm leading to isolated droplets, b) 20 µm, c) 10µm, d) 5µm. In images b), c) and d), the printing parameters have been adjusted to overlap adjacent droplet leading to the coalescence of droplets and the formation of a stable pattern.

  A c c e p t e d m a n u s c r i p t

Figure S4 :

 S4 Figure S4: Optical images of two droplets successively drop casted on Su8 surface exposed to 6 minutes UV ozone as function of time. Droplet in the bottom left has been deposited at first. Images a to c show that the two droplets spread with same mechanism than for isolated droplet. In image d, the two contact line collapse and form the same outer ring than this one observed when droplet are printed. Images e to h show the drying step of polymer rich region.

Figure S5 :

 S5 Figure S5: 3D scheme showing working principle of DoD inkjet printing for square shaped patterns. Overdrop is relative to droplets spacing that coalesce to form a line. Overline is relative to

Video S1 :

 S1 20s-movie at 25 frame/s showing jetting of silver based in droplets that respect jettable criterions.

  A c c e p t e d m a n u s c r i p t A c c e p t e d m a n u s c r i p t

ACKNOWLEDGMENTS

This work is supported by the European Union through the European Regional Development Fund (ERDF), and by the French region of Brittany (project: IMPRIM′).

Conflict of interest:

The authors declare that they have no conflict of interest.

AUTHOR INFORMATION

Corresponding Author

* E-mail: maxime.harnois@univ-rennes1.fr

Notes

The authors declare no competing financial interest.

Author Contributions

All authors have given approval to the final version of the manuscript.


N Lazaar

Y Lebbah

S Loudni

M Maamar

V Lemière

C Bessiere

P Boizumault

A Global Constraint for Closed Frequent Pattern Mining

Discovering the set of closed frequent patterns is one of the fundamental problems in Data Mining. Recent Constraint Programming (CP) approaches for declarative itemset mining have proven their usefulness and flexibility. But the wide use of reified constraints in current CP approaches leads to difficulties in coping with high dimensional datasets. In this paper, we proposes the ClosedPattern global constraint to capture the closed frequent pattern mining problem without requiring reified constraints or extra variables. We present an algorithm to enforce domain consistency on ClosedPattern in polynomial time. The computational properties of this algorithm are analyzed and its practical effectiveness is experimentally evaluated.

Introduction

Frequent Pattern Mining is a well-known and perhaps the most popular research field of data mining. Originally introduced by Agrawal et al. [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF], it plays a key role in many data mining applications. These applications include the discovery of frequent itemsets and association rules [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF], correlations [START_REF] Brin | Beyond market baskets: Generalizing association rules to correlations[END_REF] and many other data mining tasks.

In practice, the number of frequent patterns produced is often huge and can easily exceed the size of the input dataset. Most frequent patterns are redundant and can be derived from other found patterns. Hence, closed frequent patterns have been introduced. They provide a concise and condensed representation that avoids redundancy. Discovering the set of closed frequent patterns is one of the fundamental problems in Data Mining. Several specialized approaches have been proposed to discover closed frequent patterns (e.g., A-Close algorithm [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF], CHARM [START_REF] Zaki | CHARM: an efficient algorithm for closed itemset mining[END_REF], CLOSET [START_REF] Pei | CLOSET: an efficient algorithm for mining frequent closed itemsets[END_REF], LCM [START_REF] Uno | An efficient algorithm for enumerating closed patterns in transaction databases[END_REF]).

Over the last decade, the use of the Constraint Programming paradigm (CP) to model and to solve Data Mining problems has received considerable attention [START_REF] De Raedt | Constraint programming for itemset mining[END_REF][START_REF] Guns | k-pattern set mining under constraints[END_REF][START_REF] Khiari | Constraint programming for mining n-ary patterns[END_REF]. The declarative aspect represents the key success of the proposed CP approaches. Doing so, one can add/remove any user-constraint without the need of developing specialized solving methods.

Related to the Closed Frequent Pattern Mining problem (CFPM), Guns et. al., propose to express the different constraints that we can have in Pattern Mining as a CP model [START_REF] Guns | k-pattern set mining under constraints[END_REF]. The model is expressed on Boolean variables representing items and transactions, with a set of reified sum constraints. The reified model has become a de facto standard for many DM tasks. Indeed, the reified model had been adopted for the k-pattern sets [START_REF] Guns | k-pattern set mining under constraints[END_REF]. The drawback is the wide use of reified constraints in the CP model, which makes the scalability of the approach questionable.

In the line of the work of Kemmar et al. [START_REF] Kemmar | PREFIX-PROJECTION global constraint for sequential pattern mining[END_REF], we propose in this paper the ClosedPattern global constraint. ClosedPattern does not require reified constraints and extra variables to encode and propagate the CFPM problem. ClosedPattern captures the particular semantics of the CFPM problem and domain consistency can be achieved on it using a polynomial algorithm. Experiments on several known large datasets show that our approach outperforms the reified model used in CP4IM [START_REF] De Raedt | Constraint programming for itemset mining[END_REF] and is more scalable, which is a major issue for CP approaches. This result can be explained by the fact that ClosedPattern insures domain consistency.

The paper is organized as follows. Section 2 recalls preliminaries. Section 3 provides the context and the motivations for the ClosedPattern global constraint. Section 4 presents the global constraint ClosedPattern. Section 5 illustrates the power of the prunning algorithm compared with the reified model. Section 6 reports experiments. Finally, we conclude and draw some perspectives.

Background

In this section, we introduce some useful notions used in closed frequent pattern mining and constraint programming.

Closed frequent pattern mining

Let I = {1, ..., n} be a set of n item indices1 and T = {1, ..., m} a set of m transaction indices. A pattern P (i.e., itemset) is a subset of I. The language of patterns corresponds to L I = 2 I . A transaction database is a set D ⊆ I × T . The set of items corresponding to a transaction identified by t is denoted by D[t] = {i | (i, t) ∈ D}. A transaction t is an occurrence of some pattern P iff the set D[t] contains P (i.e., P ⊆ D[t]).

The cover of P , denoted by T D (P ), is the set of transactions containing P , that is,

T D (P ) = {t ∈ T | P ⊆ D[t]}. Given S ⊆ T a subset of transactions, I D (S) is the set of common items of S, that is, I D (S) = t∈S D[t]
. The (absolute) frequency of a pattern P is the size of its cover (i.e., freq

D (P ) = |T D (P )|). Let θ ∈ N + be some given constant called a minimum support. A pattern P is frequent if freq D (P ) ≥ θ.
Example 1. Consider the transaction database in Table 1. We have

T D (C) = {t 1 , t 3 } , freq D (C) = 2 and I D ({t 1 , t 3 }) = CH.
Trans. Items t1 B C G H t2 A D t3 A C D H t4 A E F t5 B E F G (b) Trans. A B C D E F G H t1 0 1 1 0 0 0 1 1 t2 1 0 0 1 0 0 0 0 t3 1 0 1 1 0 0 0 1 t4 1 0 0 0 1 1 0 0 t5 0 1 0 0 1 1 1 0
The closure of a pattern P in D, denoted by Clos(P ), is the set of common items of its cover T D (P ), that is, Clos(P ) = I D (T D (P )). A pattern is closed if and only if Clos(P ) = P .

Definition 1 (Closed Frequent Pattern Mining (CFPM)). Given a transaction database D and a minimum support threshold θ, the closed frequent pattern mining problem is the problem of finding all patterns P such that (freq D (P ) ≥ θ) and (Clos(P ) = P ).

Example 2. For θ = 2, the set of closed frequent patterns in Table 1

is ∅ 5 , 2 A 3 , AD 2 , BG 2 , CH 2 and EF 2 .
Closed frequent patterns provide a minimal representation of frequent patterns, i.e. we can derive all frequent patterns with their exact frequency value from the closed ones [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF]. We now define the important notion of full extension that comes from pattern mining algorithms and that we will use later in this paper.

Definition 2 (Full extension). The non-empty itemset Q is called a full extension of P iff T D (P ) = T D (P ∪ Q).

Definition 2 is at the key of the item merging property [START_REF] Wang | CLOSET+: searching for the best strategies for mining frequent closed itemsets[END_REF] stated as follows: If some pattern Q is a full extension of some pattern P , and none of the proper supersets of Q is a full extension of P , then P ∪ Q forms a closed pattern. In other words, a closed pattern can be defined as a pattern that does not possess a full extension. Search Space Issues. In pattern mining, the search space contains 2 I candidates. Given a large number of items I, a naive search that consists of enumerating and testing the frequency of pattern candidates in a dataset is infeasible.

The main property exploited by most algorithms to reduce the search space is that frequency is monotone decreasing with respect to extension of a set.

Property 1 (Anti-monotonicity of the frequency). Given a transaction database D over I, and two patterns X, Y ⊆ I. Then,

X ⊆ Y ⇒ freq D (Y ) ≤ freq D (X).
Hence, any subset (resp. superset) of a frequent (resp. infrequent) pattern is also a frequent (resp. infrequent) pattern.

CFPM under constraints

Constraint-based pattern mining aims at extracting all patterns P of L I satisfying a query q(P ) (conjunction of constraints), which usually defines what we call a theory [START_REF] Mannila | Levelwise search and borders of theories in knowledge discovery[END_REF]: T h(q) = {P ∈ L I | q(P ) is true}. A common example is the frequency measure leading to the frequent pattern constraint. It is also possible to have other kind of (user-)constraints. For instance, constraints on the size of the returned patterns, minSize(P, min ) constraint holds if and only if the number of items of P is greater than or equal to min . Constraints on the presence of an item in a pattern item(P, i) state that an item i must be in a pattern P .

CSP and global constraints

A constraint network is defined by a set of variables X = {x 1 , . . . , x n }, each variable x i ∈ X having an associated finite domain dom(x i ) of possible values, and a set of constraints C on X. A constraint c ∈ C is a relation that specifies the allowed combinations of values for its variables X(c). An assignment σ is a mapping from variables in X to values in their domains. The Constraint Satisfaction Problem (CSP) consists in finding an assignment satisfying all constraints. Domain Consistency (DC). Constraint solvers typically use backtracking search to explore the search space of partial assignments. At each assignment, filtering algorithms prune the search space by enforcing local consistency properties like domain consistency. A constraint c on X(c) is domain consistent, if and only if, for every x i ∈ X(c) and every d i ∈ dom(x i ), there is an assignment σ satisfying c such that x i = d i . Global constraints are constraints capturing a relation between a non-fixed number of variables. These constraints provide the solver with a better view of the structure of the problem. Examples of global constraints are AllDifferent, Regular and Among (see [START_REF] Hoeve | Global constraints[END_REF]). Except the case when for a given global constraint a Berge-acyclic decomposition exists, global constraints cannot be efficiently propagated by generic local consistency algorithms, which are exponential in the number of the variables of the constraint. Dedicated filtering algorithms are constructed to achieve polynomial time complexity in the size of the input, i.e., the domains and extra parameters. The aim of this paper is to propose a filtering algorithm for the frequent closed pattern constraint.

Context and Motivations

This section provides a critical review of ad-hoc specialized methods and CP approaches for CFPM, and motivates the proposition of a global constraint.

Specialized methods for CFPM. CLOSE [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF] was the first algorithm proposed to extract closed frequent patterns (CFPs). It uses an apriori-like bottom-up method. Later, Zaki and Hsiao [START_REF] Zaki | CHARM: an efficient algorithm for closed itemset mining[END_REF] proposed a depth-first algorithm based on a vertical database format e.g. CHARM. In [START_REF] Pei | CLOSET: an efficient algorithm for mining frequent closed itemsets[END_REF], Pei et al. extended the FP-growth method to a method called CLOSET for mining CFPs. Lastly, Uno et al. [START_REF] Uno | An efficient algorithm for enumerating closed patterns in transaction databases[END_REF] have proposed LCM, one of the fastest frequent itemset mining algorithm. It uses a hybrid representation based on vertical and horizontal representations. The milestone of LCM is a technique called prefix preserving closure extension (PPCE), which allows to generate a new frequent closed pattern from a previously obtained closed pattern. Let us explain the PPCE principle. Consider the closed pattern P . Let P (i) = P ∩ {1, ..., i} be the subset of P consisting of items no greater than i. The core index of P , denoted by core(P ), is the minimum index i such that T D (P (i)) = T D (P ). A pattern Q is PPCE of P if Q = Clos(P ∪ {i}) and P (i -1) = Q(i -1) for an item i ∈ P and i > core(P ). The completeness of PPCE is guaranteed by the following property: If Q is a nonempty closed itemset, then there is only one closed itemset P such that Q is a PPCE of P . The mining process using LCM is a depth first search where at each node we have a closed pattern P . LCM uses the PPCE technique as a branching strategy to jump from a closed pattern to other closed patterns by adding new items. With its specialized depth first search, LCM succeeds to enumerate very quickly the closed patterns. However, if the user considers other (user-)constraints on patterns, the search procedure should be revised. In fact, all these specialized proposals (e.g., Closet, Charm, LCM, etc.), though efficient, are ad-hoc methods suffering from the lack of genericity, since adding new constraints requires new implementations.

Reified constraint model for itemset mining. De Raedt et al. have proposed in [START_REF] De Raedt | Constraint programming for itemset mining[END_REF] a CP model for itemset mining. They show how some constraints (e.g., frequency, maximality, closedness) can be modeled as CSP [START_REF] Nijssen | Integrating constraint programming and itemset mining[END_REF][START_REF] Guns | Itemset mining: A constraint programming perspective[END_REF]. This modeling uses two sets of Boolean variables P and T : (1) Decision variables: item variables P 1 , P 2 , ..., P n , where P i = 1 if and only if item i is in the searched pattern; (2) Auxiliary variables: transaction variables T 1 , T 2 , ..., T m , where T t = 1 if and only if the searched pattern is in D [t].

The relationship between P and T , set of channeling constraints, is modeled by reified constraints stating that, for each transaction t,

(T t = 1) iff P is a subset of D[t]: ∀t ∈ T : (T t = 1) ↔ i∈I P i (1 -D[t, i]) = 0 (arity n + 1). The min frequency constraint is modeled us: ∀i ∈ I : (P i = 1) → t∈T T t D[t, i] ≥ θ (arity m + 1)
. The closedness constraint is expressed with: ∀i ∈ I :

(P i = 1) ↔ t∈T T t (1 -D[t, i]) = 0 (arity m + 1)
. Such encoding has a major drawback since it requires (m + n + n) reified constraints of arity (n + 1) and (m + 1) to encode the whole database. This constitutes a strong limitation especially when it comes to handle very large databases.

We propose in the next section the ClosedPattern global constraint to encode both the minimum frequency constraint and the closedness constraint. This global constraint requires neither reified constraints nor auxiliary variables.

ClosedPattern Constraint

This section presents the ClosedPattern global constraint for the CFPM problem.

Definition and filtering

Let P be the unknown pattern we are looking for. The unknown pattern P is encoded with Boolean item variables P 1 , ..., P n . In the rest of the paper we will denote by σ the partial assignment obtained from the variables P 1 , ..., P n that have a singleton domain. We will also use the following subsets of items:

-present items: σ + = {j ∈ 1..n | P j = 1}, -absent items: σ -= {j ∈ 1..n | P j = 0}, -other items: σ * = {1..n} \ (σ + ∪ σ -). σ * is the set of free items (non instantiated variables). If σ * = ∅ then σ is a complete assignment.
The global constraint ClosedPattern ensures both the minimum frequency property and the closedness property.

Definition 3 (ClosedPattern global constraint). Let P 1 , . . . , P n be binary item variables. Let D be a transaction database and θ a minimum support. Given a complete assignment σ on P 1 , . . . , P n , ClosedPattern D,θ (σ) holds if and only if freq D (σ + ) ≥ θ and σ + is closed. Let σ be a partial assignment of variables P and i a free item. We use the vertical representation of the dataset, denoted V D where for each item, the transactions containing it are stored: ∀i ∈ I, V D (i) = T D ({i}). We denote by V σ + D (i) the cover of item i within the current cover of a pattern σ + :

V σ + D (i) = T D (σ + ∪ {i}) = T D (σ + ) ∩ T D ({i}).
We need to define extensible assignments. Definition 4 (Extensible assignment). Given a constraint ClosedPattern D,θ on P 1 , . . . , P n , a partial assignment is said to be extensible if and only if it can be extended to a complete assignment of P 1 , . . . , P n that satisfies ClosedPattern D,θ .

We show when a partial assignment is extensible with respect to Closed-Pattern constraint.

Proposition 1. Let σ be a partial assignment of variables in P 1 , . . . , P n . σ is an extensible partial assignment if and only if freq D (σ + ) ≥ θ and ∃j ∈ σ -such that {j} is a full extension of σ.

Proof. According to the anti-monotonicity property of the frequency (cf. Property 1), if the partial assignment σ is infrequent (i.e., freq D (σ + ) < θ), it cannot, under any circumstances, be extended to a closed pattern.

Given now a frequent partial assignment σ (i.e., freq D (σ + ) ≥ θ), let us take j ∈ σ -such that {j} is a full extension of σ. It follows that T D (σ + ) = T D (σ + ∪{j}) = V σ + D (j). Therefore, Clos(σ + ) = Clos(σ + ∪{j}). Since σ + without j (j being in σ -) cannot be extended to a closed pattern, the result follows. If there is no item j ∈ σ -such that {j} is a full extension of σ, then the current assignment σ can be definitely extended to a closed itemset by adopting a full extension to form a closed pattern.

We now give the ClosedPattern filtering rules by showing when a value of a given variable is inconsistent.

Proposition 2 (ClosedPattern filtering rules). Let σ be an extensible partial assignment of variables in P 1 , . . . , P n , and P j (j ∈ σ * ) be a free variable. The following two cases characterize the inconsistency of the values 0 and 1 of P j :

-0 ∈ dom(P j ) iff: {j} is a full extension of σ.

(rule 1)

-1 ∈ dom(P j ) iff: |V σ + D (j)| < θ ∨ (rule 2) ∃k ∈ σ -, V σ + D (j) ⊆ V σ + D (k). ( rule 3)
Proof. Let σ be an extensible partial assignment and P j be a free variable.

0 ∈ dom(P j ) : (⇒) Let 0 be an inconsistent value. In this case, P j can only take value 1. It means that Clos(σ

+ ) = Clos(σ + ∪ {j}). Thus, T D (σ + ) = T D (σ + ∪ {j})
. By definition 2, {j} is a full extension of σ.

(⇐) Let {j} be a full extension of σ, which means that Clos(σ + ) = Clos(σ + ∪ {j}) (def. 2). The value 0 is inconsistent where j cannot be in σ -(prop.1). 1 ∈ dom(P j ) : (⇒) Let 1 be an inconsistent value. This can be the case if the frequency of the current pattern σ + is set up below the threshold θ by adding the item j (i.e., |V σ + D (j)| < θ). Or, σ + ∪ {j} cannot be extended to a closed itemset: this is the case when there exists an item k ∈ σ -such that at each time the item j belongs to a transaction in the database, k belongs as well

(V σ + D (j) ⊆ V σ + D (k)).
Conversly, the lack of k (i.e., k ∈ σ -) implies the lack of j as well. This means that: (P k = 0 ⇒ P j = 0). (⇐) This is a direct consequence of Proposition 1.

The first rule takes its origin from item merging [START_REF] Wang | CLOSET+: searching for the best strategies for mining frequent closed itemsets[END_REF]. The second rule is a basic rule derived from the property of anti-monotonicity of the frequency (Property 1). To the best of our knowledge, the third rule is a new rule taking its originality from the reasoning made on absent items.

Example 4. Following Example 3, consider a partial assignment σ such that the variable

P 1 is set to 0 (item A). That is, σ -= {A} and σ + = ∅. Value 1 from dom(P 4 ) (item D) is inconsistent because the lack of A implies the lack of D in D (i.e., V σ + D (D) ⊆ V σ + D (A)). Let now P 1 = 0, P 4 = 0, that is, σ -= {A, D} and σ + = ∅. If the variable P 3 is set to 1 (item C), value 1 from P i , i = {2, 5, 6, 7} (items B, E, F, G) is inconsistent because |V σ + D (P i )| < 2,
and value 0 from P 8 (item H) is also inconsistent because {H} is a full extension of σ.

Algorithm 1: Filter-ClosedPattern(V D , θ, σ, P )

1 Input: VD : vertical database; θ : minimum support 2 InOut: P = {P1 . . . Pn}: Boolean item variables; σ : current assignment.

3 begin 4 if ( |TD(σ + )| < θ) then return f alse; 5 if ∃ i ∈ σ -: |V σ + D (i)| = |TD(σ + )| then return f alse; 6 foreach i ∈ σ * do 7 if (|V σ + D (i)| = |TD(σ + )|) then 8 dom(Pi) ← dom(Pi) -{0}; 9 σ + ← σ + ∪ {i}; σ * ← σ * \ {i}; 10 else if (|V σ + D (i)| < θ) then 11 dom(Pi) ← dom(Pi) -{1}; 12 σ -← σ -∪ {i}; σ * ← σ * \ {i}; 13 foreach i ∈ σ -do 14 foreach j ∈ σ * : V σ + D (j) ⊆ V σ + D (i) do 15 dom(Pj) ← dom(Pj) -{1}; 16 σ -← σ -∪ {j}; σ * ← σ * \ {j}; 17 return true;

ClosedPattern Filtering Algorithm

In this section, we present the algorithm Filter-ClosedPattern (Algorithm 1) for enforcing domain consistency on the ClosedPattern constraint. Filter-ClosedPattern incrementally maintains the internal data structures σ =< σ + , σ -, σ * > and the corresponding cover T D (σ + ). Using these two structures, one can check if an item is present or not in the vertical dataset V D .

Algorithm 1 takes as input the vertical dataset V D , a minimum support threshold θ, the current partial assignment σ on P where σ * = ∅, and the variables P . As output, Algorithm 1 reduces the domains of P i 's and therefore, increases σ + and/or σ -, and decreases σ * .

The algorithm starts by checking if the current partial assignment is extensible or not (Proposition 1). This is performed by checking 1) if the size of the current cover is greater than the minimum support (line 4) and 2) if no item of a variable already instantiated to zero is a full extension of σ + (line 5).

Lines 6-12 are a straightforward application of rules 1 and 2 of Proposition 2. For each non-instantiated variable, 1) we check if value 0 is consistent: that item is not a full extension (lines 6-9), and 2) we check if value 1 is consistent: the new cover size by adding that item remains greater than θ (lines 10-12).

Finally, lines 13-16 implement rule 3 of Proposition 2. We prune value 1 from each free item variable i ∈ σ * such that its cover is a superset of the cover of an absent item j ∈ σ . This is done only once. The cover V σ + D (i) can be computed by intersecting T D (σ + ) (already computed) and T D ({i}) (given by the vertical representation) within at most O(m). Checking rules 1 and 2 on all free variables can be done in O(n × m) ( lines 6-12). However, checking rule 3 is cubic at lines 13-16 (i.e., O(n × (n × m))), where checking if a cover V σ + D (i) is a subset of another cover can be done in O(m). Finally, the worst case complexity is O(n × (n × m)). Space: The space complexity of Filter-ClosedPattern lies in the storage of V D , σ and the cover T data structures. The vertical representation V D requires at most n × m space. In the worst case, we have to store n items within σ and m transactions within T . That is, the worst case space complexity is

-(V σ + D (i) ⊆ V σ + D (j)).
O(n × m + n + m) = O(n × m).
During the solving process in depth first search, the whole space complexity is O(n × (m + n)) because (1) the depth is at most n; (2) σ and T require O(n × (m + n)); (3) the vertical representation is the same data used all along the solving process

O(n × m); (4) O(n × (m + n)) + O(n × m) = O(n × (m + n)).
Proposition 3 (Backtrack-free). Extracting the total number of closed frequent patterns, noted C, is backtrack-free with a complexity in O(C × n 2 × m) using Filter-ClosedPattern to propagate the ClosedPattern constraint.

Proof. Filter-ClosedPattern ensures DC at each node of the search tree. Hence, the closed frequent patterns are guaranteed to be produced in a backtrackfree manner. The explored search tree is a binary full tree where each node is either a leaf (a solution) or possesses exactly two child nodes. The number of nodes is thus in O(2×C). Knowing that ensuring DC is in O(n 2 ×m), extracting the total number of closed frequent patterns is in O(C × n 2 × m).

Data structures

To represent the transactional dataset and the cover of items, we adopted the vertical representation format [START_REF] Zaki | Fast vertical mining using diffsets[END_REF]. Our implementation is in or-tools solver3 . Static structures: for each item i ∈ I, T D (i) = {t ∈ T | i ∈ t} is stored as a bitset of size m. If t ∈ T D (i), then the associated bit is set to 1 (0 otherwise). Dynamic structure: a vector M emo of bitsets is used to store the cover of each partial solution. M emo is a vector of size n + 1, since at the beginning of the search, the partial assignment is empty. Let σ be a partial assignment. Each time a (new) variable P i is instantiated, the cover of the new partial assignment Backtracking. First, all P i , as well as their domains dom(P i ), are fully maintained by the or-tools backtracking. Then, a single value (the current index of the vector M emo) is asked to be managed by the or-tools backtracking. Each time a partial solution is extended (from σ to σ ∪ {i}), the current index of M emo is memorised. When a backtrack occurs (from σ ∪ {i} to σ), this value is restored by or-tools giving access to the cover of the (restored) partial solution. Rule 3. The inclusion between two covers

V σ + D (i) ⊆ V σ + D (j) is rewritten as V σ + D (i) ∩ V σ + D (j) = V σ + D (i)
, and the intersection is performed by a bitwise-AND.

Running example

In this section, we illustrate the propagation of our ClosedPattern constraint and the difference that exists comparing to the use of a simple Reified Constraint Model (denoted by RCM, and detailed in Section 3). For that, let us take the transactional dataset given in Table 1: Five transactions t 1 to t 5 and eight items from A to H. Figure 1 shows the tree search explored using ClosedPattern (part(a)) and the tree search explored using a reified model (part(b)) to extract closed frequent patterns at minimum support θ = 2. Here, both approaches use the same branching heuristics, namely Lex on variables and Max_val on values. First of all, it is worth noticing that the search space that can be explored using ClosedPattern is defined only on decision variables (item variables), whereas the reified model adds a further dimension with auxiliary variables (transaction variables).

At the root node (node 1), no pruning is done since all items are frequent and no item is a full extension of the empty pattern (see Table 1). Thereafter, ClosedPattern and RCM are acting in the same manner on the branch A = 1. With A = 1, B, C, E, F, G, H become infrequent. That is, the 1 values are pruned (rule 2). With RCM on node 2, the pruning on the five decision variables (the item variables) induce a pruning on four auxiliary variables (transaction variables). On the branch A = 1, two solutions are found: AD and A .

Branching on A = 0 (node 5), the value 1 of D is pruned with rule 3 of ClosedPattern. From Table 1, we have D ⇒ A, and a branching on A = 0 reduces D to 0. Here, we can say that the DC is maintained on node 5 using ClosedPattern, which is not the case using RCM. The same observation can be made on nodes 7, 9 and 11.

Let us take the node 6, here the branching on A = 0 and thereafter on B = 1 will make C, D, E, F, H infrequent (rule 2). Moreover, (rule 1) can be applied since G is a full extension of B (i.e., we cannot have a frequent closed pattern including B without G). That is, the value 0 is pruned from the domain of G, which allows us to reach the solution BG . The same observation can be made on node 8.

To sum up, Filter-ClosedPattern maintains DC at each node and thus, enumerates the solutions backtrack-free (no fails). The same cannot be said with RCM because the rule 3 is never covered in this example and there are 3 fails.

Experiments

We made several experiments to compare and evaluate our global constraint with the state of the art methods (CP and specialized methods). Benchmark datasets. We selected several real and synthetic datasets [START_REF] Zaki | CHARM: an efficient algorithm for closed itemset mining[END_REF][START_REF] Grahne | Fast algorithms for frequent itemset mining using FP-Trees[END_REF] from FIMI repository4 with large size. These datasets have varied characteristics representing different application domains. Table 2 reports for each dataset, the number of transactions |T |, the number of items |I|, the average size of transactions |T |, its density ρ (i.e., |T |/|I|) and its size (i.e., |T | × |I|). We note that the datasets are presented according to their size. They represent various numbers of transactions, numbers of items, densities. We have datasets that are very dense like Chess and Connect (resp. 49% and 33%), and others that are very sparse like Retail and BMS-Web-View1 (resp. 0.06% and 0.5%). Note that we have datasets of sizes going from ≈ 10 5 to more than 10 9 . Experimental protocol. The implementation of our approach was carried out in the or-tools solver. All experiments were conducted on an Intel Xeon E5-2680 @ 2.5 GHz with 128 Gb of RAM with a timeout of 3600s. For each dataset, we decreased the (relative) θ threshold until it is impossible to extract all closed patterns within the allocated time/memory. We have implemented two variants of ClosedPattern constraint: (i) ClosedPattern-dc ensuring DC with rules 1,2 and 3 (cubic prunning). (ii) ClosedPattern-wc ensuring a weaker consistency with only rules 1 and 2 (quadratic prunning). Comparisons are made with: (i) CP4IM, the state-of-the-art on CP approaches, that uses an RCM model.

(ii) LCM, the state-of-the-art on specialized methods. For ClosedPattern and CP4IM, we use the same branching heuristics, namely Lex on variables and Max_val on values. We experimented using the available distributions of LCM-v5.3,5 and CP4IM, 6 with Gecode as the underlying solver of CP4IM. Table 3 gives a comparison between ClosedPattern (wc and dc versions), CP4IM and LCM. We report the number of closed patterns #C of each instance, the number of propagations, the number of nodes, the CPU times in seconds and the number of failures.

ClosedPattern (dc vs wc). Despite the pruning complexity, dc clearly dominates wc in terms of CPU times (except for BMS1 dataset where both are more or less equivalent). For instance, on the pumsb dataset with θ = 70%, dc is about 4 times faster than wc. As a second observation, the use of rule 3 can reduce drastically the number of explored nodes and thus, number of propagations. For instance, we note a reduction of 38% on explored nodes on connect and 98% on splice1 compared to wc. ClosedPattern vs CP4IM. If we compare ClosedPattern with CP4IM, the main observation is that dc outperforms significantly CP4IM at all levels. In terms of CPU times and without counting the Out-of-memory instances, we can observe 23 instances (out of 30) with a speed-up factor between 2 and 15. Factors of 27 to 45 are noted for six instances and for one instance, we have a factor of 182. The weaker version (wc) is also better than CP4IM except two instances in connect and two instances in chess. In terms of number of propagations, we observe a gain factor within a range from 13 to 300. This is because of Figure 2 shows a comparison between two models, M1 using ClosedPattern for the CFPM part of the problem, M2 using a CP4IM implementation. We selected two dataset instances where CP4IM does not reach the Out-of-memory state and where we have a reasonable number of closed patterns, chess with θ = 80% (5084 closed patterns) and connect with θ = 90% (3487 closed patterns), and we have varied k with a timeout of 3600s. After a few preliminary tests, the bounds lb and ub on the size of the patterns were set to 2 and 10 respectively. On chess, model M1 is robust and scales well: it is linear on k and never exceeds 6 min even with k = 12 (323.53s). M2 follows an exponential scale and goes beyond the timeout with only k = 8 (7222.41s). The same observation can be made on the connect instance, but in a more pronounced way on the exponential scale followed by M2. With k = 4, M2 goes beyond the timeout with 5428.05s whereas M1 confirms its linear behavior when varying k from 2 to 12.

D θ #C #Propagations #Nodes Time (s) Failures (%) (≈) (1) (2) (3) (1) (2) (3) (1) (2) (3) LCM (1) (2) (3)
For such problems, a baseline can be the use of specialized methods with postprocessing. One can imagine (i) the use of LCM to extract the total number of closed patterns and (ii) a generate-and-test search trying to find distinct patterns of a given size. Such approach can be very expensive. Here, the postprocessing will generate all the possible k combinations of closed patterns. For instance, we recall that for chess with θ = 80% we have 5084 closed patterns. With k = 12 and using M1 , we need less than 6 min, where using the baseline we have to cope with a massive number of combinations. Thus, this last experiment confirms that if LCM is faster on basic queries (e.g., asking for closed frequent with given size), it cannot cope with complex queries. It would need to think and to propose an adhoc solution whereas CP enables a novice DM-user to express his query as constraints.

Conclusion

In this paper we have introduced a new global constraint for Closed Frequent Pattern Mining. The ClosedPattern constraint captures the particular semantic of the CFPM problem, namely the minimum frequency and closedness of patterns. To propagate efficiently this global constraint, we have first defined three filtering rules that ensure domain consistency. Second, we have defined a filtering algorithm that establishes domain consistency in a cubic time complexity and quadratic space complexity. We have implemented this filtering algorithm into the or-tools solver using a vertical representation of datasets and smart data structures. We have conducted an experimental study on several real and synthetic datasets, showing the efficiency and the scalability of the global constraint compared to a reified constraints approach such as CP4IM. Finally, to show the applicability and the flexibility of ClosedPattern compared to specialized methods we performed experiments on an instance of k-pattern set problem where ClosedPattern is integrated with a set of constraints.

Example 3 .

 3 Consider the transaction database of Table 1a with θ = 2. Let P = P 1 , . . . , P 8 with dom(P i ) = {0, 1} for i ∈ 1..8. Consider the closed pattern AD encoded by P = 10010000 , where σ + = {A, D} and σ -= {B, C, E, F, G, H}. ClosedPattern D,2 (P ) holds because freq D ({A, D}) ≥ 2 and {A, D} is closed.

Theorem 1 .

 1 Given a transaction database D of n items and m transactions, and a threshold minsup θ. Algorithm Filter-ClosedPattern enforces domain consistency on the ClosedPattern constraint, or proves that it is inconsitent in time O(n 2 × m) with a space complexity of O(n × m). Proof. DC: Filter-ClosedPattern implements exactly Proposition 1 and the three rules given in Proposition 2. Thus Filter-ClosedPattern ensures domain consistency (see the description of Algorithm 1). Time: Let n = |I| and m = |T |. First, we need to compute T D (σ + ) which requires at most O(n × m)

Fig. 1 :

 1 Fig. 1: (a) ClosedPattern and (b) Reified Constraint Model (RCM)

Fig. 2 :

 2 Fig. 2: dist_kpatterns_lb_ub instance using ClosedPattern and CP4IM.

Table 1 :

 1 A transaction database D (a) and its binary matrix (b).

	(a)

Table 2 :

 2 Dataset Characteristics.

	Dataset	|T |	|I|	|T | ρ	type of data	size
	Chess	3 196 75	37 49% game steps	239 700
	Splice1	3 190 287	60 21% genetic sequences	915 530
	Mushroom	8 124 119	23 19% species of mushrooms	966 756
	Connect	67 557 129	43 33% game steps	8 714 853
	BMS-Web-View1 59 602 497	2.5 0.5% web click stream	29 622 194
	T10I4D100K	100 000 1 000 10 1%	synthetic dataset	100 000 000
	T40I10D100K	100 000 1 000 40 4%	synthetic dataset	100 000 000
	Pumsb	49 046 7 117 74 1%	census data	349 060 382
	Retail	88 162 16 470 10 0.06% retail market basket data 1 452 028 140

Table 3 :

 3 ClosedPattern vs CP4IM vs LCM. (OOM: Out Of Memory; TO: TimeOut;

	(1): ClosedPattern-wc; (2): ClosedPattern-dc; (3): CP4IM)

  OOMthe huge number of propagator calls for reified constraints comparing to one propagator call using ClosedPattern. The number of explored nodes is also reduced, sometimes by half (e.g., mushroom), using ClosedPattern-dc. This is not a surprise as its number of explored nodes is optimal. Another observation is the experimental validation of Proposition 3: ClosedPattern-dc extracts the closed patterns in a backtrack-free manner. All solutions are enumerated without any fail (see failures column in Table3). CP4IM requires an important number of backtracks on most datasets. On connect and three instances of splice1 we can observe that ClosedPattern-dc and CP4IM explore the same number of nodes. The reified model on such dense datasets and using (Lex\Max_val) heuristics is able to prune all inconsistent values. This result is confirmed by the number of failures always equal to zero (backtrack-free). Even if the wc version is faster, CP4IM remains better in terms of pruning (#nodes). Finally, the major drawback using the reified model for frequent pattern extraction is the memory consumption. We denote 25 Out-of-memory (out of 51 instances). The Out-ofmemory state is due to the huge number of reified constraints. For instance, if we take the T40I10D100K dataset, the CP model produced by CP4IM contains |T | + |I| = 101 000 variables, |T | = 100 000 reified constraints to express the channeling constraints, 2×|I| = 2×1 000 reified constraints to express the closure and frequency constraints. This means that the CP solver has to load in memory a CP model of 102 000 reified constraints expressed on 101 000 variables, which represents the size given in Table2. From Table2, we observe that Gecode is not able to handle CP4IM models on datasets of size greater than ≈ 10 7 (greater than connect dataset).ClosedPattern vs LCM. In terms of CPU times, LCM remains the leader on basic queries. However, ClosedPattern is quite competitive as a declarative approach. For instance, if we take chess dataset, LCM is 15 times faster than ClosedPattern-dc on average, where it is more than 120 times faster on average comparing to CP4IM. ClosedPattern pruning acts only within the current node of the search tree, without imposing any condition on the main search algorithm such as variable or value orderings. This allows to consider new constraints and let the main search algorithm adopt the best heuristics favouring the whole solving. To illustrate our point, we propose to model a particular problem (k-pattern sets) in a declarative manner where LCM could not meet this need.

		50 10 5	4 037 618	920 377 9 201 740	4 037 211	738 901	738 907	7.26	3.21	10.97	0.32 1 649 155 0	3
	chess	40 10 6 15 931 714 30 10 6 71 744 915 13 298 679 105 040 377 71 734 057 10 679 631 10 681 739 3 411 690 30 541 475 15 929 751 2 733 667 2 733 735 20 10 7 305 446 222 56 550 872 385 399 747 305 374 413 45 837 171 45 901 933	26.37 109.36 480.52 187.89 467.52 27.55 1.29 × 10 8 0 32 381 12.27 40.85 1.44 6 598 042 0 34 45.92 136.31 6.07 30 527 213 0 1 054
		10 10 8	1.51 × 10 9 304 335 522 1.66 × 10 9 1.51 × 10 9 247 960 091 249 411 325 2 287.98 969.40 1 950.51 141.55 6.34 × 10 8 0 725 617
	splice1	20 10 2 10 10 3 5 10 4 1 10 7 754 074 683 193 156 761 2.43 × 10 9 754 067 617 13 454 755 13 467 247 54 055 25 078 913 779 53 991 487 487 303 405 57 623 1 810 466 303 359 3 211 3 211 5 013 077 1 706 269 36 211 067 5 013 031 63 935 63 935	0.10 0.18 3.39 502.77 400.10 1 652.41 53.59 3.70 × 10 8 0 6 246 0.59 22.59 0.04 26 752 0 0 0.14 25.54 0.07 150 074 0 0 3.23 138.54 1.46 2 474 548 0 0
		30 10 2	6 323	1 530	430 016	6 179	853	1 039	0.46	0.64	0.77	0.00	2 663 0	93
		20 10 3	34 375	4 414 1 031 778	34 113	2 405	3 083	0.92	0.56	2.36	0.01	15 854 0	339
	mushroom	10 10 4 5 10 4 1 10 5 0.5 10 5	148 429 496 643 2 347 734 3 896 158	17 456 2 771 719 46 165 5 574 143 178 834 13 813 312 264 660 18 230 838	147 623 494 559 2 339 109 3 883 697	9 793 25 707 103 343 156 613	13 281 36 495 168 999 265 781	0.38 0.84 3.42 5.00	0.15 0.41 1.74 3.62	5.32 10.98 24.06 29.84	0.04 0.09 0.22 1 117 883 0 32 828 68 915 0 1 744 234 426 0 5 394 0.34 18 635 42 0 54 584
		0.1 10 5	7 148 533	516 041 31 222 435	7 130 827	328 233	529 289	9.96	5.40	41.38	0.47 3 401 297 0 100 528
		0.05 10 5	8 001 925	613 712 36 520 438	7 983 119	407 763	622 145	9.94	6.37	43.69	0.51 3 787 678 0 107 191
		90 10 3	12 377	10 272 1 865 236	9 725	6 973	6 973	2.45	0.92	7.10	0.22	1 376 0	0
		80 10 4	60 312	48 156 9 455 886	44 771	30 223	30 223	9.35	1.65	16.57	0.31	7 274 0	0
		70 10 4	158 817	120 184 24 969 205	115 335	71 761	71 761	24.26	4.09	33.72	0.40	21 787 0	0
	connect	60 10 5 50 10 5 40 10 5	297 175 570 870 1 139 466	240 634 51 648 114 469 442 98 602 318 886 722 177 653 293	202 637 378 603 762 579	136 699 260 223 478 781	136 699 260 223 478 781	45.23 85.99 159.04	7.30 14.53 110.19 45.73 27.32 153.39	0.39 0.52 0.83	32 969 0 59 190 0 141 899 0	0 0 0
		30 10 5	2 173 593	1 752 199 313 288 691	1 400 609	920 823	920 823	263.64	49.97 304.52	1.37	239 893 0	0
		20 10 6	8 440 998	5 637 016 633 429 969	6 092 697	2 966 399 2 966 399	678.95 157.40 712.68	4.37 1 563 149 0	0
		10 10 7 55 152 559 31 370 763 1.76 × 10 9 41 641 659 16 075 555 16 075 555 3 110.90 760.71 2 597.89 17.70 12 783 052 0	0
	BMS1	0.20 10 3 0.16 10 3 0.12 10 3	311 638 493 069 921 446	105 403 116 902 134 436	OOM OOM OOM	250 959 432 419 860 811	1 677 2 617 4 971	OOM OOM OOM	111.04 161.60 239.08 202.46 145.72 218.88	OOM OOM OOM	0.04 0.06 0.05	124 671 0 214 939 0 427 940 0	OOM OOM OOM
		0.08 10 4	3 638 431	200 049	OOM	3 577 735	20 787	OOM 2 441.84 1 899.70	OOM	0.11 1 778 490 0	OOM
		10 1	1 000	1 000	OOM	1	1	OOM	0.46	0.24	OOM	0.03	0 0	OOM
		1	10 2	155 166	76 955	OOM	154 559	805	OOM	3.75	1.14	OOM	0.14	76 894 0	OOM
	T10*	0.5 10 3 0.1 10 3 11 228 933 509 852	174 015 520 218	OOM OOM 11 228 667 509 441	2 185 53 625	OOM OOM	10.29 258.44	3.11 11.30	OOM OOM	0.42 0.94 5 587 527 0 253 647 0	OOM OOM
		0.05 10 4 21 004 412	1 257 876	OOM 21 003 915	93 987	OOM	477.22	27.96	OOM	1.30 10 454 964 0	OOM
		0.01 10 5 130 686 806 17 313 642	OOM 130 673 093	566 795	OOM 1 471.32 905.17	OOM	3.49 65 053 149 0	OOM
		10 10 2	8 712	4 900	OOM	7 801	177	OOM	0.89	1.13	OOM	0.43	3 818 0	OOM
	T40*	5 1	10 2 10 5 19 932 041 97 982	47 983 937 766	OOM OOM 19 931 799 97 289	643 130 477	OOM OOM	2.34 599.49	1.78 25.78	OOM OOM 21.32 9 900 663 0 1.31 48 328 0	OOM OOM
		0.5 10 6	TO	6 394 931	OOM	TO	2 551 883	OOM	TO 953.58	OOM 13.31	TO 0	OOM
		95 10 2	7 981	7 438	OOM	877	223	OOM	2.85	1.45	OOM	0.20	328 0	OOM
	pumsb	90 10 3 85 10 4 80 10 4 75 10 5	17 429 61 459 176 955 472 624	11 074 29 149 89 805 249 382	OOM OOM OOM OOM	10 323 54 331 169 743 465 267	2 933 17 027 66 615 202 165	OOM OOM OOM OOM 1 010.43 44.92 155.79 640.59 133.97 13.37 58.84 271	OOM OOM OOM OOM	0.29 0.27 0.33 0.48	3 695 0 18 652 0 51 564 0 131 551 0	OOM OOM OOM OOM
		70 10 5	969 374	567 929	OOM	961 763	482 517	OOM 2 150.80 509.79	OOM	0.69	239 623 0	OOM
		10 10	16 501	16 490	OOM	37	19	OOM	1	2.55	OOM	0.06	9 0	OOM
	retail	1 0.5 10 3 10 2 0.1 10 4 23 520 823 31 089 205 688	19 852 56 868 4 506 219	OOM OOM OOM 23 506 749 14 695 189 475	329 1 233 15 901	OOM OOM OOM	11.03 61.41 495.52	4.02 12.73 796.82	OOM OOM OOM	0.10 0.32 0.80 11 745 679 0 7 188 0 94 156 0	OOM OOM OOM
		0.05 10 4 114 357 067 18 342 468	OOM 114 345 005	40 229	OOM 2 352.14 2 645.06	OOM	1.07 57 152 804 0

k-patterns instance. A promising road to discover useful patterns is to impose constraints on a set of k related patterns (k-pattern sets)

[START_REF] Guns | k-pattern set mining under constraints[END_REF][START_REF] Khiari | Constraint programming for mining n-ary patterns[END_REF]

. In this setting, the interest of a pattern is evaluated w.r.t. a set of patterns. We propose to model and solve a particular instance, coined dist_kpatterns_lb_ub. Here, we aim at finding k closed patterns {P 1 , . . . , P k } s.t: (i) ∀i ∈ [1, k] : ClosedPattern(P i ) (Closed Frequent Patterns), (ii)∀i, j ∈ [1, k] : P i ∩ P j = ∅ (all distinct patterns constraints), (iii) ∀i ∈ [1, k] : lb < |P i | < ub (min and max size constraints).

For the sake of readability, our examples refer to items by their names instead of their indices.

Value between . indicates the frequency of a pattern.

https://developers.google.com/optimization/

http://fimi.ua.ac.be/data/

http://research.nii.ac.jp/~uno/codes.htm

https://dtai.cs.kuleuven.be/CP4IM/