Algorithm to construct similarity structure from hash lookup table I have constructed a lookup table using locality-sensitive hashing for comparing nearly similar documents/records. If two records (columns) have the same hash value in a row, they are considered to be similar. For example, the structure is 

   R1 R2 R3 R4 R5
b1 a1 a2 a3 a2 a5 .....
b2 a2 a4 a1 a4 a4 ..... 
b3 a3 a5 a3 a7 a4....


Since each band holds similar records, similar record sets will be

S1 = {R2,R4}
S2 = {R2, R4, R5}
S3 = {R1,R3}


And the merged similarity structures will be 

S1' = {R2,R4,R5}
S2' = {R1,R3}


I want to span the matrix and map all similarity structures so I have buckets of similar records. The dimensionality of the hash table is large, hence a naive approach is not likely to work. What types of algorithms should I consider to achieve this efficiently?

Edit 1:
Question updated to clarify more on the objective
The algorithm you are asking about is very straightforward. 

What you do, you are looking for connected components in a certain graph where edges are determined by matching hash values. You can implement this with a modification of the disjoint-set data structure. 

Your particular variation would be that apart from keeping track of vertices in each component, you have to keep track of m (number of rows) sets of hash values that have been found for each component.