{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:58:31Z","timestamp":1781326711532,"version":"3.54.1"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>\n                    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\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -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\n                    <jats:sup>7<\/jats:sup>\n                    vertices occupy 80MB, fitting entirely within modern CPU caches (e.g., AMD Ryzen 7 9800X3D's 96MB L3).\n                  <\/jats:p>\n                  <jats:p>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\u00d7 speedup for edge queries and accelerates triangle counting and set inclusion by 1.7\u00d7 and 5.4\u00d7, respectively. By optimizing cache residency and accelerating foundational primitives, GraphTwin addresses cache inefficiencies in graph processing, enabling fast graph queries without sacrificing exactness.<\/jats:p>","DOI":"10.1145\/3769798","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-2960-4775","authenticated-orcid":false,"given":"Can","family":"Lu","sequence":"first","affiliation":[{"name":"Guangzhou University, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-1637-9405","authenticated-orcid":false,"given":"Sijin","family":"Wang","sequence":"additional","affiliation":[{"name":"Guangzhou University, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-2606-2076","authenticated-orcid":false,"given":"Wenxuan","family":"Deng","sequence":"additional","affiliation":[{"name":"Guangzhou University, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-4060-0834","authenticated-orcid":false,"given":"Xinyu","family":"Li","sequence":"additional","affiliation":[{"name":"Guangzhou University, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4924-7824","authenticated-orcid":false,"given":"Yikai","family":"Zhang","sequence":"additional","affiliation":[{"name":"Guangzhou University, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9738-827X","authenticated-orcid":false,"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.50"},{"key":"e_1_2_1_3_1","volume-title":"Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations. CoRR abs\/1806.01799","author":"Besta Maciej","year":"2018","unstructured":"Maciej Besta and Torsten Hoefler. 2018. Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations. CoRR abs\/1806.01799 (2018)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3466752.3480133"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3295500.3356182"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300086"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_9_1","unstructured":"Bloom Filter. 2006. https:\/\/code.google.com\/archive\/p\/bloom\/."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389137"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM58522.2023.00015"},{"key":"e_1_2_1_14_1","first-page":"743","volume-title":"Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Demaine Erik D.","year":"2000","unstructured":"Erik D. Demaine, Alejandro L\u00f3pez-Ortiz, and J. Ian Munro. 2000. Adaptive set intersections, unions, and differences. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 9-11, 2000, San Francisco, CA, USA. ACM\/SIAM, 743-752. http:\/\/dl.acm.org\/citation.cfm?id=338219.338634"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213855"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452797"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517862"},{"key":"e_1_2_1_19_1","volume-title":"Community detection in graphs. CoRR abs\/0906.0612","author":"Fortunato Santo","year":"2009","unstructured":"Santo Fortunato. 2009. Community detection in graphs. CoRR abs\/0906.0612 (2009). arXiv:0906.0612 http:\/\/arxiv.org\/abs\/0906.0612"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"e_1_2_1_21_1","volume-title":"Johnson","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_1_22_1","first-page":"17","volume-title":"PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs. In 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012","author":"Gonzalez Joseph E.","year":"2012","unstructured":"Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs. In 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8-10, 2012. USENIX Association, 17-30. https:\/\/www.usenix.org\/conference\/osdi12\/technical-sessions\/presentation\/gonzalez"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196924"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/WIDM.1226"},{"key":"e_1_2_1_26_1","volume-title":"Computer architecture: a quantitative approach","author":"Hennessy John L","unstructured":"John L Hennessy and David A Patterson. 2011. Computer architecture: a quantitative approach. Elsevier."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452815"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2691190.2691193"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316801"},{"key":"e_1_2_1_31_1","first-page":"31","volume-title":"10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012","author":"Kyrola Aapo","year":"2012","unstructured":"Aapo Kyrola, Guy E. Blelloch, and Carlos Guestrin. 2012. GraphChi: Large-Scale Graph Computation on Just a PC. In 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8-10, 2012. USENIX Association, 31-46. https:\/\/www.usenix.org\/conference\/osdi12\/technical-sessions\/presentation\/kyrola"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00032"},{"key":"e_1_2_1_33_1","volume-title":"Graph Summarization Methods and Applications: A Survey. ACM Comput. Surv. 51, 3","author":"Liu Yike","year":"2018","unstructured":"Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Koutra. 2018. Graph Summarization Methods and Applications: A Survey. ACM Comput. Surv. 51, 3 (2018), 62:1-62:34."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457253"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Deepankar Medhi and Karthikeyan Ramasamy. 2007. Network routing - algorithms protocols and architectures. Morgan Kaufmann.","DOI":"10.1016\/B978-012088588-6\/50006-1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376661"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1093\/ACPROF:OSO\/9780199206650.001.0001"},{"key":"e_1_2_1_39_1","first-page":"823","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005","author":"Pagh Anna","year":"2005","unstructured":"Anna Pagh, Rasmus Pagh, and S. Srinivasa Rao. 2005. An optimal Bloom filter replacement. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005. SIAM, 823-829. http:\/\/dl.acm.org\/citation.cfm?id=1070432.1070548"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2004.44"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00162"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113280"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2018.00052"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390334.1390423"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380581"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589326"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311907"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206038"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2011.031611.00024"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376675"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732992"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915220"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00051"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00193"},{"key":"e_1_2_1_56_1","first-page":"301","volume-title":"Gemini: A Computation-Centric Distributed Graph Processing System. In 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016","author":"Zhu Xiaowei","year":"2016","unstructured":"Xiaowei Zhu, Wenguang Chen, Weimin Zheng, and Xiaosong Ma. 2016. Gemini: A Computation-Centric Distributed Graph Processing System. In 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2-4, 2016. USENIX Association, 301-316."},{"key":"e_1_2_1_57_1","first-page":"375","volume-title":"Proceedings of the 2015 USENIX Annual Technical Conference, USENIX ATC 2015, July 8-10","author":"Zhu Xiaowei","year":"2015","unstructured":"Xiaowei Zhu, Wentao Han, and Wenguang Chen. 2015. GridGraph: Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning. In Proceedings of the 2015 USENIX Annual Technical Conference, USENIX ATC 2015, July 8-10, Santa Clara, CA, USA. USENIX Association, 375-386."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769798","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:47:17Z","timestamp":1781326037000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769798"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":57,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769798"],"URL":"https:\/\/doi.org\/10.1145\/3769798","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}