Improving \textit{Tug-of-War} sketch using Control-Variates method

Rameshwar Pratap, Bhisham Dev Verma, Raghav Kulkarni

Computing space-efficient summary, or \textit{a.k.a. sketches}, of large data, is a central problem in the streaming algorithm. Such sketches are used to answer \textit{post-hoc} q…