Recovering Information from Summary Data

dc.contributor.authorFaloutsos, Christosen_US
dc.contributor.authorJagadish, H.V.en_US
dc.contributor.authorSidiropoulos, N.D.en_US
dc.contributor.departmentISRen_US
dc.date.accessioned2007-05-23T10:03:37Z
dc.date.available2007-05-23T10:03:37Z
dc.date.issued1997en_US
dc.description.abstractData is often stored in summarized form, as a histogram of aggregates (COUNTs,SUMs, or AVeraGes) over specified ranges. Queries regarding specific values, or ranges different from those stored, cannot be answered exactly from the summarized data. In this paper we study how to estimate the original detail data from the stored summary.<P>We formulate this task as an inverse problem, specifying a well-defined cost function that has to be optimized under constraints.<P>In particular, we propose the use of a Linear Regularization method, which ﲭaximizes the smoothness of the estimate. Our main theoretical contribution is a Theorem, which shows that, for smooth enough distributions, we can achieve full recovery from summary data.<P>Our theorem is closely related to the well known Shannon-Nyquist sampling theorem.<P>We describe how to apply this theory to a variety of database problems, that involve partial information, such as OLAP, data warehousing and histograms in query optimization. Our main practical contribution is that the Linear Regularization method is extremely effective, both on synthetic and on real data. Our experiments show that the proposed approach almost consistently outperforms the ﲵniformity assumption, achieving significant savings in root-mean-square error: up to 20% for stock price data, and up to 90% for smoother data sets.en_US
dc.format.extent1283165 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/5844
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1997-7en_US
dc.subjectestimationen_US
dc.subjectfilteringen_US
dc.subjectsignal processingen_US
dc.subjectdatabase management systemsen_US
dc.subjectSystems Integration Methodologyen_US
dc.titleRecovering Information from Summary Dataen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
TR_97-7.pdf
Size:
1.22 MB
Format:
Adobe Portable Document Format