Time Lower Bounds for Distributed Distance Oracles
Time Lower Bounds for Distributed Distance Oracles
复制标题
分布式距离预言机的时间下限
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Roger Wattenhofer
中科院分区：
文献类型：
--
作者：
Taisuke Izumi;Roger Wattenhofer
分布式距离甲骨文由标记方案组成，该标记方案将标签分配给每个节点，以及部署到每个节点的本地数据结构。当节点V想知道与节点U的距离时，它会使用u的标签查询其本地数据结构。数据结构将估计的距离返回到U，该距离必须大于实际距离，但可以高估。距离甲骨文的准确性是通过拉伸测量的，这定义为所有对（u，v）的实际距离和估计距离之间的最大比率。
Distributed distance oracles consist of a labeling scheme which assigns a label to each node and a local data structure deployed to each node. When a node v wants to know the distance to a node u, it queries its local data structure with the label of u. The data structure returns an estimated distance to u, which must be larger than the actual distance but can be overestimated. The accuracy of the distance oracle is measured by stretch, which is defined as the maximum ratio between actual distances and estimated distances over all pairs (u, v).