Scaling up cosine interesting pattern discovery: A depth-first method

This paper presents an efficient algorithm called CosMiner_t for interesting pattern discovery. The widely used cosine similarity, found to possess the null-invariance property and the anti-cross-support-pattern property, is adopted as the interestingness measure in CosMiner_t. CosMiner_t is generally an FP-growth-like depth-first traversal algorithm that rests on an important property of the cosine similarity: the conditional anti-monotone property (CAMP). The combined use of CAMP and the depth-first support-ascending traversal strategy enables the pre-pruning of uninteresting patterns during the mining process of CosMiner_t. Extensive experiments demonstrate the high efficiency of CosMiner_t in interesting pattern discovery, in comparison to the breath-first strategy and the post-evaluation strategy. In particular, CosMiner_t shows its capability in suppressing the generation of cross-support patterns and discovering rare but truly interesting patterns. Finally, an interesting case of landmark recognition is presented to illustrate the value of cosine interesting patterns found by CosMiner_t in real-world applications.