Mining Colocation from Big Geo-Spatial Event Data on GPU

Arpan Man Sainju () and Zhe Jiang ()
Additional contact information
Arpan Man Sainju: The University of Alabama, Department of Computer Science
Zhe Jiang: The University of Alabama, Department of Computer Science

Chapter Chapter 10 in Handbook of Big Geospatial Data, 2021, pp 241-259 from Springer

Abstract: Abstract This chapter investigates the colocation pattern mining problem for big spatial event data. Colocation patterns refer to subsets of spatial features whose instances are frequently located together. The problem is important in many applications such as analyzing relationships of crimes or disease with various environmental factors, but is computationally challenging due to a large number of instances, the potentially exponential number of candidate patterns, and high computational cost in generating pattern instances. Existing colocation mining algorithms (e.g., Apriori algorithm, multi-resolution filter, partial join and joinless approaches) are mostly sequential, and thus can be insufficient for big spatial event data. Recently, parallel colocation mining algorithms have been developed based on the Map-reduce framework. However, these algorithms need a large number of nodes to scale up, which is economically expensive, and their reducer nodes have a bottleneck of aggregating all instances of the same colocation patterns. Another work proposes a parallel colocation mining algorithm on GPU based on the iCPI tree and the joinless approach, but assumes that the number of neighbors for each instance is within a small constant, and thus may be inefficient when instances are dense and unevenly distributed. To address these limitations, we introduce a grid-based GPU colocation mining algorithm that includes a cell aggregate based upper bound filter, and two refinement algorithms. We prove the correctness and completes of the GPU algorithms. Experimental results on both real world data and synthetic data show that the GPU algorithms are promising with over 30 times speedup on up to millions of instances.

Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-030-55462-0_10

Ordering information: This item can be ordered from
http://www.springer.com/9783030554620

DOI: 10.1007/978-3-030-55462-0_10

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().