F-NSP+: A fast negative sequential patterns mining method with self-adaptive data storage

作者：

Highlights：

• We propose a novel and efficient data structure, bitmap, to obtain the support of Negative sequential candidates (NSC).

• A fast NSP mining algorithm f-NSP is proposed, which uses bitmap to store the PSP’s information and then obtain the support of NSC only by bitwise operations.

• Given a self-adaptive storage strategy and a corresponding algorithm f-NSP+ to overcome the space-consumption deficiency of f-NSP.

• Results show that f-NSP and f-NSP+ substantially improve the efficiency of e-NSP both in runtime and space cost. f-NSP+ has better space efficiency but slightly longer runtime when min sup is very low.

摘要

•We propose a novel and efficient data structure, bitmap, to obtain the support of Negative sequential candidates (NSC).•A fast NSP mining algorithm f-NSP is proposed, which uses bitmap to store the PSP’s information and then obtain the support of NSC only by bitwise operations.•Given a self-adaptive storage strategy and a corresponding algorithm f-NSP+ to overcome the space-consumption deficiency of f-NSP.•Results show that f-NSP and f-NSP+ substantially improve the efficiency of e-NSP both in runtime and space cost. f-NSP+ has better space efficiency but slightly longer runtime when min sup is very low.

论文关键词：Nonoccurring behavior analysis,Sequential patterns,Negative sequential patterns,Bitmap

论文评审过程：Received 16 December 2016, Revised 23 April 2018, Accepted 25 June 2018, Available online 27 June 2018, Version of Record 6 July 2018.

论文官网地址：https://doi.org/10.1016/j.patcog.2018.06.016