论文标题
在不断发展的树上的最佳跟踪标签
Optimally Tracking Labels on an Evolving Tree
论文作者
论文摘要
由于在随着时间的流逝中正在发展的大量点维护数据结构的问题，我们考虑了将一组标签分配给树的顶点的标签的问题，这些标签的位置随时间而变化。我们研究了不断发展的数据框架中的问题，在该框架中，由于称为Evolver的代理商的作用，标签会随着时间而变化。该算法只能通过明确探测树的各个节点来跟踪这些更改。该框架捕捉了保持结构的最新视图的复杂性与可用视图计算的结果质量之间的权衡。我们的结果允许数据的随机和对抗性演变，但要允许算法和Evolver之间的不同加速因子。我们表明，在极限上，我们的算法将标签保持在其实际位置的$ O（1）$之内。我们还提出了几乎匹配的下限。
Motivated by the problem of maintaining data structures for a large sets of points that are evolving over the course of time, we consider the problem of maintaining a set of labels assigned to the vertices of a tree, where the locations of these labels change over time. We study the problem in the evolving data framework, where labels change over time due to the action of an agent called the evolver. The algorithm can only track these changes by explicitly probing individual nodes of the tree. This framework captures the tradeoff between the complexity of maintaining an up-to-date view of the structure and the quality of results computed with the available view. Our results allow for both randomized and adversarial evolution of the data, subject to allowing different speedup factors between the algorithm and the evolver. We show that in the limit, our algorithm maintains labels to within an average distance of $O(1)$ of their actual locations. We also present nearly matching lower bounds.
