Efficient Pr-Skyline Query Processing and Optimization in Wireless Sensor Networks
- 1
- 2
Abstract
As one of the commonly used queries in modern databases, skyline query has received extensive attention from database research community. The uncertainty of the data in wireless sensor networks makes the corresponding skyline uncertain and not unique. This paper investigates the Pr-Skyline problem, i.e., how to compute the skyline with the highest existence probability in a computational and energy-efficient way. We formulate the problem and prove that it is NP-Complete and cannot be approximated in a given expression. However, the proposed algorithm SKY-SEARCH with pruning techniques can guarantee the computational efficiency given relatively large input size, while the filter-based distributed optimization strategy significantly reduces the transmission cost and the required storage space of the sensor nodes. Extensive experiments verify the efficiency and scalability of SKY-SEARCH and the distributed optimizing strategy.
- I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, et al., “Wireless Sensor Networks: A Survey,” Computer Networks, Vol. 38, No. 4, 2002, pp. 393-422.
- W. Liang, B. Chen and J. Yu, “Energy-Efficient Skyline Query Processing and Maintenance in Sensor Networks,” in Proceedings of ACM CIKM, New York, 2008, pp. 1471-1472.
- A. Deshpande, C. Guestrin, S. Madden, et al., “Model- Driven Data Acquisition in Sensor Networks,” in Proceedings of VLDB, New York, 2004, pp. 588-599.
- N. Shrivastava, C. Buragohain, D. Agrawal, et al., “Medians and Beyond: New Aggregation Techniques for Sensor Networks,” in Proceedings of SenSys, ACM, New York, 2004, pp. 239-249.
- S. Madden, M. Franklin, J. Hellerstein, et al., “TAG: A Tiny Aggregation Service for Ad-Hoc Sensor Networks,” in Proceedings of OSDI, ACM, New York, 2002, pp. 131 -146.
- X. Yang, H. B. Lim, M. Ozsu, et al., “In-Network Execution of Monitoring Queries in Sensor Networks,” in Proceedings of ACM SIGMOD, ACM, New York, 2007, pp. 521-532.
- A. Vlachou, C. Doulkeridis and Y. Kotidis, “Angle -Based Space Partitioning for Efficient Parallel Skyline Computation,” in Proceedings of SIGMOD, ACM, New York, 2008, pp. 227-238.
- X. Lian and L. Chen, “Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases,” in Proceedings of ACM SIGMOD, ACM, New York, 2008, pp. 213-226.
- J. Li, S. Sun and Y. Zhu, “Efficient Maintaining of Skyline over Probabilistic Data Stream,” in Proceedings of IEEE ICNC, Washington D.C., 2008, pp. 378-382.
- W. Liang, B. Chen and J. Yu, “Energy-Efficent Skyline Query Processing and Maintenance in Sensor Networks,” in Proceedings of ACM CIKM, ACM, New York, 2008, pp. 1471-1472.
- R. Cheng, Y. Xia, S. Prabhakar, et al., “Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data,” in Proceedings of VLDB, ACM, New York, 2004, pp. 876-887.
- R. Cheng, D. Kalashnikov and S. Prabhakar, “Evaluating Probabilistic Queries over Imprecise Data,” in Proceedings of ACM SIGMOD, ACM, New York, 2003, pp. 551-562.
- C. Koch and D. Olteanu, “Conditioning Probabilistic Databases,” in Proceedings of VLDB, ACM, New York, 2008, pp. 313-325.
- R. Cheng, J. Chen and X. Xie, “Cleaning Uncertain Data with Quality Guarantees,” in Proceedings of VLDB, ACM, New York, 2008, pp. 722-735.