Efficient Pr-Skyline Query Processing and Optimization in Wireless Sensor Networks

• 作者: Jianzhong Li Shuguang Xiong
• 来源期刊: 无线传感网络(英文)
• 学科: 工学
• 关键词: Wireless Sensor Network QUERY Processing UNCERTAIN DATA PROBABILISTIC DATA SKYLINE QUERY
• 年，卷（期）: 2010,（11）
• 页码范围: 838-849
• 页数: 12页
• 分类号: TP39

摘要

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.