Calibration and Profile based Synopses Error Estimation and Synopses Reconciliation

An important factor in the effective utilization of data synopses is the ability to have good a priori estimates on their expected query approximation errors. Such estimates are essential for the appropriate decisions regarding which synopses to build and how much space to allocate to them, which are also at the heart of the synopses reconciliation problem. We present a novel synopses error estimation method based on the construction of synopses-dependant error estimation functions. These functions are computed in a pre-processing stage using a calibration method. Subsequently, they are used to provide ad hoc error estimation w.r.t. given data sets and query workloads based only on their statistical profiles. We also present a novel approach to synopses reconciliation, using the error-estimation functions within synopses reconciliation algorithms, gaining significant efficiency improvements by lowering to a minimum and even avoiding interference to the operational databases. Our method enables the first practical solution for the dynamic synopses reconciliation problem.