Mining Tree-Structured Data on Multicore Systems

Free registration required

Executive Summary

Mining frequent subtrees in a database of rooted and labeled trees is an important problem in many domains, ranging from phylogenetic analysis to biochemistry and from linguistic parsing to XML data analysis. In this paper the authors revisit this problem and develop an architecture conscious solution targeting emerging multicore systems. Specifically they identify a sequence of memory related optimizations that significantly improve the spatial and temporal locality of a state-of-the-art sequential algorithm - alleviating the effects of memory latency. Additionally, these optimizations are shown to reduce the pressure on the front-side bus, an important consideration in the context of large-scale multicore architectures.

  • Format: PDF
  • Size: 509.3 KB