MITra: A Framework for Multi-Instance Graph Traversal

Summary: MITra is a framework and formal model for multi-instance graph traversal that composes traversals from multiple source vertices on a single thread, capturing and exploiting traversal-sharing across instances to enable SIMD-friendly execution. It provides a concise programming model (vertex ranks + edge functions) that synthesizes multi-instance algorithms provably outperforming prior frameworks, delivering ~10× speedups over existing frameworks while matching hand-tuned state-of-the-art implementations. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13102
Venue: VLDB
Year: 2023
Pagerank: 4.3466395e-05
Overall Rank: 9,367 | 34.90%
DOI: 10.14778/3603581.3603594

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,486	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	4.3300131e-05
10,678	X-Blossom: Massive Parallelization of Graph Maximum Matching	2025	VLDB	4.1905499e-05
11,000	Automating Vectorized Distributed Graph Computation	2024	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
4	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0019040811
39	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00075263552
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030020929
570	From "Think Like a Vertex" to "Think Like a Graph"	2014	VLDB	0.00019895021
1,170	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00013526297
1,665	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB	0.00010958779
4,486	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1413967e-05
4,688	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	5.9900111e-05
5,966	Cache-Efficient Fork-Processing Patterns on Large Graphs	2021	SIGMOD	5.2471834e-05
7,402	A General-Purpose Query-Centric Framework for Querying Big Graphs	2016	VLDB	4.7346959e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,805	Automating Incremental Graph Processing with Flexible Memoization	2021	VLDB	4.2766788e-05
1,665	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB	0.00010958779
11,552	Parallel Traversal of Graphs Stored in RDBMSs	2020	CIDR	4.1905499e-05
3,976	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	6.5694893e-05
2,452	GraphMat: High performance graph analytics made productive	2015	VLDB	8.782919e-05
9,070	GraphTwist: Fast Iterative Graph Computation with Two-tier Optimizations	2015	VLDB	4.3982218e-05
1,684	Fast Iterative Graph Computation with Block Updates	2013	VLDB	0.00010912102
4,525	GPU-based Graph Traversal on Compressed Graphs	2019	SIGMOD	6.1087614e-05
8,152	MiniGraph: Querying Big Graphs with a Single Machine	2023	VLDB	4.5711161e-05
11,000	Automating Vectorized Distributed Graph Computation	2024	SIGMOD	4.1905499e-05