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.

has been cited by the following article:

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

  AUTHORS: Jianzhong Li, Shuguang Xiong

  KEYWORDS: Wireless Sensor Network, Query Processing, Uncertain Data, Probabilistic Data, Skyline Query

  JOURNAL NAME: Wireless Sensor Network, Vol.2 No.11, November 19, 2010

  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.