CAP Researchers won the Best Paper Award for work on Sequential Pattern Mining at the ACM Computing Frontiers Conference
The Center for Automata Processing (CAP) continues its excellence in research exploration of novel applications of the automata computing paradigm. Led by Research Scientist Ke Wang and Graduate Research Assistant Elaheh Sadredini, the CAP team successfully implemented sequential pattern mining on Micron’s Automata Processor with impressive results.
Sequential pattern mining (SPM) is a widely used data mining technique for discovering common sequences of events in large databases. When compared with the simple set mining problem and string mining problem, the hierarchical structure and the resulting large permutation space makes SPM extremely expensive on conventional processor architectures. CAP researchers propose a hardware acceleration solution of the SPM using Micron’s Automata Processor (AP). The Generalized Sequential Pattern (GSP) algorithm for SPM searching exposes massive parallelism, and is therefore well-suited for AP acceleration. When compared with the optimized multicore CPU and GPU GSP implementations, up to 90X and 29X speedups are achieved by the AP-accelerated GSP on six real-world datasets. The AP-accelerated solution also outperforms the state-of-the-art PrefixSpan and SPADE algorithms on multicore CPU by up to 452X and 49X speedups. The AP advantage grows further with larger datasets.
CAP’s research contribution is recognized by the Association for Computing and Machinery (ACM) International Conference on Computing Frontiers (SC 2016) with the Best Paper Award. An authors’ version of the paper can be found at the CAP website (www.cap.virginia.edu). Official version of the paper can be found at the ACM digital library.
Congratulations to Ke Wang and Elaheh Sadredini for an honor well deserved!!!