Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An efficient heuristic approach combining maximal itemsets and area measure for compressing voluminous table constraints

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

Constraint Programming is a powerful paradigm to model and solve combinatorial problems. While there are many kinds of constraints, the table constraint is perhaps the most significant—being the most well-studied and has the ability to encode any other constraints defined on finite variables. However, constraints can be very voluminous and their size can grow exponentially with their arity. To reduce space and the time complexity, researchers have focused on various forms of compression. In this paper, we propose a new approach based on maximal frequent itemsets technique and area measure for enumerating the maximal frequent itemsets relevant for compressing table constraints. Our experimental results show the effectiveness and efficiency of this approach on compression and on solving compressed constraint satisfaction problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Data availability

The Oscar solver is available at https://bitbucket.org/oscarlib/oscar/src/dev/. The Instances used in our experiments to validate the approach can be found at: https://bitbucket.org/pschaus/xp-table/src/master/instances/. The source code of our implementation is available at https://bitbucket.org/pschaus/xp-table/src/master/instances/.

Notes

  1. The area of an itemset is the product of its length and its frequency value.

  2. benchmarks downloaded from https://bitbucket.org/pschaus/xp-table/src/master/instances/.

  3. For an itemset u \(\in\) \({{{\mathcal {L}}}}_{{\mathcal {I}}}\) and a transaction t, \(match(p,t) = true iff p\) covers the transaction t.

