On Efficient Processing of Continuous Historical Top- $k$ Queries in Sensor Networks

The top-k query has long been an important topic in computer science. Efficient implementation of top-k queries is the key for information searching. In this paper, we develop the Efficient algorithm for the Continuous Historical Top-k (ECHT) extraction, which is a novel algorithm that can effectively process the continuous historical top-k query. A simple top-k extraction algorithm based on aggregation is used for user query processing, and two additional steps on the filter setting by which individual nodes do not have to report all their readings are proposed to further reduce communication cost. To the best of our knowledge, this is the first work for continuous historical top-k query processing in sensor networks, and our simulation results show that our schemes can reduce the total communication cost by up to two orders of magnitude, as compared with the centralized scheme or a straightforward extension from the previous top-k algorithm on a continuous monitoring query.