SAF:  a similarity-based adaptable framework for approximate querying answering based on time series forecasting

Daniela Tulone and Sam Madden

We propose an energy--efficient framework, called SAF Similarity--based Adaptable query Framework} \cite{PAQ, SAF}), for approximate querying and detecting outlier values in sensor networks. The idea is to combine local AR models built at each node into a global model stored at the root of the network
(\emph{the sink}) that is used to approximately answer user queries. Our approach uses dramatically fewer transmissions than previous approximate approaches by using AR models and organizing the network into \emph{clusters} based on data similarity between nodes. Our definition of data similarity is based on the coefficients of local AR models stored at the sink, which reduces energy consumption over techniques that directly compare data values, and allows us to
derive an efficient clustering algorithm that is \emph{provably optimal} in the number of clusters formed by the network. Our clusters have several interesting features that make them suitable also for mobile networks: first, they can capture similarity between nodes that are not geographically adjacent; second, cluster membership adapts at no additional cost; third, nodes within a cluster are not required to track the membership of other nodes in the cluster. Furthermore, SAF provides \emph{provably correct} error bounds and allows the user to dynamically tune answer quality to answer queries in an energy and resource efficient manner.