Mining Popular Patterns: A Novel Mining Problem and Its Application to Static Transactional Databases and Dynamic Data Streams

摘要

Since the introduction of the frequent pattern mining problem, researchers have extended frequent patterns to different useful patterns such as cyclic, emerging, periodic and regular patterns. In this paper, we (ⅰ) introduce popular patterns, which capture the popularity of individuals, items, or events among their peers or groups. Moreover, we also propose (ⅱ) the Pop-tree structure to capture the essential information from transactional databases and (ⅲ) the Pop-growth algorithm for mining popular patterns from the Pop-tree. Moreover, we illustrate how our algorithm (ⅳ) mines popular friends from social networks. As we are not confined to mining popular patterns from static transactional databases, we extend our work to mining popular patterns from dynamic data streams. Specifically, we propose (ⅴ) the Pop-stream structure to capture the popular patterns in batches of data streams and (ⅵ) the Pop-streaming algorithm for mining popular patterns from the Pop-stream structure. Experimental results showed that (ⅰ) our proposed tree structure is compact and space efficient and (ⅱ) our proposed algorithm is time efficient in mining popular patterns from static transactional databases and dynamic data streams.