Mining Tree-Structured Data on Multicore Systems

Shirish Tatikonda, Srinivasan ParthasarathyPVLDB 2009 · DOI

TL;DR

This paper tackles the challenge of efficiently mining frequent subtrees from large tree-structured datasets on modern multicore processors. They introduce memory-conscious optimizations and an adaptive parallelization strategy that significantly reduces memory usage and boosts performance, achieving near-perfect parallel efficiency on up to 16 cores.

What Problem Does This Paper Address?

The paper addresses the growing need for efficient algorithms to mine tree-structured data, which is prevalent in domains like bioinformatics (RNA structures), web log analysis, and natural language processing. Traditional tree mining algorithms, while effective on single-core systems, struggle on multicore architectures due to their high memory footprints and inefficient handling of memory latency. This leads to poor scalability and performance on modern hardware. The authors specifically aim to overcome the limitations of existing algorithms by developing an architecture-conscious solution that leverages the parallelism and memory hierarchy of multicore systems.

Methods

The core of the paper lies in two main contributions: memory optimizations and an adaptive parallelization framework.

Memory Optimizations: * On-the-fly Embedding Lists (NOEM): Instead of storing large embedding lists (which track subtree matches), this technique dynamically constructs them as needed and then de-allocates them. This significantly reduces memory usage. * Tree Matching Optimizations (LF, DOM, SIMUL): These techniques optimize the process of finding subtree matches within a tree. * Label Filtering (LF): Prunes irrelevant nodes from trees before matching. * Dominant Match Processing (DOM): Avoids redundant backtracking in the matching process. * Simultaneous Matching (SIMUL): Combines subsequence and structural matching to detect false positives earlier. * Computation Chunking (CHUNK): This approach eliminates explicit lists by reorganizing computation. It groups matches into "chunks" and processes them efficiently, improving cache locality and reducing working set size. This forms the basis of their Memory Conscious Trips (MCT) algorithm.

Adaptive Parallelization Framework: * Multi-level Work Sharing: The authors propose a framework that adaptively modulates the type and granularity of work shared among threads. This includes: * Task-parallel: Divides work based on equivalence classes or individual patterns. * Data-parallel: Parallelizes the mining of a single pattern across different trees in its projected database. * Chunk-parallel: Parallelizes the mining of a pattern within a single tree at the chunk level. * Adaptive Strategies (AdP, HyP): They introduce adaptive task partitioning (AdP) and a hybrid approach (HyP) that dynamically switches between these parallelization modes based on workload and available resources. * Scheduling Service: A general-purpose scheduling service is developed to manage job pools and facilitate adaptive scheduling across different granularities.

Datasets

The authors evaluated their algorithms on two real-world datasets:

  • Treebank (TB): Derived from computational linguistics.
  • Cslogs (CS): Derived from web usage mining.

These datasets are characterized by their number of trees and average tree size. The paper notes that TB has a deep recursive structure, while CS exhibits high variance in label frequencies.

Key Insights and Ideas

  • Memory is King on Multicores: The paper strongly emphasizes that for efficient parallel tree mining on multicore systems, reducing memory footprint and managing memory latency are paramount. Traditional algorithms that trade space for time become a bottleneck.
  • Dynamic vs. Static Data Structures: The shift from static, large data structures (like embedding lists) to dynamic, on-the-fly computation is crucial for scalability.
  • Adaptive Granularity is Essential: No single parallelization strategy works best for all scenarios. An adaptive approach that can dynamically switch between task, data, and chunk parallelism is key to achieving high efficiency across diverse workloads.
  • Chunking for Cache Locality: The "Computation Chunking" optimization is highlighted as particularly effective in improving cache performance and reducing working set size, which is critical for multicore architectures.
  • General Purpose Scheduling Service: The development of a flexible scheduling service that supports adaptive and moldable algorithms is a significant outcome, with potential applications beyond tree mining.

Key Results

  • Memory Reduction: The memory optimizations (especially CHUNK) reduced memory usage by up to 366-folds compared to the baseline (Trips).
  • Runtime Improvement: The optimized MCT algorithm achieved up to a 4-fold improvement in runtime compared to the baseline.
  • Parallel Efficiency: Near-perfect parallel efficiency was achieved on up to 16 processors, with speedups of 7.85-folds on a dual quad-core system and 15.5-folds on a 16-processor SMP system.
  • Comparison with Existing Algorithms: MCT significantly outperformed TreeMiner and iMB3-T in terms of both memory usage and runtime, with TreeMiner and iMB3-T often aborting due to excessive memory consumption or taking prohibitively long times.
  • Cache Performance: Optimizations led to substantial improvements in cache performance, with CHUNK improving L1 misses by a factor of 1,442.
  • Bandwidth Pressure: The optimizations resulted in more uniform and smaller memory requests, reducing pressure on the front-side bus.

Limitations and Future Work

  • Out-of-Core Performance: The paper acknowledges that the out-of-core performance of their optimizations was not extensively evaluated due to space limitations. They suggest that their memory optimizations would translate to good out-of-core implementations, with chunking playing an even larger role.
  • Cluster Systems: The current implementation is limited to CMPs and SMPs, and the authors plan to extend the scheduling service for cluster systems.
  • Portability: While they used pthreads, they plan to implement the service on top of Intel's TBB and other related libraries for better portability.
  • Further Exploration of Scheduling: The paper mentions exploring more sophisticated out-of-core algorithms and leveraging hash-based data placement.

Summary updated

BibTeX
@article{tatikonda2009mining,
  author = {Shirish Tatikonda and Srinivasan Parthasarathy},
  title = {{Mining Tree-Structured Data on Multicore Systems}},
  journal = {Proc. VLDB Endow.},
  year = {2009},
  doi = {10.14778/1687627.1687706},
}

Loading related content...

Figure