A parallel algorithm for building iCPI-trees*

被引：5

作者：

Andrzejewski, Witold ^{[1
]}

Boinski, Pawel ^{[1
]}

机构：

[1] Poznan University of Technology, Institute of Computing Science, Piotrowo 2, Poznan

来源：

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | 2014年 / 8716卷

关键词：

Forestry - Graphics processing unit - Trees (mathematics);

D O I：

10.1007/978-3-319-10933-6_21

中图分类号：

学科分类号：

摘要：

In spatial databases collocation pattern discovery is one of the most interesting fields of data mining. It consists in searching for types of spatial objects that are frequently located together in a spatial neighborhood. With the advent of data gathering techniques, huge volumes of spatial data are being collected. To cope with processing of such datasets a GPU accelerated version of the collocation pattern mining algorithm has been proposed recently [3]. However, the method assumes that a supporting structure that contains information about neighborhoods (called iCPI-tree) is given in advance. In this paper we present a GPU-based version of iCPI-tree generation algorithm for the collocation pattern discovery problem. In an experimental evaluation we compare our GPU implementation with a parallel implementation of iCPI-tree generation method for CPU. Collected results show that proposed solution is multiple times faster than the CPU version of the algorithm. © Springer International Publishing Switzerland 2014.

引用

页码：276 / 289

页数：13

共 19 条

[1]

Agrawal R., Srikant R., Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, pp. 487-499, (1994)

[2]

Alcantara D.A.F., Efficient Hash Tables on the GPU. PhD thesis, (2011)

[3]

Andrzejewski W., Boinski P., GPU-accelerated collocation pattern discovery, ADBIS 2013. LNCS, 8133, pp. 302-315, (2013)

[4]

Bell N., Hoberock J., GPU Computing Gems: Jade edition, chapter Thrust: A Productivity-Oriented Library for CUDA, Morgan-Kauffman, pp. 359-371, (2011)

[5]

Boinski P., Zakrzewicz M., Collocation Pattern Mining in a Limited Memory Environment Using Materialized iCPI-Tree, DaWaK 2012. LNCS, 7448, pp. 279-290, (2012)

[6]

Bress S., Beier F., Rauhe H., Sattler K.-U., Schallehn E., Saake G., Efficient co-processor utilization in database query processing, Information Systems, 38, 8, pp. 1084-1096, (2013)

[7]

De Berg M., Van Kreveld M., Overmars M., Schwarzkopf O., Computational Geometry: Algorithms and Applications, Springer-Verlag New York, Inc., Secaucus, (1997)

[8]

Fang W., Lu M., Xiao X., He B., Luo Q., Frequent itemset mining on graphics processors, Proceedings of the Fifth International Workshop on Data Management on New Hardware, DaMoN 2009, pp. 34-42, (2009)

[9]

Fayyad U., Piatetsky-Shapiro G., Smyth P., From Data Mining to Knowledge Discovery in Databases, AI Magazine, 17, pp. 37-54, (1996)

[10]

He B., Lu M., Yang K., Fang R., Govindaraju N.K., Luo Q., Sander P.V., Relational query coprocessing on graphics processors, ACM Trans. Database Syst, 34, 4, pp. 1-21, (2009)

← 1 2 →