References

  1. Pesant G (2004) A regular language membership constraint for finite sequences of variables. In: International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, pp 482–495

  2. Cheng KCK, Yap RHC (2010) An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints. Constraints 15(2):265–304

    Article  MathSciNet  MATH  Google Scholar 

  3. Mohr R, Masini G (1988) Good old discrete relaxation. In: 8th European Conference on Artificial Intelligence (ECAI ’88), Munich, pp 651–656

  4. Bessiere C, Régin J-C (1997) Arc consistency for general constraint networks: preliminary results. In: IJCAI-97. Nagoya, Japan, pp 398–404

    Google Scholar 

  5. Yap RHC, Xia W, Wang R (2020) Generalized arc consistency algorithms for table constraints: a summary of algorithmic ideas. In: Proceedings of the AAAI Conference on Artificial Intelligence, pp 13590–13597

  6. Bessiere C, Régin J-C, Yap RHC et al (2005) An optimal coarse-grained arc consistency algorithm. Artif Intell 165(2):165–185

    Article  MathSciNet  MATH  Google Scholar 

  7. Wang R, Xia W, Yap RHC et al (2016) Optimizing simple tabular reduction with a bitwise representation. In: IJCAI, pp 787.v–795.v

  8. Verhaeghe H, Lecoutre C, Schaus P (2017) Extending compact-table to negative and short tables. In: Thirty-First AAAI Conference on Artificial Intelligence

  9. Ullmann JR (2007) Partition search for non-binary constraint satisfaction. Inf Sci 177(18):3639–3678

    Article  MathSciNet  MATH  Google Scholar 

  10. Lecoutre C (2011) STR2: optimized simple tabular reduction for table constraints. Constraints 16(4):341–371

    Article  MathSciNet  MATH  Google Scholar 

  11. Lecoutre C, Likitvivatanavong C, Yap RHC (2015) STR3: a path-optimal filtering algorithm for table constraints. Artif Intell 220:1–27

    Article  MathSciNet  MATH  Google Scholar 

  12. Mairy J-B, Deville Y, Lecoutre C (2015) The smart table constraint. In: International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Springer, Cham, pp 271–287

  13. Audemard G, Lecoutre C, Maamar M (2020) Segmented tables: an efficient modeling tool for constraint reasoning. In: ECAI 2020. IOS Press, pp 315–322

  14. Katsirelos G, Walsh T (2007) A compression algorithm for large arity extensional constraints. In: International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, pp 379–393

  15. Xia W, Yap RHC (2013) Optimizing STR algorithms with tuple compression. In: International Conference on Principles and Practice of Constraint Programming. Springer, Berlin, pp 724–732

  16. Jefferson C, Nightingale P (2013) Extending simple tabular reduction with short supports. In: Twenty-Third International Joint Conference on Artificial Intelligence

  17. Gharbi N, Hemery F, Lecoutre C et al (2014) Sliced table constraints: combining compression and tabular reduction. In: International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Springer, Cham, pp 120–135

  18. Mairy J-B, Deville Y, Lecoutre C (2015) The smart table constraint. In: International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Springer, Cham, pp 271–287

  19. Verhaeghe H, Lecoutre C, Deville Y et al (2017) Extending compact-table to basic smart tables. In: International Conference on Principles and Practice of Constraint Programming. Springer, Cham, pp 297–307

  20. Jabbour S, Roussel S, Sais L et al (2015) Mining to compress table constraints. In: 2015 IEEE 27th International Conference on Tools with Artificial Intelligence (ICTAI). IEEE, pp 405–412

  21. Bennai S, Amroun K, Loudni S (2019) Exploiting data mining techniques for compressing table constraints. In: 2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI). IEEE, pp 42–49

  22. Montanari U (1974) Networks of constraints: fundamental properties and applications to picture processing. Inf Sci 7:95–132

    Article  MathSciNet  MATH  Google Scholar 

  23. Guns T, Nijssen S, De Raedt L (2011) Itemset mining: a constraint programming perspective. Artif Intell 175(12–13):1951–1983

    Article  MathSciNet  MATH  Google Scholar 

  24. Han J, Pei J, Yin Y (2000) Mining frequent patterns without candidate generation. ACM Sigmod Rec 29(2):1–12

    Article  Google Scholar 

  25. Maamar M, Lazaar N, Loudni S et al (2017) Fault localization using itemset mining under constraints. Autom Softw Eng 24(2):341–368

    Article  Google Scholar 

  26. Pasquier N, Bastide Y, Taouil R et al (1999) Discovering frequent closed itemsets for association rules. In: International Conference on Database Theory. Springer, Berlin, pp 398–416

  27. Boulicaut J-F, Artur B,Christophe R (2000) Approximation of frequency queries by means of free-sets. In: European Conference on Principles of Data Mining and Knowledge Discovery. Springer, Berlin

  28. Bayardo Jr. RJ (1998) Efficiently mining long patterns from databases. In: Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data

  29. Mannila H, Toivonen H (1997) Levelwise search and borders of theories in knowledge discovery. Data Min Knowl Discov 1(3):241–258

    Article  Google Scholar 

  30. Pasquier N, Bastide Y, Taouil R et al (1999) Efficient mining of association rules using closed itemset lattices. Inf Syst 24(1):25–46

    Article  Google Scholar 

  31. Ke Y, Cheng J, Yu JX (2009) Top-k correlative graph mining. In: Proceedings of the 2009 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, pp 1038–1049

  32. Wang J, Han J, Lu Y et al (2005) TFP: an efficient algorithm for mining top-k frequent closed itemsets. IEEE Trans Knowl Data Eng 17(5):652–663

    Article  Google Scholar 

  33. Uno T, Kiyomi M, Arimura H et al (2004) LCM ver. 2: Efficient mining algorithms for frequent/closed/maximal itemsets. In: FIMI

  34. Perez G, Régin J-C (2014) Improving GAC-4 for table and MDD constraints. In: International Conference on Principles and Practice of Constraint Programming. Springer, Cham, pp 606–621

  35. Verhaeghe H, Lecoutre C, Schaus P (2018) Compact-MDD: efficiently filtering (s)MDD constraints with reversible sparse bitsets. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence

  36. Verhaeghe H, Lecoutre C, Deville Y, Schaus P (2017) Extending compact-table to basic smart tables. In: Proceedings of the 23rd International Conference on Principles and Practice of Constraint Programming

  37. Verhaeghe H, Lecoutre C, Schaus P (2017) Extending compact-table to negative and short table. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence, pp 3951–3957

  38. Wang R, Yap RH (2019) Arc consistency revisited. In: Proceedings of the 16th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Springer, pp 599–615

  39. Geerts F, Goethals B, Mielikäinen T (2004) Tiling databases. In: Suzuki E, Arikawa S (eds) Discovery Science. DS 2004. Lecture Notes in Computer Science, vol 3245. Springer, Berlin. https://doi.org/10.1007/978-3-540-30214-8_22

  40. Fleischer R (1994) A tight lower bound for the worst case of bottom–up-heapsort. Algorithmica 11(2):104–115

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This work has been sponsored by the General Directorate for Scientific Research and Technological Development, Ministry of Higher Education and Scientific Research DGRSDT, Algeria.

Author information

Authors and Affiliations

  1. LIMED Laboratory, Faculty of Exact Sciences, University of Bejaia, 06000, Bejaïa, Algeria

    Soufia Bennai & Kamal Amroun

  2. TASC (LS2N-CNRS), IMT Atlantique, 44307, Nantes, France

    Samir Loudni

  3. UNICAEN, ENSICAEN, CNRS, GREYC, Normandy University, 14000, Caen, France

    Abdelkader Ouali

Authors
  1. Soufia Bennai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kamal Amroun
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Samir Loudni
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Abdelkader Ouali
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Soufia Bennai, Kamal Amroun, Samir Loudni or Abdelkader Ouali.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bennai, S., Amroun, K., Loudni, S. et al. An efficient heuristic approach combining maximal itemsets and area measure for compressing voluminous table constraints. J Supercomput 79, 650–676 (2023). https://doi.org/10.1007/s11227-022-04667-1

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-022-04667-1

Keywords

Search

Navigation