Communication-Efficient Distributed Skyline Computation
Communication-Efficient Distributed Skyline Computation
复制标题
DOI：
10.1145/3132847.3132927
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
Haoyu Zhang;Qin Zhang
中科院分区：
文献类型：
--
作者：
Haoyu Zhang;Qin Zhang
在本文中，我们研究了分布式计算模型中的天际线查询，在该模型中，我们拥有远程站点和中央协调员。每个站点都有一个数据，并且协调员希望计算S数据集联合的天际线。该计算是在巡回演出方面，目的是最大程度地减少总通信成本和圆形成本。我们首先给出了算法，其沟通成本很小，但可能是巨大的回合成本；从理论上讲，我们向信息表明，即使我们允许无限数量的通信回合，交流成本也是最佳的。接下来，我们给出算法，并具有平稳的通信折衷方案。如果我们只能使用一轮沟通，我们还显示出强大的沟通成本下限。最后，我们通过在合成世界和现实世界数据集上进行了一系列实验，证明了算法比现有算法的优势。
In this paper we study skyline queries in the distributed computational model, where we have s remote sites and a central coordinator; each site holds a piece of data, and the coordinator wants to compute the skyline of the union of the s datasets. The computation is in terms of rounds, and the goal is to minimize both the total communication cost and the round cost. We first give an algorithm with a small communication cost but potentially a large round cost; we show information-theoretically that the communication cost is optimal even if we allow an infinite number of communication rounds. We next give algorithms with smooth communication-round tradeoffs. We also show a strong lower bound for the communication cost if we can only use one round of communication. Finally, we demonstrate the superiority of our algorithms over existing ones by an extensive set of experiments on both synthetic and real world datasets.