Optimizing Skyline Queries in SPA Distributed Networks
HUANG Zhen-hua1,2, XIANG Yang1, SUN Sheng-li3, CHEN Qian1
1. Department of Computer and Technology, Tongji University, Shanghai 201804, China;
2. The Key Laboratory of Embedded System and Service Computing, Ministry of Education, Tongji University, Shanghai 201804, China;
3. School of Software and Microelectronics, Peking University, Beijing 102600, China
Abstract：Skyline query has recently received a lot of attention in information service community.The TPAOSS (Three-Phase Algorithm for Optimizing Skyline Scalar) algorithm has two performance drawbacks:(1) in the third phase of TPAOSS,as the number of objects on net nodes increases,the length of bloom filter will increases exponentially,which will seriously influence the efficiency of obtaining replicated values and the occupation size of memory;(2) the TPAOSS algorithm does not consider the computation efficiency of local or global subspace skyline queries in each net node.Motivated by these facts,we propose EPSSQDN (Efficient Processing of Subspace Skyline Queries in Distributed Networks),an algorithm for efficient processing of subspace skyline queries in SPA distributed networks.Moreover,in order to further reduce the computation cost of subspace skyline queries and decrease the volume of data transferred,we present an efficient optimized techniques.Furthermore,we present extensive experiments that demonstrate our method is more advantageous than the TPAOSS algorithm.
[1] S Borzsonyi,D Kossmann,K Stocker.The skyline operator[A].Proc IEEE ICDE '01[C].Heidelberg:IEEE Press,2001.421-430.[2] 黄震华,王智慧,郭建奎,汪卫,施伯乐.有效预处理P2P网络中的子空间skyline查询[J].软件学报,2009,20(7):1825-1838. Z Huang,Z Wang,J Guo,W Wang,B Shi.Efficient preprocessing of subspace skyline queries in P2P networks[J].Journal of Software,2009,20(7):1825-1838.(in Chinese)[3] P Wu,C Zhang,Y Feng,B Zhao,D Agrawal,A Abbadi.Parallelizing skyline queries for scalable distribution[A].Proc EDBT'06[C].Munich:Springer Verlag,2006.112-130.[4] H Li,Q Tan,W Lee.Efficient progressive processing of skyline queries in peer-to-peer systems[A].Proc INFOSCALE'06[C].Hong Kong:ACM Press,2006.84-93.[5] S Wang,B Ooi,A Tung,L Xu.Efficient skyline query processing on peer-to-peer networks[A].Proc ICDE'07[C].Istanbul:IEEE Press,2007.372-381.[6] K Banafaa,R Li.Efficient algorithms for constrained subspace skyline query in structured peer-to-peer systems[A].Proc WAIM '12[C].Harbin:Springer Verlag,2012.334-345.[7] 薛小平,张思东,张宏科,王小平,葛乐,尹琴.基于内容的发布订阅系统路由算法[J].电子学报,2008,36(5):953-961. X Xue,S Zhang,H Zhang,X Wang,L Ge,Q Yin.Content-based routing algorithms of the publish-subscribe systems[J].Acta Electronica Sinica,2008,36(5):953-961.(in Chinese)[8] J Parreira,S Michel,G Weikum.P2P Dating:Real life inspired semantic overlay networks for web search[J].Information Processing and Management:An International Journal,2007,43(3):643-664.[9] K Zhao,Y Tao,S Zhou.Efficient top-k processing in large-scaled distributed environments[J].Data & Knowledge Engineering,2007,63(2):315-335.[10] 吴万明,吴毅坚,赵文耘.基于Chord网的语义Web Service发现[J].电子学报,2007,35(z2):152-155. W Wu,Y Wu,W Zhao.Chord-based semantic web service discovery[J].Acta Electronica Sinica,2007,35(z2):152-155.(in Chinese)[11] X Liu,Y Yuan,W Wang,H Lu.Stabbing the sky:efficient skyline computation over sliding windows[A].Proc IEEE ICDE'05[C].Tokyo:IEEE Press,2005.502-513.[12] Q Li,L Lopez,B Moon.Skyline index for time series data[J].IEEE Transactions on Knowledge and Data Engineering,2004,16(6):669-684.
2013, Vol. 41 
