SCARAB: Scaling Reachability Computation on Large Graphs

Summary: SCARAB: scalable reachability framework for graphs with tens of millions of vertices/edges. Unified approach to scale state-of-the-art indices and speed up online queries; demonstrates orders-of-magnitude improvement over GRAIL on large-scale graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4583
Venue: SIGMOD
Year: 2012
Pagerank: 7.8401031e-05
Overall Rank: 3,021 | 79.28%
DOI: 10.1145/2213836.2213856

Incoming Non-self Citations Over Time

Authors

1. Ruoming Jin (Kent State University)
2. Ning Ruan (Kent State University)
3. Saikat Dey (Kent State University)
4. Jeffrey Yu Xu (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{jin_sigmod12,
        title = {{SCARAB: Scaling Reachability Computation on Large Graphs}},
        author = {Jin, Ruoming and Ruan, Ning and Dey, Saikat and Xu, Jeffrey Yu},
        series = {{SIGMOD} '12},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2213836.2213856},
        url = {https://dl.acm.org/doi/10.1145/2213836.2213856},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,533	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010467148
1,796	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	9.7380494e-05
1,838	Efficient Ad-hoc Search for Personalized PageRank	2013	SIGMOD	9.6436348e-05
2,575	K-Reach: Who is in Your Small World	2012	VLDB	8.3982298e-05
2,700	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	8.2411888e-05
3,278	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	7.5712342e-05
3,979	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.9754185e-05
6,603	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	5.824568e-05
7,707	DAG Reduction: Fast Answering Reachability Queries	2017	SIGMOD	5.5636745e-05
7,963	Coarsening Massive Influence Networks for Scalable Diffusion Analysis	2017	SIGMOD	5.5177915e-05
9,625	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	5.2434488e-05
10,052	Top-k Relevant Semantic Place Retrieval on Spatial RDF Data	2016	SIGMOD	5.1685424e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
269	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022786599
282	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.0002242162
322	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00021275303
444	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00018350865
679	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00015055389
746	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00014402233
1,301	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD	0.00011255351

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,278	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB
2	2,490	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD
3	8,651	Distributed Set Reachability	2016	SIGMOD
4	322	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD
5	6,603	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB
6	9,625	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB
7	1,796	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD
8	746	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD
9	5,968	SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization	2022	VLDB
10	679	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB