An efficient scheme for probabilistic skyline queries over distributed uncertain data
详细信息 查看全文
- 作者：Xiaoyong Li ; Yijie Wang ; Jie Yu
- 关键词：Uncertain data ; Probabilistic skyline ; Distributed skyline ; Grid filtration
- 刊名：Telecommunication Systems
- 出版年：2015
- 出版时间：October 2015
- 年：2015
- 卷：60
- 期：2
- 页码：225-237
- 全文大小：1,171 KB
- 参考文献：1.Andritsos, P., Fuxman, A., Miller, R. (2006). Clean answers over dirty databases: A probabilistic approach. In Proceedings of the 22 nd international conference on data engineering (ICDE), p. 30.
2.Atallah, M., Qi, Y. (2009). Computing all skyline probabilities for uncertain data. In Proceedings of the twenty-eighth ACM SIGMODSIGACT-SIGART symposium on principles of database systems (PODS), pp. 279鈥?87.
3.Balke, W., G眉ntzer, U., Zheng, J. (2004). Efficient distributed skylining for web information systems. In Proceedings of the international conference on extending database technology: Advances in database technology (EDBT), pp. 573鈥?74.
4.Benjelloun, O., Sarma, A., Halevy, A., Widom, J. (2006). Uldbs: Databases with uncertainty and lineage. In Proceedings of the 32nd international conference on very large data bases (VLDB), pp. 953鈥?64.
5.B枚hm, C., Fiedler, F., Oswald, A., Plant, C., Wackersreuther, B. (2009). Probabilistic skyline queries. In Proceeding of the 18th ACM conference on information and knowledge management (CIKM), pp. 651鈥?60.
6.B枚hm, C., Pryakhin, A., Schubert, M. (2006). The gauss-tree: Efficient object identification in databases of probabilistic feature vectors. In Proceedings of the 22nd international conference on data engineering (ICDE).
7.B枚rzsonyi, S., Kossmann, D., Stocker, K. (2001). The skyline operator. In Proceedings of the 17th international conference on data engineering (ICDE), pp. 421鈥?30.
8.Carli, M., Campisi, P., & Neri, A. (2006). Perceptual aspects in data hiding. Telecommunication Systems, 33(1), 117鈥?29.CrossRef
9.Chen, L., Cui, B., Lu, H., Xu, L., Xu, Q. (2008). isky: Efficient and progressive skyline computing in a structured p2p network. In Proceedings of the 28th international conference on distributed computing systems (ICDCS), pp. 160鈥?67.
10.Chen, L., 脰zsu, M., Oria, V. (2005). Robust and fast similarity search for moving object trajectories. In Proceedings of the international conference on management of data (SIGMOD), pp. 491鈥?02.
11.Cheng, R., Kalashnikov, D., & Prabhakar, S. (2007). Evaluation of probabilistic queries over imprecise data in constantly-evolving environments. Information Systems, 32(1), 104鈥?30.CrossRef
12.Christian, B., Frank, F., Annahita, O. (2009). Computing all skyline probabilities for uncertain data. In Proceedings of the IEEE international conference on data mining (CIKM).
13.Cui, B., Lu, H., Xu, Q., Chen, L., Dai, Y., Zhou, Y. (2008). Parallel distributed processing of constrained skyline queries by filtering. In Proceedings of the 24th international conference on data engineering (ICDE).
14.Deb, B., Bhatnagar, S., & Nath, B. (2004). Stream: Sensor topology retrieval at multiple resolutions. Telecommunication Systems, 26(2), 285鈥?20.CrossRef
15.Deng, K., Zhou, X., Shen, H. (2007). Multi-source skyline query processing in road networks. In Proceedings of international conference on data engineering (ICDE), pp. 796鈥?05.
16.Ding, X., Jin, H. (2010). Efficient and progressive algorithms for distributed skyline queries over uncertain data. In Proceedings of the international conference on distributed computing systems (ICDCS), pp. 149鈥?58.
17.Fagin, R., Lotem, A., Naor, M. (2001). Optimal aggregation algorithms for middleware. In Proceedings of the twentieth ACM SIGMODSIGACT-SIGART symposium on principles of database systems (PODS), pp. 102鈥?13.
18.Fotiadou, K., Pitoura, E.: Bitpeer (2008). Continuous subspace skyline computation with distributed bitmap indexes. In Proceedings of the 2008 international workshop on data management in peer-to peer systems, pp. 35鈥?2.
19.Fuxman, A., Fazli, E., Miller, R. (2005). Conquer: Efficient management of inconsistent databases. In Proceedings of the ACM international conference on management of data (SIGMOD), pp. 155鈥?66.
20.Gunnar, A., & Johansson, M. (2011). Robust load balancing under traffic uncertainty tractable models and efficient algorithms. Telecommunication Systems, 48, 93鈥?07.CrossRef
21.Hose, K., Lemke, C., Sattler, K. (2006). Processing relaxed skylines in pdms using distributed data summaries. In Proceedings of the 15th ACM international conference on information and knowledge management (CIKM), pp. 425鈥?34.
22.Huang, Z., Jensen, C., Lu, H., Ooi, B. (2006). Skyline queries against mobile lightweight devices in Manets. In Proceedings of the 22nd international conference on data engineering (ICDE), pp. 66鈥?6.
23.Jagadish, H., Ooi, B., Vu, Q. (2005). Baton: A balanced tree structure for peer-to-peer networks. In Proceedings of the 31st international conference on very large data bases (VLDB), pp. 661鈥?72.
24.Khalefa, M., Mokbel, M., Levandoski, J. (2008). Skyline query processing for incomplete data. In Proceedings of the IEEE 24th international conference on data engineering (ICDE).
25.Li, X. Y., Wang, Y. J., Li, X. L., & Wang, Y. (2014). Parallelizing skyline queries over uncertain data streams with sliding window partitioning and grid index. Knowledge and Information Systems, 41(2), 277鈥?09.
26.Lian, X., Chen, L. (2008). Monochromatic and bichromatic reverse skyline search over uncertain data. In Proceedings of the international conference on management of data (SIGMOD), pp. 213鈥?26.
27.Nilesh, D., Dalvi, N. (2004). Efficient query evaluation on probabilistic databases. In Proceedings of the international conference on very large data bases (VLDB).
28.Pei, J., Jiang, B., Lin, X., Yuan, Y. (2007). Probabilistic skylines on uncertain data. In Proceedings of international conference on very large data bases (VLDB), pp. 15鈥?6.
29.Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S. (2001). A scalable content-addressable network. In Proceedings of the conference on applications, technologies, architectures, and protocols for computer communications, pp. 161鈥?72.
30.Re, C., Dalvi, N., Suciu, D. (2007). Efficient top-k query evaluation on probabilistic data. In Proceedings of the 23rd international conference on data engineering (ICDE), pp. 886鈥?95.
31.Rocha-Junior, J., Vlachou, A., Doulkeridis, C., & N酶rvag, K. (2009). AGiDS: A grid-based strategy for distributed skyline query processing. In Proceedings of data management in grid and peer-to-peer systems (Globe), pp. 12鈥?3.
32.Vlachou, A., Doulkeridis, C., Kotidis, Y., Vazirgiannis, M. (2007). Skypeer: Efficient subspace skyline computation over distributed data. In Proceedings of the 23rd international conference on data engineering (ICDE), pp. 416鈥?25.
33.Wang, S., Ooi, B., Tung, A., Xu, L. (2007). Efficient skyline query processing on peer-to-peer networks. In Proceedings of the 23rd international conference on data engineering (ICDE), pp. 1126鈥?135.
34.Wang, S., Vu, Q., Ooi, B., Tung, A., & Xu, L. (2009). Skyframe: A framework for skyline query processing in peer-to-peer systems. The VLDB Journal: The International Journal on Very Large Data Bases (VLDBJ), 18(1), 345鈥?62.CrossRef
35.Widom, J. (2005). Trio: A system for integrated management of data, accuracy, and lineage. In Proceedings of the 2nd biennial CIDR conference, pp. 262鈥?76.
36.Wu, P., Zhang, C., Feng, Y., Zhao, B., Agrawal, D., El Abbadi, A. (2006). Parallelizing skyline queries for scalable distribution. In Proceedings of the international conference on extending database technology: Advances in database technology (EDBT), pp. 112鈥?30.
37.Yiu, M., Mamoulis, N., Dai, X., Tao, Y., Vaitis, M. (2009). Efficient evaluation of probabilistic advanced spatial queries on existentially uncertain data. IEEE transactions on knowledge and data engineering (TKDE), pp. 108鈥?22.
38.Zhang, W., Lin, X., Zhang, Y., Wang, W., Yu, J. (2009). Probabilistic skyline operator over sliding windows. In Proceedings of the 25th international conference on data engineering (ICDE), pp. 1060鈥?071.
39.Zhu, L., Tao, Y., Zhou, S. (2009). Distributed skyline retrieval with low bandwidth consumption. IEEE transactions on knowledge and data engineering (TKDE), pp. 384鈥?00. - 作者单位：Xiaoyong Li (1)
Yijie Wang (1)
Jie Yu (1)
1. National Key Laboratory for Parallel and Distributed Processing, College of Computer, Academy of Ocean Science and Engineering, National University of Defense Technology, Changsha, China - 刊物类别：Business and Economics
- 刊物主题：Economics
Business Information Systems
Computer Communication Networks
Artificial Intelligence and Robotics
Probability Theory and Stochastic Processes - 出版者：Springer Netherlands
- ISSN：1572-9451
文摘
Uncertain data has already widely existed in many practical applications, such as sensor networks, RFID networks, location-based services and mobile object management, etc. The skyline queries over uncertain data as an important aspect of uncertain data management, has received extensive attention from the database research community currently, due to its importance in many application including multi-criteria decision making, preference answering, market analysis, etc. However, in most uncertainty applications, the uncertain data are usually collected from vast number of independent data sources among geographically scattered sites, which makes the central assembly of data at one location for storage and query is infeasible and inefficient. Taking account of the network delay and limited bandwidth associated with sharing and communicating large amounts of distributed data over an internet, an important and challenging problem in the scenario is to retrieve all the global skyline tuples from all the distributed local sites with minimum communication cost. In this paper, we propose GFS, which is an efficient scheme for probabilistic skyline over distributed uncertain data. GFS firstly prunes the unqualified tuples with the global grid information and further iteratively prune the unqualified tuples with an improved feedback mechanism. Extensive experiments confirm that the effectiveness and the efficiency of the GFS scheme. Keywords Uncertain data Probabilistic skyline Distributed skyline Grid filtration