Accelerating Itemset Sampling using Satisfiability Constraints on FPGA

Mael Gueguen 1 Olivier Sentieys 1 Alexandre Termier 2
1 CAIRN - Energy Efficient Computing ArchItectures with Embedded Reconfigurable Resources
Inria Rennes – Bretagne Atlantique , IRISA-D3 - ARCHITECTURE
2 LACODAM - Large Scale Collaborative Data Mining
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : Finding recurrent patterns within a data stream is important for fields as diverse as cybersecurity or e-commerce. This requires to use pattern mining techniques. However, pattern mining suffers from two issues. The first one, known as “pattern explosion”, comes from the large combinatorial space explored and is the result of too many patterns outputed to be analyzed. Recent techniques called output space sampling solve this problem by outputing only a sampled set of all the results, with a target size provided by the user. The second issue is that most algorithms are designed to operate on static datasets or low throughput streams. In this paper, we propose a contribution to tackle both issues, by designing an FPGA accelerator for pattern mining with output space sampling. We show that our accelerator can outperform a state-of-the-art implementation on a server class CPU using a modest FPGA product.
Complete list of metadatas

https://hal.inria.fr/hal-01941862
Contributor : Olivier Sentieys <>
Submitted on : Sunday, December 2, 2018 - 5:10:00 PM
Last modification on : Friday, September 13, 2019 - 9:49:43 AM
Long-term archiving on : Sunday, March 3, 2019 - 1:47:29 PM

File

main.pdf
Files produced by the author(s)

Identifiers

Citation

Mael Gueguen, Olivier Sentieys, Alexandre Termier. Accelerating Itemset Sampling using Satisfiability Constraints on FPGA. DATE 2019 - 22nd IEEE/ACM Design, Automation and Test in Europe, Mar 2019, Florence, Italy. pp.1046-1051, ⟨10.23919/DATE.2019.8714932⟩. ⟨hal-01941862⟩

Share

Metrics

Record views

595

Files downloads

127