Continuous Probabilistic Reverse Skyline Monitoring over Uncertain Data Streams

Abstract:

Reverse skyline is useful for supporting many applications, such as marketing decision,environmental monitoring. Since the uncertainty of data is inherent in many scenarios, there is a needfor processing probabilistic reverse skyline queries. In this paper, we study the problem of efficientlyprocessing these queries on uncertain data streams. We first show the formal definitions of reverseskyline probability and probabilistic reverse skyline. Then we propose a new algorithm called CPRSto maintain the most recent N uncertain data elements and to process continuous queries on them.CPRS is based on R-tree, and efficient pruning techniques, one of which is based on a new structurenamed Characteristic Rectangle, are incorporated into it to handling the extra computing complexityarising from the uncertainty of data. Finally, extensive experiments demonstrate that our techniquesare very efficient in handling uncertain data streams.

• Periodical: Applied Mechanics and Materials (Volumes 380-384)
• Pages: 2681-2686
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.380-384.2681
• Online since: August 2013
• Authors: Yong Tao Yang, Yi Jie Wang, Min Guo, Xiao Yong Li
• Keywords: Data Stream, Probabilistic Reverse Skyline, Sliding Window, Uncertain Data

References

[1] E. Dellis and B. Seeger, Efficient computation of reverse skyline queries, in VLDB, 2007, pp.291-302.

[2] X. Lian and L. Chen, Monochromatic and bichromatic reverse skyline search over uncertain databases, in SIGMOD, 2008, pp.213-226.

DOI: 10.1145/1376616.1376641

[3] D. Papadias, Y. Tao, G. Fu, and B. Seeger, An optimal and progressive algorithm for skyline queries, in SIGMOD, 2003, pp.467-478.

DOI: 10.1145/872757.872814

[4] W. Zhang, X. Lin, Y. Zhang, W. Wang, and J. X. Yu, Probabilistic skyline operator over sliding windows, in ICDE, 2009, pp.1060-1071.

DOI: 10.1109/icde.2009.83

[5] Y. Yang and Y. Wang, Towards estimating expected sizes of probabilistic skylines, SCIENCE CHINA Information Sciences, vol. 54, no. 12, pp.2554-2564, (2011).

DOI: 10.1007/s11432-011-4387-4

[6] Y. Wang, X. Li, X. Li, and Y. Wang, A survey of queries over uncertain data, Knowledge and Information Systems, 2013, doi: 10. 1007/s10115-013-0638-6.

[7] B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom, Models and issues in data stream systems, in PODS, 2002, pp.1-16.

DOI: 10.1145/543613.543615

[8] M. Bai, J. Xin, and G. Wang, Probabilistic reverse skyline query processing over uncertain data stream, in DASFAA, 2012, pp.17-32.

DOI: 10.1007/978-3-642-29035-0_2

[9] L. Zhu, C. Li, and H. Chen, Efficient computation of reverse skyline on data stream, in CSO, 2009, pp.735-739.

[10] J. Lim, Y. Park, J. Lee, D. Seo, and J. Yoo, An efficient method for processing reverse skyline queries, in Global Mobile Congress, 2010, pp.1-5.

DOI: 10.1109/gmc.2010.5634617

[11] G. Wang, J. Xin, L. Chen, and Y. Liu, Energy-efficient reverse skyline query processing over wireless sensor network, TKDE, vol. 24, no. 7, pp.1259-1275, (2012).

DOI: 10.1109/tkde.2011.64

[12] P. M. Deshpande and D. P, Efficient reverse skyline retrieval with arbitrary non-metric similarity measures, in EDBT, 2011, pp.319-330.

DOI: 10.1145/1951365.1951404

[13] N. Beckmann, H. -P. Kriegel, R. Schneider, and B. Seeger, The r*-tree: An efficient and robust access method for points and rectangles, in SIGMOD, 1990, pp.322-311.

DOI: 10.1145/93605.98741

[14] S. Börzsönyi, D. Kossmann, and K. Stocker, The skyline operator, in ICDE, 2001, pp.421-430.