Abstract: In the last few years, we have been witnessing an evergrowing need for continuous observation and monitoring applications. This need is driven by recent technological advances that have made streaming applications possible, and by the fact that analysts in various domains have realized the value that such applications can provide. In this paper, we propose a general framework for computing efficiently an approximation of multi-dimensional distributions of streaming data. This framework enables the development of a wide variety of complex streaming applications. In addition, we demonstrate how our framework can operate in a distributed fashion, thus, making better use of the available resources. We motivate our techniques using two concrete problems, both in the challening context of resource-constrained sensor networks. The first problem is outlier detection, while the second is detection and tracking of homogeneous regions. Experiments with synthetic and real data show that our method is efficient and accurate, and compares favorably to other proposed techniques for both the problems that we studied.