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)
Incoming Non-self Citations Over Time
Authors
- 1. Jia Li (Huawei)
- 2. Wenyue Zhao (University of Edinburgh)
- 3. Nikos Ntarmos (Huawei)
- 4. Yang Cao (University of Edinburgh)
- 5. Peter Buneman (University of Edinburgh)
BibTeX Citation
@article{li_vldb23,
title = {{MITra: A Framework for Multi-Instance Graph Traversal}},
author = {Li, Jia and Zhao, Wenyue and Ntarmos, Nikos and Cao, Yang and Buneman, Peter},
journal = {PVLDB},
series = {{VLDB} '23},
volume = {16},
number = {10},
pages = {2551--2564},
doi = {10.14778/3603581.3603594},
url = {https://doi.org/10.14778/3603581.3603594},
year = {2023}
}Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,504 | Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries | 2024 | VLDB | 5.4132367e-05 |
| 10,919 | X-Blossom: Massive Parallelization of Graph Maximum Matching | 2025 | VLDB | 5.093636e-05 |
| 11,208 | Automating Vectorized Distributed Graph Computation | 2024 | SIGMOD | 5.093636e-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.
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 1,432 | The More the Merrier: Efficient Multi-Source Graph Traversal | 2015 | VLDB |
| 2 | 11,745 | Parallel Traversal of Graphs Stored in RDBMSs | 2020 | CIDR |
| 3 | 3,503 | Accelerating Truss Decomposition on Heterogeneous Processors | 2020 | VLDB |
| 4 | 10,252 | GraphRTX: Lighting the Way to Scalable Graph Analytics | 2026 | SIGMOD |
| 5 | 1,966 | GraphMat: High performance graph analytics made productive | 2015 | VLDB |
| 6 | 9,218 | GraphTwist: Fast Iterative Graph Computation with Two-tier Optimizations | 2015 | VLDB |
| 7 | 1,911 | Fast Iterative Graph Computation with Block Updates | 2013 | VLDB |
| 8 | 4,157 | GPU-based Graph Traversal on Compressed Graphs | 2019 | SIGMOD |
| 9 | 7,380 | MiniGraph: Querying Big Graphs with a Single Machine | 2023 | VLDB |
| 10 | 11,208 | Automating Vectorized Distributed Graph Computation | 2024 | SIGMOD |