Frequent Items Mining Acceleration Exploiting Fast Parallel Sorting on the GPU

• Tweet

• Tweet

In this paper, authors show how to employ Graphics Processing Units (GPUs) to provide an efficient and high performance solution for finding frequent items in data streams. They discuss several design alternatives and present an implementation that exploits the great capability of graphics processors in parallel sorting. Authors provide an exhaustive evaluation of performances, quality results and several design trade-offs. On an-off-the-shelf GPU, the fastest of our implementations can process over 200 million items per second, which is better than the best known solution based on Field Programmable Gate Arrays (FPGAs) and CPUs. Moreover, in previous approaches, performances are directly related to the skewness of the input data distribution, while in our approach, the high throughput is independent from this factor.

Conclusions
We implemented on GPU an algorithm for finding frequent items in data streams and gave an experimental comparison of its behavior with respect to SpaceSaving algorithm. We observed that our implementation GPUSB offers in general better performances. In particular, as the number of items is large enough to saturate the GPU resources, our approach has a clear speed-up over a parallel implementation of the SpaceSaving. The trade-off in using large amount of GPU memory is that the result is not affected by the skewness of the data distribution as in the case of SpaceSaving which in the case of low skew demonstrated the greater gap. Furthermore, the obtained result is valid without take into account the time to join the output of each concurrent thread in the parallel implementation of SpaceSaving. From the point of view of quality results, our approach is comparable with SpaceSaving and in same case, the relative error is slightly better.

Ugo Erra, Bernardino Frola, Frequent Items Mining Acceleration Exploiting Fast Parallel Sorting on the GPU, Procedia Computer Science, Volume 9, 2012, Pages 86-95; [DOI: 10.1016/j.procs.2012.04.010].

Tags: CUDA, data mining, GPU, streaming algorithm

Category: Articles, Computer Science