Parallel Formulations of Tree-Projection Based Sequence Mining Algorithms
2003-01-20
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Parallel Formulations of Tree-Projection Based Sequence Mining Algorithms
Authors
Published Date
2003-01-20
Publisher
Type
Report
Abstract
Discovery of sequential patterns is becoming increasingly useful and essential in many scientific and commercialdomains. Enormous sizes of available datasets and possibly large number of mined patterns demand efficient,scalable, and parallel algorithms. Even though a number of algorithms have been developed to efficiently parallelizefrequent pattern discovery algorithms that are based on thecandidate-generation-and-counting framework, theproblem of parallelizing the more efficient projection-based algorithms has received relatively little attention and existing parallel formulations have been targeted only toward shared-memory architectures. The irregular and unstructured nature of the task-graph generated by these algorithms and the fact that these tasks operate on overlapping sub-databases makes it challenging to efficiently parallelize these algorithms on scalable distributed-memory parallel computing architectures. In this paper we present and study a variety of distributed-memory parallel algorithms for a tree-projection-based frequent sequence discovery algorithm that are able to minimize the various overheads associated with load imbalance, database overlap, and interprocessor communication. Our experimental evaluation on a32 processor IBM SP show that these algorithms are capable of achieving good speedups, substantially reducing theamount of the required work to find sequential patterns in large databases.
Keywords
Description
Related to
Replaces
License
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Guralnik, Valerie; Karypis, George. (2003). Parallel Formulations of Tree-Projection Based Sequence Mining Algorithms. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/215546.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.