Séminaire COATI : Luciano Gualà

Luciano Gualà, Associate Professor, University of Rome « Tor Vergata » will give a seminar on November 12, 2025 at 2:00 p.m. by videoconference at the Centre Inria d'Université Côte d'Azur in the Euler building, room E006.

 

TITLE : 

Maintaining $k$-MinHash Signatures over Fully-Dynamic Data Streams with Recovery


ABSTRACT : 

We consider the task of performing Jaccard similarity queries over a large collection of data sets that are dynamically updated according to a streaming input model. A data set 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 unique data structure which is able to answer to both \textit{Similarity Estimation} and \textit{All-Candidate Pairs} queries, and, moreover, to dynamically manage an arbitrary, online  sequence of element insertions and deletions received in input.
We introduce and provide an in-depth analysis of a dynamic, buffered version of the well-known $k$-MinHash 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$-MinHash uses $O(k \log |U|)$ memory words per set and that its \textit{amortized} update time per insertion/deletion is $O(k \log |U|)$ \textit{with high probability}. Moreover, it outputs the $k$-MinHash signature of any set $A$ in $O(k)$ time, and this signature is exactly the same signature as it was computed from scratch from $A$ (and thus the quality of the signature is the one guaranteed by the static $k$-MinHash).  
The analytical and experimental comparisons with the other, state-of-the-art global solutions for this problem given in [Bury et al.,WSDM'18] globally show that the \textit{buffered} $k$-MinHash turns out to be competitive in a wide and relevant range  of the online input parameters.

joint work with: Andrea Clementi, Luca Pepè Sciarria, Alessandro Straziota (paper presented at WSDM'25)