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: 13101
Venue: VLDB
Year: 2023
Pagerank: 4.350809e-05
Overall Rank: 9,360 | 34.89%
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,484	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	4.3341665e-05
10,670	X-Blossom: Massive Parallelization of Graph Maximum Matching	2025	VLDB	4.1945683e-05
10,997	Automating Vectorized Distributed Graph Computation	2024	SIGMOD	4.1945683e-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.0019005923
37	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.0007522744
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030040036
574	From "Think Like a Vertex" to "Think Like a Graph"	2014	VLDB	0.00019883211
1,171	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00013511313
1,665	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB	0.00010967716
4,494	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1414196e-05
4,733	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	5.9631943e-05
6,059	Cache-Efficient Fork-Processing Patterns on Large Graphs	2021	SIGMOD	5.2307519e-05
7,402	A General-Purpose Query-Centric Framework for Querying Big Graphs	2016	VLDB	4.7392415e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,802	Automating Incremental Graph Processing with Flexible Memoization	2021	VLDB	4.2807806e-05
1,665	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB	0.00010967716
11,548	Parallel Traversal of Graphs Stored in RDBMSs	2020	CIDR	4.1945683e-05
3,975	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	6.5736847e-05
2,449	GraphMat: High performance graph analytics made productive	2015	VLDB	8.7915899e-05
9,072	GraphTwist: Fast Iterative Graph Computation with Two-tier Optimizations	2015	VLDB	4.4024417e-05
1,685	Fast Iterative Graph Computation with Block Updates	2013	VLDB	0.0001091808
4,522	GPU-based Graph Traversal on Compressed Graphs	2019	SIGMOD	6.1146374e-05
8,146	MiniGraph: Querying Big Graphs with a Single Machine	2023	VLDB	4.5755031e-05
10,997	Automating Vectorized Distributed Graph Computation	2024	SIGMOD	4.1945683e-05