H-Mine: Fast and space-preserving frequent pattern mining in large databases

Jian Pei, Jiawei Han, Hongjun Lü, Shojiro Nishio, Shiwei Tang, D. YangIIE 2007 · DOI

TL;DR

This paper introduces H-Mine, a novel frequent pattern mining algorithm that uses a unique hyper-linked data structure (H-struct) to achieve fast and memory-efficient mining. H-Mine significantly outperforms existing methods like Apriori and FP-growth, especially on large and sparse datasets, by offering predictable memory usage and excellent scalability.

What Problem Does This Paper Address?

Frequent pattern mining is a cornerstone of data mining, crucial for tasks like association rule discovery, market basket analysis, and more. However, existing algorithms face significant challenges:

  • Memory Consumption: Algorithms like Apriori can require enormous amounts of memory to store candidate patterns, especially for long or dense patterns. FP-growth, while more memory-efficient, can struggle with very large and sparse datasets due to recursive partitioning and potentially large FP-trees. The memory cost is often hard to predict precisely.
  • Scalability: Many methods perform well on smaller datasets but falter when faced with massive transaction databases, leading to performance degradation or "thrashing" as data exceeds main memory.
  • Data Heterogeneity: Real-world datasets vary greatly in density (sparse vs. dense). A single algorithm that performs optimally across all these scenarios is desirable but difficult to achieve.

The authors aim to develop a mining method that is fast, memory-efficient with predictable costs, and highly scalable across diverse datasets.

Methods

The core innovation of H-Mine lies in its novel data structure, H-struct, and the associated H-mine(Mem) algorithm for in-memory mining.

  • H-struct: This is a hyper-linked data structure designed to store frequent-item projections of transactions. Instead of explicitly building separate projected databases, H-struct organizes these projections using linked entries. A header table points to queues of these projections, where items within a projection are linked to subsequent items. This structure allows for efficient traversal and manipulation without the overhead of creating new databases.
  • H-mine(Mem): This is the in-memory mining algorithm. It first identifies all frequent items and then uses the H-struct to recursively mine for frequent patterns. The key idea is to partition the search space based on a global ordering of frequent items (F-list). For each frequent item x, H-mine(Mem) effectively mines the x-projected database by traversing the corresponding queue in the H-struct. This avoids explicit candidate generation and leverages the hyper-link structure for efficient access.
  • H-mine (for large databases): To handle datasets that don't fit into memory, H-mine extends H-mine(Mem) using a partitioning strategy. The database is divided into smaller partitions, each of which can be processed by H-mine(Mem). Frequent patterns are mined locally within each partition, and then consolidated to find globally frequent patterns. This approach requires at most three scans of the entire database.
  • Dynamic Integration with FP-trees: For dense datasets, H-mine can dynamically switch to using FP-trees. This is based on analyzing the "pattern density" of projected databases. If a projected database is dense, constructing an FP-tree can offer better compression and performance.

Datasets

The paper evaluates H-mine using:

  • Gazelle: A sparse web store visit (clickstream) dataset from Gazelle.com, containing 59,602 transactions with up to 267 items per transaction.
  • T25I15D10k: A synthetic dense dataset generated using the method described by Agrawal and Srikant (1994). It has 10,000 transactions, up to 25 items per transaction, and 1000 items in total.
  • T25I15D1280k: Another synthetic dataset, similar to T25I15D10k but much larger, with 1,280,000 transactions, used to test scalability under memory constraints.

The paper does not introduce new benchmark datasets but uses established synthetic data generation methods and a real-world dataset.

Key Insights and Ideas

  • Space-Preserving Mining: The core concept introduced is "space-preserving mining," where the memory footprint is not only minimized but also precisely predictable. This is a significant departure from algorithms where memory usage can be highly variable and difficult to estimate.
  • H-struct as an Efficient Intermediate Representation: The H-struct cleverly avoids the overhead of creating and managing numerous explicit projected databases. By using hyper-links, it allows for dynamic restructuring and traversal, making it highly efficient for memory-based mining.
  • Predictable Memory Overhead: A key advantage of H-mine is its predictable and often very small memory overhead, primarily consisting of local header tables. This makes it robust for resource-constrained environments.
  • Scalability Through Partitioning and H-struct: The combination of database partitioning and the efficient H-struct enables H-mine to scale effectively to very large datasets, requiring only a few passes over the data.
  • Dynamic Structure Selection: The ability to dynamically integrate FP-tree mining for dense datasets demonstrates a sophisticated approach to adapting to data characteristics, maximizing performance across different scenarios.

Key Results

  • Performance Superiority: H-mine consistently outperformed Apriori and FP-growth in terms of runtime across various datasets and support thresholds. On sparse datasets like Gazelle, it was significantly faster, especially at lower support thresholds. On dense datasets like T25I15D10k, it was also faster, often by a factor of 4-5 compared to FP-growth and over ten times faster than Apriori.
  • Memory Efficiency: H-mine exhibited stable and moderate memory usage, even at very low support thresholds, unlike Apriori whose memory usage scaled exponentially. FP-growth also showed good memory scalability, but H-mine was competitive or better.
  • Scalability: H-mine demonstrated linear scalability with respect to the number of transactions, outperforming Apriori in this regard. Its performance was also shown to be less sensitive to memory limitations than Apriori.
  • Reduced Third Scan Workload: For partition-based mining, H-mine's third scan (for global support verification) had a significantly lighter workload, checking only a limited portion of locally frequent patterns.

Limitations and Future Work

  • Dynamic Integration Nuances: While the paper proposes dynamic integration with FP-trees for dense data, the exact criteria and thresholds for switching between H-struct and FP-tree mining are noted as requiring further investigation, especially in the "gray area" between sparse and dense data.
  • Experimental Setup: The experiments were conducted on a specific hardware configuration (466 MHz Pentium PC, 128 Mb RAM). While the results are compelling, performance might vary on different architectures.
  • Future Work: The authors suggest that the proposed space-preserving mining methodology, exemplified by H-mine, could have a significant impact on the future development of efficient and scalable data mining methods. Further exploration of dynamic structure selection and optimization for various data characteristics is implied.

Summary updated

Abstract

In this study, we propose a simple and novel data structure using hyper-links, H-struct, and a new mining algorithm, H-mine, which takes advantage of this data structure and dynamically adjusts links in the mining process. A distinct feature of this method is that it has a very limited and precisely predictable main memory cost and runs very quickly in memory-based settings. Moreover, it can be scaled up to very large databases using database partitioning. When the data set becomes dense, (conditional) FP-trees can be constructed dynamically as part of the mining process. Our study shows that H-mine has an excellent performance for various kinds of data, outperforms currently available algorithms in different settings, and is highly scalable to mining large databases. This study also proposes a new data mining methodology, space-preserving mining, which may have a major impact on the future development of efficient and scalable data mining methods.
BibTeX
@inproceedings{pei2007h,
  author = {Jian Pei and Jiawei Han and Hongjun Lü and Shojiro Nishio and Shiwei Tang and D. Yang},
  title = {{H-Mine: Fast and space-preserving frequent pattern mining in large databases}},
  booktitle = {IIE},
  year = {2007},
  doi = {10.1080/07408170600897460},
}
Figure