Skip to main content
SpringerLink
Log in

New Methods for Compressing Table Constraints

  • Chapter
  • First Online:
Advances in Knowledge Discovery and Management

Part of the book series: Studies in Computational Intelligence ((SCI,volume 1110))

  • 47 Accesses

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, these constraints admit practical boundaries because of the memory space required to represent them which may grow exponentially with their arity. To reduce space complexity, researchers have focused on various forms of compression. In this paper we propose two approaches for compressing table constraints. The first one called FPTCM+ (FP-Tree Compression Method+) is an improvement of an existing method, it exploits the compression rate metric instead of the savings that can be offered by an itemset to enumerate the frequent itemsets relevant for compression. The second approach, called IFPTCM+, is an improvement of FPTCM+ such that it exploits the top-k approach mining method to dynamically choose the value of the minimum threshold Smin. This allows higher compression rate with lesser frequent itemsets by identifying only the more frequent itemsets relevant for compression. Experimental results show the effectiveness and efficiency of our approaches.

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 129.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 169.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Downloaded from https://www.cril.univ-artois.fr/~lecoutre/benchmarks.

  2. 2.

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

  3. 3.

    A frequent super-itemset of u is obtained by adding to u a frequent item ei such that ei ∉ u and ei is the label of the edge from u to its child in the FP-Tree.

  4. 4.

    Data sets are available at https://www.cril.univ-artois.fr/~lecoutre/benchmarks.

  5. 5.

    Solver available at https://bitbucket.org/oscarlib/oscar/src/dev/.

