[Brown CS Talks] Brown CS Seminar: Phillip B. Gibbons talk in Lubrano on 6/19/02 at 11 am

[talks-admin@list.cs.brown.edu]

			      CS Seminar

		  
		  The Department of Computer Science
			   BROWN UNIVERSITY

			      
			       presents

			  Phillip B. Gibbons


		      Intel Research Pittsburgh

				 
		  Wednesday, June 19, 2002 at 11 am
	       Lubrano Conference Room (CIT 4th floor)
	       Refreshments will be served at 10:45 am


		Wavelet Synopses with Error Guarantees
 

			       Abstract

We introduce Probabilistic Wavelet Synopses, the first wavelet-based
data reduction technique with guarantees on the accuracy of individual
approximate answers.  Whereas earlier approaches rely on deterministic
thresholding for selecting a set of ``good'' wavelet coefficients, our
technique is based on a novel, probabilistic thresholding scheme that
assigns each coefficient a probability of being retained based on its
importance to the reconstruction of individual data values, and then
flips coins to select the synopsis.  Whereas deterministic
thresholding suffers from errors that can vary widely (without bound)
and unpredictably, even for identical queries on nearly-identical
values, our probabilistic scheme provides highly-accurate answers for
individual data values in a data vector.  We propose several novel
optimization algorithms for tuning our probabilistic thresholding
scheme to minimize desired error metrics.  Experimental results on
real-world and synthetic data sets evaluate these algorithms, and
demonstrate the effectiveness of our probabilistic wavelet synopses in
providing fast, highly-accurate answers with error guarantees.

(Joint work with Minos Garofalakis, Bell Labs.)
 

		   Host: Professor Maurice Herlihy