Explain how MinHash LSH works and why it runs in linear...

MinHash LSH works by creating a K-dimensional signature for each document. The LSH component splits this signature into ‘b’ bands, each containing ‘r’ rows. Two documents are considered candidates for a near-duplicate match if they share at least one identical band. Because each document only performs ‘b’ hash lookups, the total work is O(nK), which is linear relative to the corpus size, avoiding the quadratic cost of explicit pairwise comparisons.