基于事件的位置不确定移动对象连续概率Skyline查询

付世昌; 董一鸿; 唐燕琳; 陈华辉; 钱江波

doi:10.3724/SP.J.1004.2011.00836

基于事件的位置不确定移动对象连续概率Skyline查询

doi: 10.3724/SP.J.1004.2011.00836

1.
宁波大学信息科学与工程学院宁波 315211;
2.
浙江大学计算机科学与技术学院杭州 310027

计量
- 文章访问数: 2276
- HTML全文浏览量: 68
- PDF下载量: 768
- 被引次数: 0
出版历程
- 收稿日期: 2010-04-09
- 修回日期: 2011-03-02
- 刊出日期: 2011-07-20

Continuous Probabilistic Skyline Queries for Moving Objects with Uncertainty Based on Event

1.
College of Information Science and Engineering, Ningbo University, Ningbo 315211;
2.
College of Computer Science and Technology, Zhejiang University, Hangzhou 310027

摘要

摘要: Skyline查询是基于位置服务(Location based service, LBS)的一项重要操作,其目的是发现数据集中不被其他点支配的点的集合.移动对象在运动过程中,其位置信息具有不确定性,导致各数据点间的支配关系不稳定,从而影响Skyline操作.本文针对以位置不确定移动对象为查询点的Skyline查询进行研究,首先,定义了查询点移动时各对象间支配概率,提出了支配概率和Skyline概率的微元计算方法.在此基础上,提出一种面向不确定移动对象进行连续概率Skyline查询的有效算法U_CPSC.该算法首先快速计算初始时刻的p-Skyline集合; 然后,定义了两类可能引起p-Skyline变动的事件,通过对这些事件的跟踪计算快速更新p-Skyline集合,无需在移动对象的每一运动时刻去遍历整个数据集,实现了对p-Skyline的连续更新操作,大大减少了算法的查找和计算开销,提高了运算效率;最后,提出一种静态算法U_SPSC,与U_CPSC进行了对比试验,实验结果证明了算法的有效性.
- 概率Skyline /
- 不确定数据 /
- 移动对象 /
- 支配概率
Abstract: Skyline queries are an important operator of location based service (LBS), which aim to find all data that are not dominated by any others. The uncertainty of moving objects makes the dominant relationship of data instable, which will affect skyline operator. In this paper, skyline inquires for moving objects with uncertainty are studied. Firstly, the dominant probability between two moving objects is defined. Then it is proposed how to compute the dominant probability and skyline probability by differential element method. A novel effective algorithm U_CPSC is presented to handle continuous probabilistic skyline queries for uncertain moving objects based on these definitions. The initial p-Skyline set is firstly searched by rapid computing. Secondly, two types of events affecting p-Skyline are defined to track and update p-Skyline set continuously instead of re-computing the whole dataset each time. A static algorithm U_SPSC is proposed to compare with U_CPSC. Experiments have positive results that show effectiveness of the proposed algorithm.
- Probabilistic skyline /
- uncertain data /
- moving objects /
- dominant probability

HTML全文

参考文献(1)

[1]

