Graphs are continually growing in size, and processing complex queries, such as multi-hop pattern queries, on them is becoming increasingly important. Although GPUs have received significant attention recently, there is still a notable shortage of efficient GPU-based out-of-memory methods for handling these queries. Three key issues arise when processing multi-hop queries on large-scale graphs using GPUs: the need for an efficient graph format, effective scheduling of accesses to graph partitions on storage, and dynamic buffer management on both the host and GPUs. To address these issues, we propose an efficient GPU-based out-of-memory multi-hop query processing framework called GFlux. Through extensive experiments, we have demonstrated that GFlux significantly improves both the speed and scalability compared to existing state-of-the-art methods.

Subgraph queries are widely used but face significant challenges due to complex patterns such as negative and optional edges. While worst-case optimal joins have proven effective for subgraph queries with regular patterns, no method has been proposed that can process queries involving complex patterns in a single multi-way join. Existing CPU-based and GPU-based methods experience intermediate data explosion when processing complex patterns following regular patterns. In addition, GPU-based methods struggle with issues of wasted GPU memory and redundant computation. In this paper, we propose cuMatch, a GPU-based unified worst-case optimal join processing method for subgraph queries. It avoids intermediate data explosions by processing even complex pattern queries in a single multi-way join. It is also memory-efficient and fast, due to a new partitioning format, scheduling method, and task fusion technique. Extensive experiments demonstrate that cuMatch outperforms state-of-the-art methods by orders of magnitude, without out-of-memory errors.

With the introduction of GPUs, which are specialized for iterative parallel computations, the execution of computation-intensive graph queries using a GPU has seen significant performance improvements. However, due to the memory constraints of GPUs, there has been limited research on handling large-scale output graph queries with unpredictable output sizes on a GPU. Traditionally, two-phase methods have been used, where the query is re-executed after splitting it into sub-tasks while only considering the size of the output in a static manner. However, two-phase methods become highly inefficient when used with graph data with extreme skew, failing to maximize the GPU performance. This paper proposes INFINEL, which handles unpredictable large output graph queries in a one-phase method through chunk allocation per thread and kernel stop/restart methods. We also propose applicable optimization techniques due to the corresponding unique characteristics of operating with low time/space overhead and not heavily relying on the GPU output buffer size. Through extensive experiments, we demonstrate that our one-phase method of INFINEL improves the performance by up to 31.5 times over the conventional two-phase methods for triangle listing ULO query.