OpenMP based parallel set containtment query algorithm

Set containment query is important in many fields and can be divided into three parts:subset query,equality query and superset query.With the increasing scale of set data,it is urgent to accelerate set containment query.Parallel set containment query is the way to solve this problem.In this paper three parallel set containment query algorithms are proposed based on OpenMP.These algorithms use inverted indexes as underlying structure and execute queries in parallel by paralleling for-cycles.To improve the efficiency of these algorithms,two efficient parallel data structures,PVEC and CountArr,are designed.PVEC is used to store the query results and CountArr is designed for set superset query to count the elements in related inverted lists.Each thread access disjoint part of these two structures and all threads run in parallel asynchronously.Experiments are carried out on two real datasets,MSWEB and DBLP,the results show that the three algorithms can achieve a speedup more than 4X over corresponding serial algorithms on MSWEB dataset.