计算机科学 ›› 2014, Vol. 41 ›› Issue (12): 70-77.doi: 10.11896/j.issn.1002-137X.2014.12.016
毛莺池,王康,任道宁,王久龙
MAO Ying-chi,WANG Kang,REN Dao-ning and WANG Jiu-long
摘要: 在无线传感器网络现实应用中,感知数据普遍存在不确定性。由于不确定数据引入了概率维度,使得不确定数据查询种类更加丰富,同时也给查询处理带来困难。不确定数据Top-k查询是一个典型的不确定数据查询任务。考虑到无线传感器网络查询处理技术对查询响应时间和网络通信消耗的高要求,研究了面向层次聚簇结构的无线传感器网络不确定数据Top-k查询处理技术。通过分析不确定数据特点,基于x-tuple规则元组模型,采用簇内与簇间的两阶段数据查询处理机制,提出了基于Poisson分布的分布式不确定数据PT-Top k查询处理近似算法TPQP。通过实验,从总体通信消耗、与概率阈值p相关分析、与排序数k相关分析以及数据敏感度分析等方面,说明了TPQP算法在通信消耗、查询响应时间上的优越性。
[1] Hu C A,Fan L W,Mao Y M.HPDBSCAN:Efficient clustering algorithm for processing uncertain data[J].Computer Engine-ering and Design,2013,34(3):1044-1049 [2] Liu X,Yang D N,Ye M,et al.U-skyline:A new skyline query for uncertain databases [J].IEEE Transactions on nowledge and Data Engineering, 2013,25(4):945-960 [3] Ye M,Lee W C,Lee D L,et al.Distributed processing of probabilistic top-k queries in wireless sensor networks[J].IEEE Transactions onKnowledge and Data Engineering,2013,25(1):76-91 [4] Wang Y,Yu J.A Top-k Query Algorithm on Uncertain Strea-ming Data [J].Journal of Computational Information Systems,2013,9(13):5273-5279 [5] Soliman M A,Ilyas I F,Chang K C C.Top-k query processing in uncertain databases[C]∥Proceedings of the 23nd International Conference on Data Engineering,Istanbul,Turkey.IEEE,New York,2007 [6] Nasridinov A,Park Y H.Optimal Aggregator Node Selection in Wireless Sensor Networks [J].ICCA 2013,ASTL,2013,24:37-39 [7] Sharaf A,Beaver J,Labrinidis A,et al.Balancing energy efficiency and quality of aggregate data in sensor networks[J].VLDB Journal,2004,13(4):384-403 [8] Silberstein A S,Braynard R,Ellis C,et al.A sampling-based approach to optimizing top-k queries in sensor networks[C]∥Proc.International Council for Open and Distance Education.2006:68 [9] Zeinalipour-Yazti D,Vagena Z,Gunopulos D,et al.The ThresholdJoin Algorithm for Top-k Queries in Distributed Sensor Networks[C]∥DMSN’05 Proceedings of the 2nd International Workshop on Data Management for Sensor Networks.2005:121-1 [10] Fagin R,Lotem A,Naor M.Optimal aggregation algorithms for middleware [C]∥Proceedings of Special Interest Group on Management of Data.2001:23-33 [11] Bast H,Majumdar D,Schenkel R,et al.Io-top-k:Index-aceessoptimized top-k query processing[C]∥Very Large Data Base.2006:475-486 [12] Das G,Gunopulos D,Koudas N,et al.Answering top-k queries using views[C]∥Very Large Data Base.2006:451-462 [13] Theobald M,Weikum G,Schenkel R.Top-k query evaluationwith probabilistic guarantees[C]∥Very Large Data Base.2004:648-659 [14] Han Q,Mehrotra S,Venkatasubramanian N.Energy efficientdata collection in distributed sensor environments[C]∥Proc.Institute of Electrical and Electronics Engineers.2004:590-597 [15] http://berkeley.intel-research.net/labdata [16] Ye M,Lee W,Lee D,et al.Distributed Processing of Probabilistic Top-k Queries in Wireless Sensor Networks[J].IEEE Transactons on Knowledge and Data Engineering,2013,25(1):76-91 [17] Li J,Saha B,Deshpande A.A unified approach to ranking inprobabilistic databases[J].Pro.Very Large Data Base, 2009,2(1):502-513 [18] Ye M,Liu X,Lee W C,et al.Probabilistic Top-k Query Processing in Distributed Sensor Networks[C]∥Proc.International Council for Open and Distance Education.2010 [19] Li J,Saha B,Deshpande A.A unified approach to ranking inprobabilistic databases[J].Pro.Very Large Data Base,2009,2(1): 502-513 [20] Sun Yong-jiao,Yuan Ye,Wang Guo-ren.Top-k query processing over uncertain data in distributed environments[C]∥Proc.Springer Science Business Media.2011 [21] Manjeshwar A,Agrawal D P.TEEN:A protocol for enhanced efficiency in wireless sensor network[C]∥The 15th Parallel and Distributed Procesing Symp.Sam Francisco:Institute of Electrical and Electronics Engineers Computer Society,USA,2001 [22] Hua M,Pei J,Zhang W,et al.Ranking queries on uncertain data:a probabilistic threshold approach[C]∥Proc.Special Interest Group on Management of Data.2008 |
No related articles found! |
|