Efficient K-Clique Listing With Set Intersection Speedup

Listing all k-cliques is a fundamental problem in graph mining,with applications in finance,biology,and social network analysis.However,listing all k-cliques is algorithmically challenging because the search space grows exponentially as k increases.DDegree and DDegCol are the currently state-of-the-art algorithms that utilize vertex oriented techniques based on vertex degree ordering and color ordering for k-clique listing,respectively.Due to the necessity of constructing and maintaining all induced subgraphs,both DDegree and DDegCol produce high time and space overhead for listing k-cliques.In addition,set intersection is the basic operation for solving k-clique listing problems as well as for solving many classical graph algorithms,such as triangle listing,maximal clique enumeration,subgraph matching,etc.With the instruction set architecture of modern computers,data-level parallelism can be used to speed up set intersection.However,further speedup by implementing data-level parallelism on DDegree and DDegCol is difficult to achieve due to the reliance on the construction of induced subgraphs and the set intersection method of hash join.In this thesis,two efficient algorithms SDegree and BitCol are proposed for solving k-clique listing problem,focusing mainly on accelerating set intersection during the process of k-clique listing.SDegree and BitCol exploit single instruction multiple data(SIMD)instruction sets and auto-vectorization,respectively,to obtain data-level parallelism for further speedup.In addition,two preprocessing techniques Pre-Core and Pre-List are proposed running in linear time.The preprocessing techniques shrink the original graph and avoid exploring invalid search space.In the theoretical analysis,the proposed algorithms have comparable time complexity as well as lower space complexity than the baseline algorithms.Comprehensive experiments show that SDegree is on average 3.75 times faster than the baseline algorithm for degree ordering and BitCol is 5.67 times faster for color ordering,reflecting the superiority of the designed algorithms.