P2P环境中的skyline查询综述

摘要/Abstract

摘要： 随着数据规模的增长以及网络技术的发展,对等网络(P2P)作为一种分布式信息共享与搜索的平台引起了越来越广泛的关注。基于对等网络高度动态、高度分散、扩展性强等特点,P2P上的skyline计算方法不仅需要满足集中式skyline计算方法的各种要求,还需要考虑减小网络通讯量、减少平均节点访问数、保持负载平衡等。文中对这个发展领域的最新技术进行了研究,并且描述了分布式skyline方法的目的和主要原理,概括了适用于P2P环境中的现有方法,并进行了性能比较分析。最后,给出了P2P环境skyline计算的未来发展方向。

关键词: skyline变化, skyline处理, 对等网络, 非结构化P2P, 结构化P2P

Abstract: With the growth of data scale and the development of network technology,peer-to-peer (P2P) has attracted more and more attention as a platform for distributed information sharing and searching.Based on the highly dynamic,highly decentralized and extensible features of peer-to-peer networks,the skyline calculation method on P2P not only needs to meet the requirements of centralized skyline calculation method,but also needs to reduce the network traffic,reduce the average number of nodes,maintain load balancing and other important metrics.This paper examined this ongoing research area so that readers can easily understand the most advanced overview.This paper described the purpose and main principles of the distributed skyline method,and summarized the existing methods applicable to the P2P environment and provided performance comparison analysis.Finally,this paper gave the future development direction of skyline calculation in P2P environment.

Key words: P2P, Skyline processing, Skyline variants, Structured P2P, Unstructured P2P

中图分类号:

TP3-05

孙志, 孙雪姣. P2P环境中的skyline查询综述[J]. 计算机科学, 2018, 45(11A): 63-70. https://doi.org/

SUN Zhi, SUN Xue-jiao. Survey of Skyline Processing in P2P Environments[J]. Computer Science, 2018, 45(11A): 63-70. https://doi.org/

参考文献

[1]BÖRZSÖNYI S,KOSSMANN D,STOCKER K.The Skyline Operator[C]∥International Conference on Data Engineering,2001.IEEE,2002:421-430.
[2]CHOMICKI J,GODFREY P,GRYZ J,et al.Skyline with presorting[C]∥International Conference on Data Engineering.IEEE,2003:717-719.
[3]GODFREY P,SHIPLEY R,GRYZ J.Maximal vector computation in large data sets[C]∥International Conference on Very Large Data Bases.VLDB Endowment,2005:229-240.
[4]KOSSMANN D,RAMSAK F,ROST S.Shooting stars in the sky:an online algorithm for skyline queries[C]∥International Conference on Very Large Data Bases.VLDB Endowment,2002:275-286.
[5]PAPADIAS D,TAO Y,FU G,et al.An optimal and progressive algorithm for skyline queries[C]∥ACM SIGMOD International Conference on Management of Data.ACM,2003:467-478.
[6]CUI B,LU H,XU Q,et al.Parallel Distributed Processing of Constrained Skyline Queries by Filtering[C]∥International Conference on Data Engineering.IEEE,2008:546-555.
[7]WU P,ZHANG C,FENG Y,et al.Parallelizing Skyline Queries for Scalable Distribution[C]∥International Conference on Advances in Database Technology-EDBT.DBLP,2006:112-130.
[8]PEI J,JIN W,ESTER M,et al.Catching the best views of skyline:a semantic approach based on decisive subspaces[C]∥International Conference on Very Large Data Bases.2005:253-264.
[9]TAO Y,XIAO X,PEI J.SUBSKY:Efficient Computation of Skylines in Subspaces[C]∥International Conference on Data Engineering.IEEE,2006:65-65.
[10]CRESPO A,GARCIA-MOLINA H.Routing indices for peer-to-peer systems[C]∥International Conference on Distributed Computing Systems.IEEE,2002:23-32.
[11]HOSE K,LEMKE C,SATTLER K U.Processing relaxed skylines in PDMS using distributed data summaries[C]∥ACM International Conference on Information and Knowledge Management.DBLP,2006:425-434.
[12]RATNASAMY S,FRANCIS P,HANDLEY M,et al.A scalable content-addressable network[C]∥Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications.ACM,2001:161-172.
[13]WANG S,OOI B C,TUNG A K H,et al.Efficient Skyline Query Processing on Peer-to-Peer Networks[C]∥IEEE,International Conference on Data Engineering.IEEE,2007:1126-1135.
[14]JAGADISH H V,OOI B C,VU Q H.BATON:a balanced tree structure for peer-to-peer networks[C]∥International Con-ference on Very Large Data Bases.VLDB Endowment,2006:661-672.
[15]HUANG Z,JENSEN C S,LU H,et al.Skyline Queries Against Mobile Lightweight Devices in MANETs[C]∥International Conference on Data Engineering.IEEE,2006:66.
[16]WANG S,VU Q H,OOI B C,et al.Skyframe:a framework for skyline query processing in peer-to-peer systems[J].The International Journal on Very Large Data Bases,2009,18(1):345-362.
[17]CHEN L,CUI B,LU H,et al.iSky:Efficient and Progressive Skyline Computing in a Structured P2P Network[C]∥International Conference on Distributed Computing Systems.IEEE,2008:160-167.
[18]LI H J,TAN Q Z,LEE W-C,et al.Efficient progressive proces-sing of skyline queries in peer-to-peer systems[C]∥InternationalConference on Scalable Information Systems.DBLP,2006:26.
[19]CUI B,CHEN L,XU L,et al.Efficient Skyline Computation in Structured Peer-to-Peer Systems[J].IEEE Transactions on Knowledge & Data Engineering,2009,21(7):1059-1072.
[20]HOSE K,LEMKE C,SATTLER K U,et al.A Relaxed But Not Necessarily Constrained Way from the Top to the Sky[J].Lecture Notes in Computer Science,2007,4803:399-407.
[21]VLACHOU A,DOULKERIDIS C,KOTIDIS Y,et al.SKY-PEER:Efficient Subspace Skyline Computation over Distributed Data[C]∥International Conference on Data Engineering.IEEE,2007:416-425.
[22]VLACHOU A,DOULKERIDIS C,KOTIDIS Y,et al.Efficient Routing of Subspace Skyline Queries over Highly Distributed Data[J].IEEE Transactions on Knowledge & Data Enginee-ring,2010,22(12):1694-1708.
[23]FOTIADOU K,PITOURA E.BITPEER:continuous subspace skyline computation with distributed bitmap indexes[OL].http://zeus.cs.uoi.gr/~pitoura/distribution/damap08.pdf.
[24]TAN K L,ENG P K,OOI B C.Efficient Progressive Skyline Computation[C]∥International Conference on Very Large Data Bases.2001:301-310.
[25]PEI J,JIANG B,LIN X,et al.Probabilistic skylines on uncertain data[C]∥International Conference on Very Large Data Bases.VLDB Endowment,2007:15-26.
[26]ZHANG Z,YANG Y,CAI R,et al.Kernel-based skyline cardinality estimation[C]∥ACM Sigmod International Conference on Management of Data.DBLP,2009:509-522.

