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

Summary: GraphTwin stores per-vertex k-bit GT-vectors (independent-set membership) so most non-edges are resolved by in-cache bitwise ANDs (95% in 1 cycle), drastically reducing L3 misses and query latency. Unresolved cases fall back to adjacency lists for exactness; GTWICE is a linear-time heuristic for the NP-hard submodular GT-vector construction. (summarized by gpt-5-mini on Feb 11 2026)

Paper ID: h88b1cba2027ab84d
Venue: SIGMOD
Year: 2026
Pagerank: 4.9793485e-05
Overall Rank: 10,573 | 28.92%
DOI: 10.1145/3769798

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Can Lu (Guangdong University of Technology)
2. Sijin Wang (Guangdong University of Technology)
3. Wenxuan Deng (Guangdong University of Technology)
4. Xinyu Li (Guangdong University of Technology)
5. Yikai Zhang (Guangdong University of Technology)
6. Jeffrey Xu Yu (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{lu_sigmod26,
        title = {{GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries}},
        author = {Lu, Can and Wang, Sijin and Deng, Wenxuan and Li, Xinyu and Zhang, Yikai and Yu, Jeffrey Xu},
        series = {{SIGMOD} '26},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3769798},
        url = {https://dl.acm.org/doi/10.1145/3769798},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
197	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025584127
443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018197688
490	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017438618
497	Efficient Aggregation for Graph Summarization	2008	SIGMOD	0.00017318153
563	Graph Summarization with Bounded Error	2008	SIGMOD	0.00016327158
657	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.0001505607
1,100	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00012013426
1,180	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00011627669
1,375	Query Preserving Graph Compression	2012	SIGMOD	0.00010877488
1,440	Speedup Graph Processing by Graph Ordering	2016	SIGMOD	0.00010641888
2,019	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.1750421e-05
2,469	Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU	2020	VLDB	8.4165523e-05
3,011	Efficient GPU-Accelerated Subgraph Matching	2023	SIGMOD	7.7549462e-05
3,314	Accelerating Triangle Counting on GPU	2021	SIGMOD	7.4380767e-05
4,049	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.8302372e-05
5,554	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	6.0858703e-05
5,734	Cache-Efficient Fork-Processing Patterns on Large Graphs	2021	SIGMOD	6.0137932e-05
7,015	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD	5.6210836e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,329	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD
2	4,044	Efficient Bi-triangle Counting for Large Bipartite Networks	2021	VLDB
3	3,767	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB
4	10,882	Efficient GPU-Accelerated Local Subgraph Counting	2026	VLDB
5	2,101	DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine	2016	SIGMOD
6	11,338	Efficient Graph Data Access for Out-of-Memory GPU Streaming Graph Processing	2025	VLDB
7	4,285	TurboGraph++: A Scalable and Fast Graph Analytics System	2018	SIGMOD
8	8,554	GC: A Graph Caching System for Subgraph/Supergraph Queries	2018	VLDB
9	5,734	Cache-Efficient Fork-Processing Patterns on Large Graphs	2021	SIGMOD
10	9,394	GraphTwist: Fast Iterative Graph Computation with Two-tier Optimizations	2015	VLDB