An adaptive refinement-based algorithm for median queries in wireless sensor networks
Khaled Ammar, Mário A. Nascimento, Johannes Niedermayer · 2011
A number of papers concerning algorithms for processing typical aggregate queries, e.g., Max and Top-k, within a wireless sensor network have been published in recent years. However, relatively few have addressed Median queries. In this paper we propose an exact algorithm to process Median queries that is based on a series of refinement queries. Each refinement query is a Histogram query, with the aim of incrementally refining the range where the actual median value resides. Because the cost of a Histogram query depends mostly on the structure of the histogram itself, we aim at optimizing each Histogram query, hence optimizing the overall cost of the Median query. Experiments, using synthetic and real datasets, show that our proposed approach yields up to 50% less traffic than a TAG-based solution and only about 25% more traffic on average than the minimum required.