An Apriori-based Approach for First-Order Temporal Pattern

Abstract

Previous studies on mining sequential patterns have focused on temporal patterns specified by some form of
propositional temporal logic. However, there are some interesting sequential patterns whose specification needs a more expressive formalism, the first-order temporal logic. In this article, we focus on the problem of mining multi-sequential patterns which are first-order temporal patterns (not expressible in propositional temporal logic). We propose two Apriori-based algorithms to perform this mining task. The first one, the PM (Projection Miner) Algorithm adapts
the key idea of the classical GSP algorithm for propositional sequential pattern mining by projecting the first-order
pattern in two propositional components during the candidate generation and pruning phases. The second algorithm,
the SM (Simultaneous Miner) Algorithm, executes the candidate generation and pruning phases without decomposing the pattern, that is, the mining process, in some extent, does not reduce itself to its propositional counterpart. Our extensive experiments shows that SM scales up far better than PM.