LHGstore: An In-Memory Learned Graph Storage for Fast Updates and Analytics
This addresses the problem of balancing update efficiency and traversal locality for real-world applications with dynamic graphs, representing a novel integration of learned indexing into graph management.
The paper tackles the challenge of efficiently managing in-memory dynamic graphs that require fast updates and low-latency analytics by introducing LHGstore, a learned hierarchical graph storage system that achieves 5.9-28.2× higher throughput and faster analytics than state-of-the-art systems.
Various real-world applications rely on in-memory dynamic graphs that must efficiently handle frequent updates while supporting low-latency analytics on evolving structures. Achieving both objectives remains challenging due to the trade-off between update efficiency and traversal locality, particularly under highly skewed degree distributions. This motivates the design of graph indexing schemes optimized for in-memory graph management on modern multi-core CPUs. We present LHGstore, a degree-aware Learned Hierarchical Graph storage that, for the first time, integrates learned indexing into graph management. LHGstore designs a two-level hierarchy that decouples vertex and edge access and further organizes each vertex's edges using data structures adaptive to its degree. Lightweight arrays are used for low-degree vertices to maximize traversal locality, while learned indexes are applied to high-degree vertices to improve update throughput. Extensive experiments show that LHGstore achieves 5.9-28.2$\times$ higher throughput and significantly faster analytics than SOTA in-memory graph storage systems.