UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic Trees

doi:10.1145/3774934.3786431

2026-01-01

PRE

DOI：10.1145/3774934.3786431

原文链接

原文求助

摘要

En 中文

动态树问题是指在边更新的同时维护一棵树，并支持诸如连通性查询或路径查询等操作。尽管用于该基本问题的第一种数据结构——连接-切割树——早在40年前就已发明，但我们的实验表明，它们仍然是该问题的最快顺序数据结构。然而，连接-切割树无法支持并行批量动态更新，且对支持的查询类型有限制。在本文中，我们设计了一种新的并行批量动态树数据结构，称为UFO树，它同时支持广泛的查询功能，支持高效工作的并行批量动态更新，并且在顺序运行时与连接-切割树具有竞争力。我们证明了连接-切割树和UFO树表现出强大实际性能的一个关键原因是它们能够在低直径树上以次对数时间执行更新和查询。我们对UFO树的优化C++实现进行了实验研究，将其与另外十种动态树实现（其中几种是新的）在广泛基准测试中进行比较，测试对象包括合成树和真实世界树，这些树具有不同的直径和大小。我们的结果表明，在顺序和并行设置下，UFO树都是支持广泛查询的最快动态树数据结构。我们新的UFO树实现具有低空间占用，并且可以轻松扩展到十亿规模的输入，使其成为在实际中实现更复杂动态图算法的一个有前景的构建模块。

Keyword:

dynamic trees

batch-dynamic trees