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

CREATORMahbod Afarin, Chao Gao, Xizhe Yin, Zhijia Zhao, Nael Abu-Ghazaleh, Rajiv Gupta
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-10579

Browse the full library · About the Tower of Babel