References

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

    Google Scholar 

  2. Bayardo Jr RJ (1998) Efficiently mining long patterns from databases. In: Proceedings of the 1998 ACM SIGMOD international conference on management of data, pp 85–93

    Google Scholar 

  3. 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

    Google Scholar 

  4. Bessière C, Régin J (1997) Arc consistency for general constraint networks: preliminary results. In: Proceedings of the fifteenth international joint conference on artificial intelligence, IJCAI 97, Nagoya, Japan, August 23–29, 1997, 2 vols. Morgan Kaufmann, pp 398–404

    Google Scholar 

  5. Bessière C, Régin J, Yap RHC, Zhang Y (2005) An optimal coarse-grained arc consistency algorithm. Artif Intell 165(2):165–185

    Article  MathSciNet  Google Scholar 

  6. Boulicaut J-F, Bykowski A, Rigotti C (2003) Free-sets: a condensed representation of Boolean data for the approximation of frequency queries. Data Min Knowl Disc 7(1):5–22

    Article  MathSciNet  Google Scholar 

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

    Google Scholar 

  8. Gharbi N, Hemery F, Lecoutre C, Roussel O (2014) Sliced table constraints: combining compression and tabular reduction. In: International conference on AI and OR techniques in constraint programming for combinatorial optimization problems. Springer, pp 120–135

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  11. Jabbour S, Roussel S, Sais L, Salhi Y (2015) Mining to compress table constraints. In: 2015 IEEE 27th International conference on tools with artificial intelligence (ICTAI). IEEE, pp 405–412

    Google Scholar 

  12. Jefferson C, Nightingale P (2013) Extending simple tabular reduction with short supports. In: Rossi F (ed) IJCAI 2013, Proceedings of the 23rd international joint conference on artificial intelligence, Beijing, China, August 3–9, 2013. IJCAI/AAAI, pp 573–579

    Google Scholar 

  13. Katsirelos G, Walsh T (2007) A compression algorithm for large arity extensional constraints. In: International conference on principles and practice of constraint programming. Springer, pp 379–393

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  17. Mairy J, Deville Y, Lecoutre C (2015) The smart table constraint. In: Michel L (ed) Integration of AI and OR techniques in constraint programming—12th international conference, CPAIOR 2015, Barcelona, Spain, May 18–22, 2015, Proceedings, vol 9075. Lecture notes in computer science. Springer, pp 271–287

    Google Scholar 

  18. Mairy J-B, Deville Y, Lecoutre C (2015) The smart table constraint. In: International conference on AI and OR Techniques in constraint programming for combinatorial optimization problems. Springer, pp 271–287

    Google Scholar 

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

    Google Scholar 

  20. Mohr R, Masini G (1988) Good old discrete relaxation. In: Kodratoff Y (ed) 8th European conference on artificial intelligence, ECAI 1988, Munich, Germany, August 1–5, 1988, Proceedings. Pitmann Publishing, London, pp 651–656

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  23. Perez G, Régin J (2014) Improving GAC-4 for table and MDD constraints. In: O’Sullivan B (ed) Principles and practice of constraint programming—20th international conference, CP 2014, Lyon, France, September 8–12, 2014. Proceedings, vol 8656. Lecture notes in computer science. Springer, pp 606–621

    Google Scholar 

  24. Pesant G (2004) A regular language membership constraint for finite sequences of variables. In: Wallace M (ed) Principles and practice of constraint programming—CP 2004, 10th international conference, CP 2004, Toronto, Canada, September 27–October 1, 2004, Proceedings, vol 3258. Lecture notes in computer science. Springer, pp 482–495

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Google Scholar 

  27. Verhaeghe H, Lecoutre C, Deville Y, Schaus P (2017) Extending compact-table to basic smart tables. In: Beck JC (ed) Principles and practice of constraint programming—23rd international conference, CP 2017, Melbourne, VIC, Australia, August 28–September 1, 2017, Proceedings, vol 10416. Lecture notes in computer science. Springer, pp 297–307

    Google Scholar 

  28. Verhaeghe H, Lecoutre C, Schaus P (2017) Extending compact-table to negative and short tables. In: Singh SP, Markovitch S (eds) Proceedings of the thirty-first AAAI conference on artificial intelligence, February 4–9, 2017, San Francisco, California, USA. AAAI Press, pp 3951–3957

    Google Scholar 

  29. Wang R, Xia W, Yap RHC, Li Z (2016) Optimizing simple tabular reduction with a bitwise representation. In: Kambhampati S (ed) Proceedings of the twenty-fifth international joint conference on artificial intelligence, IJCAI 2016, New York, NY, USA, 9–15 July 2016. IJCAI/AAAI Press, pp 787–795

    Google Scholar 

  30. Xia W, Yap RHC (2013) Optimizing STR algorithms with tuple compression. In: Schulte C (ed) Principles and practice of constraint programming—19th international conference, CP 2013, Uppsala, Sweden, September 16–20, 2013. Proceedings, vol 8124. Lecture notes in computer science. Springer, pp 724–732

    Google Scholar 

  31. Yap RHC, Xia W, Wang R. Generalized arc consistency algorithms for table constraints: a summary of algorithmic ideas

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LIMED—Faculty of Exact Sciences, University of Bejaia, Béjaïa, Algeria

    Soufia Bennai & Kamal Amroun

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

    Samir Loudni

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

Corresponding author

Correspondence to Soufia Bennai .

Editor information

Editors and Affiliations

  1. Paragraphe Laboratory, Paris 8 University, Saint-Denis, France

    Rakia Jaziri

  2. Université Rennes CNRS, IRISA, Lannion CEDEX, France

    Arnaud Martin

  3. MMIP, AgroParisTech, Paris, France

    Antoine Cornuéjols

  4. ICHEC Montgomery, Bruxelles, Belgium

    Etienne Cuvelier

  5. University of Nantes, LS2N, Nantes, France

    Fabrice Guillet

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Bennai, S., Amroun, K., Loudni, S. (2024). New Methods for Compressing Table Constraints. In: Jaziri, R., Martin, A., Cornuéjols, A., Cuvelier, E., Guillet, F. (eds) Advances in Knowledge Discovery and Management. Studies in Computational Intelligence, vol 1110. Springer, Cham. https://doi.org/10.1007/978-3-031-40403-0_1

Download citation

Publish with us

Policies and ethics

Search

Navigation