| Due to measurement uncertainty, often, instead of the actual values xi of the measured quantities, we only know the intervals x i = [x˜i - Delta i, x˜i + Delta i], where x˜i is the measured value and Deltai is the upper bound on the measurement error (provided, e.g., by the manufacturer of the measuring instrument). In such situations, instead of the exact value of the sample statistics such as covariance Cx,y, we can only have an interval Cx,y of possible values of this statistic. It is known that in general, computing such an interval C x,y for Cx,y is an NP-hard problem. Previously, an efficient algorithm was known for computing this range Cx,y for the case when the measurements are accurate enough---so that the intervals corresponding to different measurements do not intersect much. In this thesis, we provide a new efficient algorithm for computing Cx,y for the case when interval uncertainty comes from the need for privacy protection in statistical databases. |
