On Efficient Processing of Continuous Historical Top- $k$ Queries in Sensor Networks
Jie Cheng, Hongbo Jiang, Jiangchuan Liu, Wenyu Liu, Chonggang Wang · IEEE Transactions on Vehicular Technology · 2011
The top-kquery has long been an important topic in computer science. Efficient implementation of top-kqueries 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-kquery. A simple top-kextraction 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-kquery 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-kalgorithm on a continuous monitoring query.