Efficient Pr-Skyline Query Processing and Optimization in Wireless Sensor Networks
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.
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.
KEYWORDS
Wireless Sensor Network, Query Processing, Uncertain Data, Probabilistic Data, Skyline Query
Wireless Sensor Network, Query Processing, Uncertain Data, Probabilistic Data, Skyline Query
Cite this paper
nullJ. Li and S. Xiong, "Efficient Pr-Skyline Query Processing and Optimization in Wireless Sensor Networks," Wireless Sensor Network, Vol. 2 No. 11, 2010, pp. 838-849. doi: 10.4236/wsn.2010.211101.
nullJ. Li and S. Xiong, "Efficient Pr-Skyline Query Processing and Optimization in Wireless Sensor Networks," Wireless Sensor Network, Vol. 2 No. 11, 2010, pp. 838-849. doi: 10.4236/wsn.2010.211101.
References
[1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, et al., “Wireless Sensor Networks: A Survey,” Computer Networks, Vol. 38, No. 4, 2002, pp. 393-422. [2] 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. [3] 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. [4] 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. [5] 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. [6] 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. [7] 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. [8] 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. [9] 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. [10] 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. [11] 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. [12] 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. [13] C. Koch and D. Olteanu, “Conditioning Probabilistic Databases,” in Proceedings of VLDB, ACM, New York, 2008, pp. 313-325. [14] R. Cheng, J. Chen and X. Xie, “Cleaning Uncertain Data with Quality Guarantees,” in Proceedings of VLDB, ACM, New York, 2008, pp. 722-735. [15] R. Sarkar, X. Zhu and J. Gao, “Double Rulings for Information Brokerage in Sensor Networks,” in Proceedings of ACM MOBICOM, ACM, New York, 2006, pp. 286- 297. [16] J. Pei, B. Jiang, X. Lin, et al., “Probabilistic Skylines on Uncertain Data,” in Proceedings of VLDB, ACM, New York, 2007, pp. 15-26. [17] S. Borzsonyi, D. Kossmann and K. Stocker, “The Skyline Operator,” in Proceedings of IEEE ICDE, Washington D.C., 2001, pp. 421-430. [18] E. Dellis and B. Seeger, “Efficient Computation of Reverse Skyline Queries,” in Proceedings of VLDB, ACM, New York, 2007, pp. 291-302. [19] K. Deng, X. Zhou and H. Shen, “Multi-Source Skyline Query Processing in Road Networks,” in Proceedings of IEEE ICDE, Washington D.C., 2007, pp. 796-805. [20] M. Hua, J. Pei, W. Zhang, et al., “Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach,” in Proceedings of ACM SIGMOD, ACM, New York, 2008, pp. 673-686. [21] R. Cheng, J. Chen and M. Mokbel, “Probabilistic Verifiers: Evaluating Constrained Nearest-Neighbor Queries over Uncertain Data,” in Proceedings of IEEE ICDE, Washing- ton D.C., 2008, pp. 973-982. [22] G. Beskales, M. Soliman, I. Ilyas, “Efficient Search for the Topk Probable Nearest Neighbors in Uncertain Databases,” in Proceedings of VLDB, ACM, New York, 2008, pp. 326-339. [23] R. Cheng, S. Singh, P. Prabhakar, et al., “Efficient Join Processing over Uncertain Data,” in Proceedings of ACM CIKM, ACM, New York, 2008, pp. 738-747. [24] C. Jin, K. Yi, L. Chen, et al., “Sliding-Window Top-k Queries on Uncertain Streams,” in Proceedings of VLDB, ACM, New York, 2008, pp. 301-312. [25] A. Silberstein, R. Braynard, C. Ellis, K. Munagala and J. Yang, “A Sampling-Based Approach to Optimizing Top- k Queries in Sensor Networks,” in Proceedings of IEEE ICDE, Washington D.C., 2006, pp. 68-77. [26] M. Garey and D. Johnson, “Computers and Intractibility: A Guide to the Theory of NP-Completeness,” Bell Telephone Laboratories, Inc, 1979. [27] R. Raz and S. Safra, “A Sub-Constant Error-Probability Low-Degree Test, and Sub-Constant Error-Probability PCP Characterization of NP,” in Proceedings of ACM STOC, ACM, New York, 1997, pp. 475-484. [28] TOSSIM: A Simulator for TinyOS Networks, [EB/OL] http://www.cs.berkeley.edu/pal/pubs/nido.pdf
[1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, et al., “Wireless Sensor Networks: A Survey,” Computer Networks, Vol. 38, No. 4, 2002, pp. 393-422. [2] 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. [3] 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. [4] 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. [5] 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. [6] 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. [7] 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. [8] 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. [9] 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. [10] 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. [11] 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. [12] 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. [13] C. Koch and D. Olteanu, “Conditioning Probabilistic Databases,” in Proceedings of VLDB, ACM, New York, 2008, pp. 313-325. [14] R. Cheng, J. Chen and X. Xie, “Cleaning Uncertain Data with Quality Guarantees,” in Proceedings of VLDB, ACM, New York, 2008, pp. 722-735. [15] R. Sarkar, X. Zhu and J. Gao, “Double Rulings for Information Brokerage in Sensor Networks,” in Proceedings of ACM MOBICOM, ACM, New York, 2006, pp. 286- 297. [16] J. Pei, B. Jiang, X. Lin, et al., “Probabilistic Skylines on Uncertain Data,” in Proceedings of VLDB, ACM, New York, 2007, pp. 15-26. [17] S. Borzsonyi, D. Kossmann and K. Stocker, “The Skyline Operator,” in Proceedings of IEEE ICDE, Washington D.C., 2001, pp. 421-430. [18] E. Dellis and B. Seeger, “Efficient Computation of Reverse Skyline Queries,” in Proceedings of VLDB, ACM, New York, 2007, pp. 291-302. [19] K. Deng, X. Zhou and H. Shen, “Multi-Source Skyline Query Processing in Road Networks,” in Proceedings of IEEE ICDE, Washington D.C., 2007, pp. 796-805. [20] M. Hua, J. Pei, W. Zhang, et al., “Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach,” in Proceedings of ACM SIGMOD, ACM, New York, 2008, pp. 673-686. [21] R. Cheng, J. Chen and M. Mokbel, “Probabilistic Verifiers: Evaluating Constrained Nearest-Neighbor Queries over Uncertain Data,” in Proceedings of IEEE ICDE, Washing- ton D.C., 2008, pp. 973-982. [22] G. Beskales, M. Soliman, I. Ilyas, “Efficient Search for the Topk Probable Nearest Neighbors in Uncertain Databases,” in Proceedings of VLDB, ACM, New York, 2008, pp. 326-339. [23] R. Cheng, S. Singh, P. Prabhakar, et al., “Efficient Join Processing over Uncertain Data,” in Proceedings of ACM CIKM, ACM, New York, 2008, pp. 738-747. [24] C. Jin, K. Yi, L. Chen, et al., “Sliding-Window Top-k Queries on Uncertain Streams,” in Proceedings of VLDB, ACM, New York, 2008, pp. 301-312. [25] A. Silberstein, R. Braynard, C. Ellis, K. Munagala and J. Yang, “A Sampling-Based Approach to Optimizing Top- k Queries in Sensor Networks,” in Proceedings of IEEE ICDE, Washington D.C., 2006, pp. 68-77. [26] M. Garey and D. Johnson, “Computers and Intractibility: A Guide to the Theory of NP-Completeness,” Bell Telephone Laboratories, Inc, 1979. [27] R. Raz and S. Safra, “A Sub-Constant Error-Probability Low-Degree Test, and Sub-Constant Error-Probability PCP Characterization of NP,” in Proceedings of ACM STOC, ACM, New York, 1997, pp. 475-484. [28] TOSSIM: A Simulator for TinyOS Networks, [EB/OL] http://www.cs.berkeley.edu/pal/pubs/nido.pdf