Streaming Algorithms for Estimating High Set Similarities in LogLog Space

Estimating set similarity and detecting highly similar sets are fundamental problems in areas such as databases and machine learning. MinHash is a well-known technique for approximating Jaccard similarity of sets and has been successfully used for many applications. Its two compressed versions, <inline-formula><tex-math notation="LaTeX">$b$</tex-math><alternatives><mml:math><mml:mi>b</mml:mi></mml:math><inline-graphic xlink:href="qi-ieq1-2969423.gif"/></alternatives></inline-formula>-bit MinHash and Odd Sketch, can significantly reduce the memory usage of the MinHash, especially for estimating high similarities (i.e., similarities around 1). Although MinHash can be applied to static sets as well as streaming sets, of which elements are given in a streaming fashion, unfortunately, <inline-formula><tex-math notation="LaTeX">$b$</tex-math><alternatives><mml:math><mml:mi>b</mml:mi></mml:math><inline-graphic xlink:href="qi-ieq2-2969423.gif"/></alternatives></inline-formula>-bit MinHash and Odd Sketch fail to deal with streaming data. To solve this problem, we previously designed a memory-efficient sketch method, <italic>MaxLogHash</italic>, to accurately estimate Jaccard similarities in streaming sets. Compared with MinHash, our method uses smaller sized registers (each register consists of less than 7 bits) to build a compact sketch for each set. In this paper, we further develop a faster method, <italic>MaxLogOPH++</italic>. Compared with MaxLogHash, MaxLogOPH++ reduces the time complexity for updating each coming element from <inline-formula><tex-math notation="LaTeX">$O(k)$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:mi>k</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="qi-ieq3-2969423.gif"/></alternatives></inline-formula> to <inline-formula><tex-math notation="LaTeX">$O(1)$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="qi-ieq4-2969423.gif"/></alternatives></inline-formula> with a small additional memory. We conduct experiments on a variety of datasets, and experimental results demonstrate the efficiency and effectiveness of our methods.