SHrimp: Descriptive Patterns in a Tree

Sibylle Hess, Nico Piatkowski, Katharina MorikLWA 2014 · OpenReview

Abstract

Descriptive pattern mining aims to identify a small, non-redundant set of patterns that best characterize a dataset. While the Minimum Description Length (MDL) principle provides a robust framework for this task, existing algorithms like KRIMP suffer from significant computational bottlenecks due to repeated database scans. This paper introduces SHrimp, which utilizes a novel hierarchical data structure called the SH-tree to capture pattern dependencies. By enabling local updates and avoiding exhaustive scans, SHrimp achieves orders-of-magnitude speedups on dense datasets.

Introduction

In data mining, the "pattern explosion" problem occurs when traditional frequent pattern mining algorithms generate millions of redundant results. To filter these into a human-interpretable summary, researchers use the Minimum Description Length (MDL) principle. The goal is to find a "code table" (a set of patterns) that minimizes the total length of the compressed database and the model itself.

The KRIMP algorithm is a well-known implementation of this principle, but its performance degrades on large or dense datasets. Every time KRIMP evaluates a candidate pattern, it must re-encode the entire database to check for improvements in compression. SHrimp addresses this by replacing the flat database representation with a specialized tree structure that tracks the state of the encoding dynamically.

The SH-tree Methodology

The core of SHrimp is the SH-tree, a structure inspired by the FP-tree but designed specifically for MDL-based selection. Instead of storing individual items in nodes, the SH-tree stores sets of items that represent potential patterns.

Mapping transactions to cover sets.

As shown in the table above, each transaction is decomposed into a "cover set" based on the current patterns in the code table. These cover sets are then inserted into the SH-tree.

The SH-tree data structure.

The SH-tree (illustrated above) maintains the frequency of these sets across the database. A key innovation is the distinction between active and inactive items. Active items are those currently contributing to the compression, while inactive items are redundant. When a new candidate pattern is considered, SHrimp performs a depth-first search on the tree to identify only the affected branches. This allows it to calculate "usage" changes locally, bypassing the need for a full database scan.

Performance and Insights

The authors evaluated SHrimp against KRIMP across various benchmarks. The results highlight a "density dividend":

  • Massive Speedups: On dense datasets like Connect and Chess, SHrimp was orders of magnitude faster. While KRIMP's runtime increased exponentially with the number of candidates, SHrimp's performance remained relatively stable.
  • Efficiency in Overlap: SHrimp excels when datasets contain many overlapping patterns, as the tree structure naturally compresses these redundancies.
  • Sparse Data Overhead: For small or sparse datasets like Tic-tac-toe, the overhead of maintaining the SH-tree structure can make SHrimp slower than simpler bit-vector approaches.

Conclusion

SHrimp demonstrates that hierarchical data structures can significantly optimize MDL-based pattern selection. By shifting the computational burden from global database scans to local tree updates, it makes descriptive mining feasible for large-scale, dense data. Future work includes adapting the SH-tree for other algorithms like SLIM and exploring its use for providing immediate, human-readable dataset summaries.

Summary updated

BibTeX
@inproceedings{hess2014shrimp,
  author = {Sibylle Hess and Nico Piatkowski and Katharina Morik},
  title = {{SHrimp: Descriptive Patterns in a Tree}},
  booktitle = {LWA},
  year = {2014},
  url = {https://openreview.net/forum?id=tunqwA2ccPT},
}
Figure