Efficient Skyline Query Processing on Peer-to-Peer Networks
Efficient Skyline Query Processing on Peer-to-Peer Networks
复制标题
DOI：
10.1109/icde.2007.368971
复制
发表时间：
2007-04
期刊：
影响因子：
--
通讯作者：
Shiyuan Wang;B. Ooi;A. Tung;Lizhen Xu
中科院分区：
文献类型：
--
作者：
Shiyuan Wang;B. Ooi;A. Tung;Lizhen Xu
近年来，Skyline查询在数据库研究社区中引起了很大的兴趣。现有的研究大多集中在集中式系统上，解决分布式环境（如P2P网络）中的问题仍然是一个新兴的课题。P2P环境下高效的天际线查询要求：1)逐级返回答案；2)从访问的对等节点数量和搜索消息数量来看，处理成本较低；3)对等节点之间的查询负载均衡。在本文中，我们提出了一种满足这三个需求的解决方案。我们的解决方案是基于一个平衡的树结构的P2P网络。通过基于查询访问模式自适应划分skyline搜索空间，可以缓解skyline查询处理中存在的“热点”问题。通过能够估计查询子空间中的对等节点，我们能够控制查询转发的数量，限制涉及的对等节点数量和网络中传输的消息数量。负载均衡是在节点加入/离开期间通过查询负载敏感的数据空间分割/合并以及动态负载迁移实现的。在真实和合成数据集上的实验验证了该算法在P2P网络上的有效性和可扩展性。
Skyline query has been gaining much interest in database research communities in recent years. Most existing studies focus mainly on centralized systems, and resolving the problem in a distributed environment such as a peer-to-peer (P2P) network is still an emerging topic. The desiderata of efficient skyline querying in P2P environment include: 1) progressive returning of answers, 2) low processing cost in terms of number of peers accessed and search messages, 3) balanced query loads among the peers. In this paper, we propose a solution that satisfies the three desiderata. Our solution is based on a balanced tree structured P2P network. By partitioning the skyline search space adaptively based on query accessing patterns, we are able to alleviate the problem of "hot" spots present in the skyline query processing. By being able to estimate the peer nodes within the query subspaces, we are able to control the amount of query forwarding, limiting the number of peers involved and the amount of messages transmitted in the network. Load balancing is achieved in query load conscious data space splitting/merging during the joining/departure of nodes and through dynamic load migration. Experiments on real and synthetic datasets confirm the effectiveness and scalability of our algorithm on P2P networks.