EUVIMEDEUVIMED entdecken
Crossref

GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries

Can Lu, Sijin Wang, Wenxuan Deng, Xinyu Li, Yikai Zhang, Jeffrey Xu Yu

Proceedings of the ACM on Management of Data · 04.12.2025 · 3 (6) · 1-26

DOI: 10.1145/3769798 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 05.12.2025. Verfasst von Can Lu und 5 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 57 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Modern large-scale graph processing faces a critical challenge: conventional adjacency lists incur excessive L3 cache misses due to irregular memory access. We introduce GraphTwin, a hybrid graph representation system combining: (1) Cache-optimized k -bit vectors (termed GT-vectors, 64 bits per vertex), where each bit indicates vertex membership in a precomputed independent set; and (2) Memory-resident adjacency lists for exact verification of queries unresolved by GT-vectors. This dual-component design enables 95% of negative edge queries, which are dominant in sparse graphs, to be resolved in 1 CPU cycle via in-cache bitwise-AND operations, reducing latency from 54ns (adjacency list) to 18ns per query. Unresolved queries delegate to adjacency lists, guaranteeing zero false positives/negatives. Crucially, GT-vectors scales linearly with vertex count ( k|V| bits ), decoupling the space overhead from edge density and minimizing cache dependency. For example, GT-vectors for a graph with |V|=10 7 vertices occupy 80MB, fitting entirely within modern CPU caches (e.g., AMD Ryzen 7 9800X3D's 96MB L3). We formalize the GT-vectors construction as an NP-hard and submodular optimization problem and introduce GTWICE, a linear-time heuristic algorithm that iteratively extracts diversified maximal independent sets to maximize non-edge coverage. Experiments on 15 graphs show that GraphTwin reduces L3 cache misses by 63% on average, achieves 6.2× speedup for edge queries and accelerates triangle counting and set inclusion by 1.7× and 5.4×, respectively. By optimizing cache residency and accelerating foundational primitives, GraphTwin addresses cache inefficiencies in graph processing, enabling fast graph queries without sacrificing exactness.

Zitieren

APA

Lu, C., Wang, S., Deng, W., Li, X., Zhang, Y., & Yu, J. X. (2025). GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries. Proceedings of the ACM on Management of Data, 3(6), 1-26. https://doi.org/10.1145/3769798

Vancouver

Lu C, Wang S, Deng W, Li X, Zhang Y, Yu JX. GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries. Proceedings of the ACM on Management of Data. 2025;3(6):1-26. doi:10.1145/3769798

BibTeX
@article{Lu2025,
  author = {Lu, Can and Wang, Sijin and Deng, Wenxuan and Li, Xinyu and Zhang, Yikai and Yu, Jeffrey Xu},
  title = {GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2025},
  volume = {3},
  number = {6},
  pages = {1--26},
  doi = {10.1145/3769798}
}
Kostenlos starten →