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: 7584
Venue: SIGMOD
Year: 2026
Pagerank: 5.093636e-05
Overall Rank: 10,376 | 28.82%
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
195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025813775
442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018398144
485	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017717377
486	Efficient Aggregation for Graph Summarization	2008	SIGMOD	0.00017692185
548	Graph Summarization with Bounded Error	2008	SIGMOD	0.00016694936
659	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00015214062
1,102	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00012166591
1,237	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00011545768
1,336	Query Preserving Graph Compression	2012	SIGMOD	0.00011118804
1,511	Speedup Graph Processing by Graph Ordering	2016	SIGMOD	0.00010538011
2,112	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.1514258e-05
2,288	Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU	2020	VLDB	8.8025299e-05
3,102	Efficient GPU-Accelerated Subgraph Matching	2023	SIGMOD	7.7568687e-05
3,686	Accelerating Triangle Counting on GPU	2021	SIGMOD	7.2029305e-05
3,979	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.9754185e-05
5,415	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	6.2255551e-05
5,612	Cache-Efficient Fork-Processing Patterns on Large Graphs	2021	SIGMOD	6.1501992e-05
6,876	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD	5.7483615e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,075	CGgraph: An Ultra-fast Graph Processing System on Modern Commodity CPU-GPU Co-processor	2024	VLDB
2	1,301	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD
3	3,997	Efficient Bi-triangle Counting for Large Bipartite Networks	2021	VLDB
4	3,709	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB
5	2,119	DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine	2016	SIGMOD
6	10,950	Efficient Graph Data Access for Out-of-Memory GPU Streaming Graph Processing	2025	VLDB
7	4,323	TurboGraph++: A Scalable and Fast Graph Analytics System	2018	SIGMOD
8	8,382	GC: A Graph Caching System for Subgraph/Supergraph Queries	2018	VLDB
9	5,612	Cache-Efficient Fork-Processing Patterns on Large Graphs	2021	SIGMOD
10	9,218	GraphTwist: Fast Iterative Graph Computation with Two-tier Optimizations	2015	VLDB