Intersecting two families of sets on the GPU

Abstract

The computation of the intersection family of two large families of unsorted sets is an interesting problem from the mathematical point of view which also appears as a subproblem in decision making applications related to market research or temporal evolution analysis problems. The problem of intersecting two families of sets F and F′ is to find the family I of all the sets which are the intersection of some set of F and some other set of F′. In this paper, we present an efficient parallel GPU-based approach, designed under CUDA architecture, to solve the problem. We also provide an efficient parallel GPU strategy to summarize the output by removing the empty and duplicated sets of the obtained intersection family, maintaining, if necessary, the sets frequency. The complexity analysis of the presented algorithm together with experimental results obtained with its implementation is also presented