We consider the task of performing Jaccard similarity queries over a large collection of items that are dynamically updated according to a streaming input model. An item here is a subset of a large universe $U$ of elements. A well-studied approach to address this important problem in data mining is to design \textit{fast-similarity data sketches}. In this paper, we focus on \textit{global solutions} for this problem, i.e., a single data structure which is able to answer both \textit{Similarity Estimation} and \textit{All-Candidate Pairs} queries, while also dynamically managing an arbitrary, online sequence of element insertions and deletions received in input.

In this talk, we introduce and provide an in-depth analysis of a dynamic, buffered version of the well-known $k$-min hash sketch. This buffered version better manages critical update operations thus significantly reducing the number of times the sketch needs to be rebuilt from scratch using expensive recovery queries. We prove that the \textit{buffered} $k$-min hash uses $O(k \log |U|)$ memory words per subset and that its \textit{amortized} update time per insertion/deletion is $O(k \log |U|)$ \textit{with high probability}. Moreover, our data structure can return the $k$-min hash signature of any subset in $O(k)$ time, and this signature is exactly the same signature that would be computed from scratch (and thus the quality of the signature is the same as the one guaranteed by the static $k$-min hash