相关文章 15

[1]	李龙飞,张泾周,王鹏德,郭鹏军. 基于节点兴趣和Q-learning的P2P网络搜索机制 P2P Network Search Mechanism Based on Node Interest and Q-learning 计算机科学, 2020, 47(2): 221-226. https://doi.org/10.11896/jsjkx.190400002
[2]	周璇,宦国强,宋占杰. 基于P2P网络的机顶盒VoD系统条件接收机制 Conditional Access Mechanism of Video-on-demand System Based on Peer-to-Peer Network 计算机科学, 2015, 42(4): 72-75. https://doi.org/10.11896/j.issn.1002-137X.2015.04.013
[3]	张强,李建华,沈迪. 基于P2P网络的语义发布/订阅系统路由算法研究 Research on Routing Algorithm of Semantic-based Publish/Subscribe System over P2P Networks 计算机科学, 2014, 41(9): 137-140. https://doi.org/10.11896/j.issn.1002-137X.2014.09.026
[4]	廖新考,王力生. 基于社会规范准则和联合抵制的节点激励机制研究 Research on Incentive Mechanism Based on Social Norms and Boycott 计算机科学, 2014, 41(4): 28-30.
[5]	黄志敏,曾学文,陈君. 一种基于Kademlia的全分布式爬虫集群方法 Method for Fully Distributed Crawler Cluster Based on Kademlia 计算机科学, 2014, 41(3): 124-128.
[6]	严鹤,刘威,张戈,程文青. 基于活跃节点的KAD网络高效查询方法 Efficient Lookup Method Based on Highly Available Peers in KAD 计算机科学, 2014, 41(12): 57-59. https://doi.org/10.11896/j.issn.1002-137X.2014.12.013
[7]	张国印,李军,王向辉,徐国坤. 一种基于移动P2P改进的Gossip算法 Improved Gossip Algorithm Based on Mobile P2P Networks 计算机科学, 2013, 40(9): 103-105.
[8]	王峰,李亚,朱海,王迤然. 一种基于蚁群算法的Sybil攻击防御 Sybil Attack Defense Based on Ant Colony Algorithm 计算机科学, 2013, 40(6): 100-102.
[9]	唐浩坤,刘宴兵,黄俊,张衡. 基于形式化逻辑矩阵的结构化P2P蠕虫对抗模型 Structured P2P Worm-anti-worm Model Based on Formalized Logic Matrix 计算机科学, 2013, 40(5): 141-146.
[10]	黄海，庞涛，武娟. P2P网络技术研究现状与展望 Recent Advances and Trends of Peer-to-Peer Networking Research 计算机科学, 2012, 39(Z6): 178-183.
[11]	王蓉,陈爱网,杜炜. 改进型自组织网络路由模型研究 Study of Self-organizing Network Routing Model 计算机科学, 2012, 39(Z6): 132-135.
[12]	王海晟,王海晨,桂小林. 使用粗糙集与Bayes分类器的P2P网络安全管理机制 New P2P Network Security Mechanism Based on the Rough Set and the Bayes Classifier 计算机科学, 2012, 39(9): 28-32.
[13]	罗樵,陈靖,郭一辰,黄聪会. 大规模无线传感器网络中基于P2P的路由模型研究 Study of Large-scale WSN Routing Model Based on P2P 计算机科学, 2012, 39(2): 126-131.
[14]	徐强，孙乐昌,刘京菊,赵亭,蔡铭. DHT网络中的多维复杂查询处理方法研究 Multi-dimensional Complex Query Processing over DHT 计算机科学, 2011, 38(9): 82-86.
[15]	胡建理，周斌.周瑜.吴泉源. 一种激励相容的P2P信誉模型 Incentive Compatible Reputation Model for P2P Networks 计算机科学, 2011, 38(9): 59-63.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed