图很大、边很多的时候，想知道两个节点是否连通？传统方法空间随边数增长，新理论方法在稀疏图上反而浪费。HybridSCALE 说：把图拆开，稀疏部分无损存，稠密核心用 Sketch。
动态连通性维护是基础问题。过去几年的理论突破提出了"图 Sketch"，但实践中太臃肿。
HybridSCALE 的洞察：现实稀疏图的不均匀性——大多数边集中在少数顶点组成的稠密核心上。sketch 只编码核心，外围无损存储。BalloonSketch 进一步把 sketch 缩小 8 倍。
结果：稀疏图节省 15%，中等密度图节省 92%，稠密图节省 97%。
> 论文说 HybridSCALE 是"首个在真实图上节省空间的 Sketch 动态连通性算法"——这个"首个"很关键。
论文信息
- 标题：Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs
- 作者：Quinten De Man, Gilvir Gill, Michael A. Bender 等
- 预印本：arXiv:2605.15173 (cs.DS)
- 论文链接：https://arxiv.org/abs/2605.15173