Efficiency Analysis of ASP Encodings for Sequential Pattern Mining Tasks

Thomas Guyet 1, 2 Yves Moinard 2 René Quiniou 2 Torsten Schaub 3, 2
2 LACODAM - Large Scale Collaborative Data Mining
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : This article presents the use of Answer Set Programming (ASP) to mine sequential patterns. ASP is a high-level declarative logic programming paradigm for high level encoding combinatorial and optimization problem solving as well as knowledge representation and reasoning. Thus, ASP is a good candidate for implementing pattern mining with background knowledge, which has been a data mining issue for a long time. We propose encodings of the classical sequential pattern mining tasks within two representations of embeddings (fill-gaps vs skip-gaps) and for various kinds of patterns: frequent, constrained and condensed. We compare the computational performance of these encodings with each other to get a good insight into the efficiency of ASP encodings. The results show that the fill-gaps strategy is better on real problems due to lower memory consumption. Finally, compared to a constraint programming approach (CPSM), another declarative programming paradigm, our proposal showed comparable performance.
Complete list of metadatas

https://hal.inria.fr/hal-01631879
Contributor : Thomas Guyet <>
Submitted on : Monday, November 13, 2017 - 5:01:06 PM
Last modification on : Friday, September 13, 2019 - 9:49:21 AM
Long-term archiving on : Wednesday, February 14, 2018 - 12:34:09 PM

Identifiers

  • HAL Id : hal-01631879, version 1
  • ARXIV : 1711.05090

Citation

Thomas Guyet, Yves Moinard, René Quiniou, Torsten Schaub. Efficiency Analysis of ASP Encodings for Sequential Pattern Mining Tasks. Bruno Pinaud; Fabrice Guillet; Bruno Cremilleux; Cyril de Runz. Advances in Knowledge Discovery and Management, 7, Springer, pp.41--81, 2017, 978-3-319-65405-8. ⟨hal-01631879⟩

Share

Metrics

Record views

562

Files downloads

151