An efficient memoization engine for concurrent graph query processing

Publication Type

Conference Proceeding Article

Publication Date

5-2025

Abstract

Concurrent graph query (CGQ) processing has been used to solve a wide range of graph applications. By analyzing real-world workloads of CGQs, we observe significant repeated computations among the queries. In this work, we present KGraph, a novel graph processing memoization engine to efficiently handle CGQs on large graphs by performing memoization on graphs. However, the efficacy of memoization in optimizing CGQs on large graphs is constrained by substantial computational and memory overheads, coupled with the potential amount of sharing opportunities. Thus, we develop two novel approaches in KGraph to address the memoization overhead. First, we develop a fine-grained memoization method, which only maintains query results within their associated graph partitions. This approach not only reduces the overhead but also enhances the potential for sharing. Secondly, we selectively perform memoization on pivotal queries, those with a high likelihood of promoting substantial computation sharing among CGQs, while avoiding the excessive overhead associated with managing unnecessary memoization across a large number of queries. We comprehensively analyze KGraph's performance using five popular CGQ applications. Experimental results show that our system achieves an average speedup of 4.2× over the state-of-the-art CGQ systems.

Discipline

Databases and Information Systems | Graphics and Human Computer Interfaces

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the 2025 IEEE 41st International Conference on Data Engineering (ICDE), Hong Kong, May 19-23

First Page

1015

Last Page

1028

Identifier

10.1109/ICDE65448.2025.00081

Publisher

IEEE Computer Society

City or Country

Los Alamitos, CA

Additional URL

https://doi.org/10.1109/ICDE65448.2025.00081

This document is currently not available here.

Share

COinS