| Autor: |
Wang, Xin, Lan, Zhuo, He, Yu-Ang, Wang, Yang, Liu, Zhi-Gui, Xie, Wen-Bo |
| Rok vydání: |
2022 |
| Předmět: |
|
| Zdroj: |
Expert Systems with Applications, Volume 202, 15 September 2022 |
| Druh dokumentu: |
Working Paper |
| DOI: |
10.1016/j.eswa.2022.117262 |
| Popis: |
Nowadays, frequent pattern mining (FPM) on large graphs receives increasing attention, since it is crucial to a variety of applications, e.g., social analysis. Informally, the FPM problem is defined as finding all the patterns in a large graph with frequency above a user-defined threshold. However, this problem is nontrivial due to the unaffordable computational and space costs in the mining process. In light of this, we propose a cost-effective approach to mining near-optimal top-k patterns. Our approach applies a "level-wise" strategy to incrementally detect frequent patterns, hence is able to terminate as soon as top-k patterns are discovered. Moreover, we develop a technique to compute the lower bound of support with smart traverse strategy and compact data structures. Extensive experimental studies on real-life and synthetic graphs show that our approach performs well, i.e., it outperforms traditional counterparts in efficiency, memory footprint, recall and scalability. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
