EFFICIENT IMPLEMENTATION OF PROGRESSIVE SEQUENTIAL PATTERN MINING ON CUDA

Abstract

Sequence pattern mining extracts frequent patterns from a sequential database. The progressive sequential pattern mining algorithm introduces the concept of period of interest which helps in deleting obsolete data as well as adding new data to the database in the given window of interest and thus fmds most recent frequent items. It has many applications such as online link recommendation system, data prefetching, stock market analysis to name a few. New algorithms have been developed for progressive mining in the recent years. With the increasing amount of data, execution time of these algorithms on single processor is very large and it suffers from scalability issues. In the recent years Graphic Processor Unit has evolved as a highly parallel, multithreaded, manycore processor with tremendous computational power. So, to address the issues of running time and scalability, NVIDIA's CUDA framework is investigated here as a low-cost, high performance solution. In this Dissertation, I aim to parallelize progressive sequential pattern mining on CUDA framework. The design involves tasks to add new items, remove obsolete items, find current candidate patterns and discover frequent sequential patterns within each period of interest progressively. I discussed here various challenges that I faced and introduced an efficient implementation for Parallel design. Experiments are conducted to verify performance of the proposed scheme with synthetic and real datasets having different characteristics. The results show that the scheme overcomes running time issue of progressive pattern mining. Finally the thesis is concluded by pointing out possible future advancements and uses of parallel model