Negative Sequence Analysis: A Review

Wei Wang and Longbing Cao, ACM Computing Surveys

Negative sequential patterns (NSPs) produced by negative sequence analysis (NSA) capture more informative
and actionable knowledge than classic positive sequential patterns (PSPs) due to involving both occurring and
non-occurring items, which appear in many applications. However, the research on NSA is still at an early stage
and NSP mining involves very high computational complexity and a very large search space, there is no widely
accepted problem statement on NSP mining, and different settings on constraints and negative containment
have been proposed in existing work. Among existing NSP mining algorithms, there are no general and
systemic evaluation criteria available to assess them comprehensively. This paper conducts a comprehensive
technical review of existing NSA research. We explore and formalize a generic problem statement of NSA,
investigate, compare and consolidate the definitions of constraints and negative containment, and compare the
working mechanisms and efficiency of existing NSP mining algorithms. The review is concluded by discussing
new research opportunities in NSA.

Download the main paper and the Supplementary.