Current Approximate Graph Pattern Mining (AGPM) systems rely on uniform and static sampler allocation strategies, which result in significant computational redundancy because most regions of the sampling space contribute little to the final estimate. However, existing systems overlook this critical characteristic and fail to account for the hierarchical memory architecture of modern servers, leading to slow convergence and substantial memory access overhead. To address these challenges, we propose HierMine, a novel AGPM system designed to overcome the aforementioned drawbacks. The core contributions of HierMine include: (i) a hierarchical sampling strategy that minimizes redundant computation and accelerates convergence; (ii) a dynamic sampling adjustment mechanism that partitions the sampling space online and reallocates samplers adaptively to enhance the hierarchical strategy; (iii) an online grouping-based convergence detection technique that enables the fine-grained dynamic sampling adjustment mechanism; and (iv) a hierarchical data layout optimized for memory access efficiency. Extensive experiments show that HierMine delivers an average speedup of up to 28.9 × over state-of-the-art AGPM systems such as ScaleGPM, while maintaining strong theoretical guarantees on estimation quality. It also consistently outperforms exact graph pattern mining systems, highlighting the practical benefits of our approximate approach.
Wu et al. (Mon,) studied this question.