Online Time Interval Top-k Queries in Wireless Sensor Networks

Motivated by many applications, top-k query is a fundamental operation in modern database systems. Technological advances have enabled the deployment of large-scale sensor networks for environmental monitoring and surveillance purposes, efficient processing of top-k query in such networks poses great challenges due to the unique characteristics of sensors and a vast amount of data generated by sensor networks. In this paper, we first introduce the concept of time interval top-k query that is to return k highest sensed values from the sensory data generated within a specified time interval. We then propose a filter-based algorithm for time interval top-k query evaluation, which is capable to filter out nearly a half unlikely top-k data from transmission in comparison with a well known existing solution. We also develop a novel online algorithm for answering time interval top-k queries with various ks and time intervals one by one through maintaining a materialized view that consists of historical top-k query results. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms on real sensory datasets The experimental results show that the proposed algorithms outperform existing algorithms significantly to prolong the network lifetime.