Lattice Histograms: a Resilient Synopsis Structure

Speaker: Panagiotis Karras

Abstract

Despite the surge of interest in data reduction techniques over the past years, no known method has been proposed to date that can always achieve approximation quality preferable to that of the well-established V-optimal histogram and its variants. In this talk, we introduce the lattice histogram: a novel data reduction method that discovers and exploits any arbitrary hierarchy in the data. This structure achieves approximation quality provably at least as high as an optimal histogram for any data reduction problem without a scalability disadvantage. We develop a general algorithm that derives lattice histograms under a general error metric as well as a specialized one for maximum-error metrics. We corroborate the superiority of Lattice Histograms in approximation quality over previous techniques through experimentation.