MinHashing vs SimHashing Suppose I have five sets I'd like to cluster. I understand that the SimHashing technique described here:

https://moultano.wordpress.com/2010/01/21/simple-simhashing-3kbzhsxyg4467-6/

could yield three clusters ({A}, {B,C,D} and {E}), for instance, if its results were:

A -&gt; h01
B -&gt; h02
C -&gt; h02
D -&gt; h02
E -&gt; h03


Similarly, the MinHashing technique described in the Chapter 3 of the MMDS book:

http://infolab.stanford.edu/~ullman/mmds/ch3.pdf

could also yield the same three clusters if its results were:

A -&gt; h01 - h02 - h03

B -&gt; h04 - h05 - h06
      |
C -&gt; h04 - h07 - h08
                  |
D -&gt; h09 - h10 - h08

E -&gt; h11 - h12 - h13


(Each set corresponds to a MH signature composed of three "bands", and two sets are grouped if at least one of their signature bands is matching. More bands would mean more matching chances.)

However I have several questions related to these:

(1) Can SH be understood as a single band version of MH?

(2) Does MH necessarily imply the use of a data structure like Union-Find to build the clusters?

(3) Am I right in thinking that the clusters, in both techniques, are actually "pre-clusters", in the sense that they are just sets of "candidate pairs"?

(4) If (3) is true, does it imply that I still have to do an $O(n^2)$ search inside each "pre-cluster", to partition them further into "real" clusters? (which might be reasonable if I have a lot of small and fairly balanced pre-clusters, not so much otherwise)
As correctly pointed out above MinHash and SimHash both belong to Locality Sensitive Hashing. 
Reference: https://en.wikipedia.org/wiki/Locality-sensitive_hashing

The main difference between the two is the way collision is handled,


SimHash, uses cosine similarity
MinHash, uses Jaccard Index.


Answers to your questions:


No. They uses different collision handling techniques to validate similarity. Also there is a variant on single Hash Function for Min Hash but it works differently. For more details, check the following reference out, https://en.wikipedia.org/wiki/MinHash (Variant with a single hash function) 
Yes, https://github.com/chrisjmccormick/MinHash/blob/master/runMinHashExample.py
I think the complexity can be reduced to $O(n \log n)$ with modified form of binary search while clustering.