Probabilistic filters: a stream protocol for continuous probabilistic queries

Abstract

Pervasive applications, such as natural habitat monitoring and location-based services, have attracted plenty of research interest. These applications, which deploy a lot of sensor devices to collect data from external environments, often have limited network bandwidth and battery resources. The sensors also cannot record accurate values. The uncertainty of data captured by a sensor should thus be considered for query evaluation. To this end, probabilistic queries, which consider data impreciseness and provide statistical guarantees in answers, have been recently studied. We investigate the evaluation of a long-standing (or continuous) probabilistic query in a multi-user environment. We propose the probabilistic filter protocol, which helps remote sensor devices to decide whether values collected should be reported to the query server. This protocol can significantly reduce the communication and energy costs of sensor devices. We further introduce probabilistic tolerance, which allows a query user to relax answer accuracy, in order to further reduce the utilization of resources. We extend the protocol to facilitate concurrent handling of multiple user query requests. Experimental results on sensor and location data show that our method significantly reduces communication, energy consumption, and computational overhead of the system. © 2012 Elsevier Ltd. All rights reserved.