Stuffed IBLTs: Optimal Linear Multiset Sketches

Jonas Klausen, Rasmus Pagh, Stefan Walzer

A \emph{linear sketch} is a randomized linear mapping of a vector $v$ to a lower dimensional sketch vector, designed to preserve relevant information about $v$. We consider sketche…