Analysis of Stable Vertex Values: Fast Query Evaluation Over An Evolving Graph
Mahbod Afarin, Chao Gao, Xizhe Yin, Zhijia Zhao, Nael Abu-Ghazaleh, Rajiv Gupta · 2025
Read Analysis of Stable Vertex Values: Fast Query Evaluation Over An Evolving Graph by Mahbod Afarin, Chao Gao, Xizhe Yin, Zhijia Zhao, Nael Abu-Ghazaleh, Rajiv Gupta (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-10579.txt.
Description
Mahbod Afarin and co-authors speed in a 2025 study repeated queries over graphs that change a little at a time, by noticing how much does not change. Across twenty-five to one hundred snapshots of an evolving graph, most vertices keep the same answer, from about half to nearly all depending on the graph. Their method proves tight lower and upper bounds on each vertex's value.
Where the bounds meet, the answer is settled for every snapshot at once. The rest are computed together on a much smaller subgraph. Against a leading incremental system, speedups ran from twofold to over twelvefold.
Catalog record
| CREATOR | Mahbod Afarin, Chao Gao, Xizhe Yin, Zhijia Zhao, Nael Abu-Ghazaleh, Rajiv Gupta |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-10579