Wireless Sensor Networks (WSN) are often deployed to sample the desired environmental attributes and deliver the acquired samples to the sink for processing, analysis or simulations as per the application needs. Many applications stipulate high granularity and data accuracy that results in high data volumes. Sensor nodes are battery powered and sending the requested large amount of data rapidly depletes their energy. Fortunately, the environmental attributes (e.g., temperature, pressure) often exhibit spatial and temporal correlations. Moreover, a large class of applications such as scientific measurement and forensics tolerate high latencies for sensor data collection. Accordingly, we develop a fully distributed adaptive technique for spatial and temporal innetwork data compression with accuracy guarantees. We exploit the spatio-temporal correlation of sensor readings while benefiting from possible data delivery latency tolerance to further minimize the amount of data to be transported to the sink. Using real data, we demonstrate that our proposed scheme can provide significant communication/energy savings without sacrificing the accuracy of collected data. In our simulations, we achieved data compression of up to 95% on the raw data requiring around 5% of the original data to be transported to the sink. Copyright 2011 ACM.