Research On (ε, δ)-Approximate Query Processing Algorithms In Sensor Networks

With the development of microelectronics, computing and wireless communication technology, low-power and multi-function sensors gain rapid evolution and sensor networks are being applied widely in all kinds of applications. Wireless sensor networks are data centric, which provide data collection, processing and query services.In sensor networks, top-k queries have received considerable attention recently. Some related work brings up top-k query processing algorithm. However the existing approaches focus exclusively on providing the exact top-k result and cost much energy, which reduces the life of the sensor networks.Approximate can meet users'requirements. Some algorithms return the exact results or approximate results under some restriction. However, they can not satisfy arbitrary precision requirement given by users. In this paper we propose a sampling based approximate Top-k algorithm that is adaptive for any data distribution.ε≥0 and 0≤δ<1 are respectively relative error bound and failure probability bound. The theoretical analysis demonstrates that for anyε≥0 and 0≤δ<1 the probability that the relative error bound of the results returned by this algorithm is larger thanε/(1+ε) is less thanδ. So the proposed algorithm can reach arbitrary precision. Furthermore, we propose an optimal sampling algorithm that supports the approximate Top-k query, and we reduce the energy consumption of communication through the technique of data filtering. We present some theoretical analysis and simulation experiments for the optimal strategy. The theoretical analysis and experimental results show that the approximate algorithm proposed in this paper is efficient and consumes little energy.We also exploit the semantics of approximate Skyline query and Skyline query. We propose a sampling based approximate Skyline algorithm. The theoretical analysis demonstrates that for anyε≥0 and 0≤δ<1 the probability that the relative error bound of the results returned by this algorithm is larger thanε/(1+ε) is less thanδ. Simulations on synthetic data show that the algorithm is energy efficient...