# Approximate Sensory Data Collection: A Survey
## 4 Query-Driven Approximate Data Collection Algorithms
### Sampling-Based Algorithms  
In many WSN applications, the statistic queries, such as aggregation and top-\(k\) queries, are the most popular ones. To answer such queries, the sampling techniques are good choices for designing an approximate data collection algorithm since only a small subset of sensory data needs to be transmitted.  
The work in [40] proposed a sampling based approach to process top-\(k\) queries. The nodes with larger historical sensed values are selected to transmit data to the sink with a high probability. A group of linear programming functions are adopted to assign a sampling probability to each node. The algorithm is only applicable to top-\(k\) queries and is hard to be extended to other queries. Meanwhile, abnormal events are hard to be detected based on historical data.  
The works in [41] proposed a uniform sampling algorithm to collect sensory data in order to process aggregation queries in static WSNs. The works in [42; 43] introduced several Bernoulli sampling based algorithms to deal with aggregations in dynamic WSNs. The authors proved that the result accuracies can satisfy an arbitrary user-specified precision requirement, and the sampling ratio is quite small, i.e., only a few nodes are involved in data collection and the total communication cost is extremely small. However, similar to [40], these algorithms are only applicable to aggregations.  
The works in [44; 45] studied the sampling-based quantile computation algorithms. Although the algorithm in [44] has a fixed error bound and the work in [45] only considers one-hop networks, resulting in a large amount of energy saving, the collected data can only be used to obtain the quantile information. To overcome the above problem, the algorithms to retrieve \(\epsilon\)-quantile and \((\epsilon,\delta)\)-quantile were proposed by [46], using special data structure, tree-based routing and sampling techniques, the authors proved that the error bounds of the algorithms can be arbitrarily small. However, the algorithms in [46] only store the quantile information in-network and do not conserve the kernel information of the original sensory dataset.  
Based on Bernoulli and uniform sampling techniques, another frequency and holistic aggregation algorithms were proposed by [47; 48; 49], respectively. In these works, the optimal sampling probability and sampling size are determined theoretically, so that the algorithms transmit the minimal size of sensory data during data collection while the desired query accuracies are guaranteed. Such algorithms save lots of energy during data collection; however, similar to the aforementioned ones, they are serving for specific queries and are not suitable for recovering original sensory datasets.  
An energy-efficient data collection algorithm is proposed by [50] to process skyline queries for massively multidimensional sensory data, and several effective data reduction techniques were also introduced, such as dynamic filter, tuple-cutting strategy.etc. Such algorithm is also only suitable for dealing with skyline queries and not applicable for recovering original sensory datasets.