Date Added: Oct 2009
There is a growing realization that uncertain information is a first-class citizen in modern database management. As such, the authors need techniques to correctly and efficiently process uncertain data in database systems. In particular, data reduction techniques that can produce concise, accurate synopses of large probabilistic relations are crucial. Similar to their deterministic relation counterparts, such compact probabilistic data synopses can form the foundation for human understanding and interactive data exploration, probabilistic query planning and optimization, and fast approximate query processing in probabilistic database systems. In this paper, the authors introduce definitions and algorithms for building histogram- and Haar wavelet-based synopses on probabilistic data.