<p>Regarding the second step b) there are recent developments which significantly speed up the calculation of signatures:</p>

<ul>
<li>Optimal Densification for Fast and Accurate Minwise Hashing, 2017,
<a href="https://arxiv.org/abs/1703.04664" rel="nofollow noreferrer">https://arxiv.org/abs/1703.04664</a></li>
<li>Fast Similarity Sketching, 2017, <a href="https://arxiv.org/abs/1704.04370" rel="nofollow noreferrer">https://arxiv.org/abs/1704.04370</a></li>
<li>SuperMinHash - A New Minwise Hashing Algorithm for Jaccard Similarity Estimation, 2017, <a href="https://arxiv.org/abs/1706.05698" rel="nofollow noreferrer">https://arxiv.org/abs/1706.05698</a></li>
<li>ProbMinHash - A Class of Locality-Sensitive Hash Algorithms for the (Probability) Jaccard Similarity, 2019, <a href="https://arxiv.org/pdf/1911.00675.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1911.00675.pdf</a></li>
</ul>
State-of-the-art method for large-scale near-duplicate detection of documents?
<p>To my understanding, the scientific consensus in NLP is that the most effective method for near-duplicate detection in large-scale scientific  document collections (more than 1 billion documents) is the one found here: </p>

<p><a href="http://infolab.stanford.edu/~ullman/mmds/ch3.pdf" rel="noreferrer">http://infolab.stanford.edu/~ullman/mmds/ch3.pdf</a></p>

<p>which can be briefly described by: </p>

<p>a) shingling of documents 
b) minhashing to obtain theminhash signatures of the shingles
c) locality-sensitive hashing to avoid doing pairwise similarity calculations for all signatures but instead focus only to pairs within buckets.</p>

<p>I am ready to implement this algorithm in Map-Reduce or Spark, but because I am new to the field (I have been reading upon large-scale near-duplicate detection for about two weeks) and the above was published quite a few years ago, I am wondering whether there are known limitations of the above algorithm and whether there are different approaches that are more efficient (offering a more appealing performance/complexity trade-off ). </p>

<p>Thanks in advance! </p>