Borzsonyi S, Kossmann D, Stocker K. The skyline operator. In: Proceedings of the 17th International Conference on Data Engineering. Heidelberg, Germany: IEEE, 2001. 421-430[2] Pei J, Jiang B, Lin X, Yuan Y D. Probabilistic skylines on uncertain data. In: Proceedings of the 33rd International Conference on Very Large Data Bases. Vienna, Austria: VLDB Endowment, 2007. 15-26[3] Zhang W J, Lin X M, Zhang Y, Wang W, Yu J X. Probabilistic skyline operator over sliding windows. In: Proceedings of the 25th International Conference on Data Engineering. Shanghai, China: IEEE, 2009. 1060-1071[4] Atallah M J, Qi Y N. Computing all skyline probabilities for uncertain data. In: Proceedings of the 28th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. New York, USA: ACM, 2009. 279-287[5] Bohm C, Fiedler F, Oswald A, Plant C, Wackersreuther B. Probabilistic skyline queries. In: Proceedings of the 18th ACM Conference on Information and Knowledge Management. New York, USA: ACM, 2009. 651-660[6] Tan K L, Eng P K, Ooi B C. Efficient progressive skyline computation. In: Proceedings of the 27th International Conference on Very Large Data Bases. San Francisco, USA: Morgan Kaufmann Publishers, 2001. 301-310[7] Kossmann D, Ramsak F, Rost S. Shooting stars in the sky: an online algorithm for skyline queries. In: Proceedings of the 28th International Conference on Very Large Data Bases. Hong Kong, China: Morgan Kaufmann Publishers, 2002. 275-286[8] Papadias D, Tao Y, Fu G, Seeger B. Progressive skyline computation in database systems. ACM Transactions on Database Systems, 2005, 30(1): 41-82 [9] Zhou Hong-Fu, Gong Xue-Qing, Zheng Kai, Zhou Ao-Ying. CSky: an online efficient algorithm for subspace skyline computation in high dimensional space. Chinese Journal of Computers, 2007, 30(8): 1409-1417(周红福, 宫学庆, 郑凯, 周傲英. 基于高维空间的在线高效子空间Skyline 算法-CSky. 计算机学报, 2007, 30(8): 1409-1417)[10] Sun Sheng-Li, Huang Zhen-Hua, Li Jin-Jiu, Guo Jian-Kui, Zhu Yang-Yong. Efficient computation of subspace skyline over data streams. Chinese Journal of Computers, 2007, 30(8): 1418-1428(孙圣力, 黄震华, 李金玖, 郭建奎, 朱扬勇. 数据流上高效计算子空间Skyline的算法. 计算机学报, 2007, 30(8): 1418-1428)[11] Su Liang, Zou Peng, Jia Yan. Adaptive mining of sparse skyline over data stream. Acta Automatica Sinica, 2008, 34(3): 360-366(苏亮, 邹鹏, 贾焰. 数据流上自适应的稀疏Skyline挖掘. 自动化学报, 2008, 34(3): 360-366)[12] Sun Sheng-Li, Dai Dong-Bo, Huang Zhen-Hua, Zhang Qi-Xun, Zhou Li-Xin. Algorithm on computing skyline over probabilistic data stream. Acta Electronica Sinica, 2009, 37(2): 285-293(孙圣力, 戴东波, 黄震华, 张齐勋, 周立新. 概率数据流上Skyline查询处理算法. 电子学报, 2009, 37(2): 285-293)[13] Huang Zhen-Hua, Xiang Yang, Xue Yong-Sheng, Zhao Gang. An efficient method for parallel processing of skyline queries. Acta Automatica Sinica, 2010, 36(7): 968-975(黄震华, 向阳, 薛永生, 赵杠. 一种并行处理Skyline查询的有效方法. 自动化学报, 2010, 36(7): 968-975)[14] Huang Z, Lu H, Ooi B C, Tung A K H. Continuous skyline queries for moving objects. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(12): 1645-1658[15] Lee M W, Hwang S W. Continuous skylining on volatile moving data. In: Proceedings of the IEEE International Conference on Data Engineering . Washington D.C., USA: IEEE, 2009. 1568-1575[16] Cheng R, Kalashnikov D V, Prabhakar S. Querying imprecise data in moving object environments. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(9): 1112-1127[17] Ding Xiao-Feng, Lu Yan-Sheng, Pan Peng, Hong Liang, Wei Qiong. U-Tree based indexing method for uncertain moving objects. Journal of Software, 2008, 19(10): 2696-2705(丁晓锋, 卢炎生, 潘鹏, 洪亮, 魏琼. 基于U-tree的不确定移动对象索引策略. 软件学报, 2008, 19(10): 2696-2705)[18] Benetis R, Jensen C, Karciauskas G, Saltenis S. Nearest neighbor and reverse nearest neighbor queries for moving objects. In: Proceedings of the International Database Engineering and Applications Symposium. Edmonton, Canada: IEEE, 2002. 44-53

施引文献

资源附件(0)

访问统计