I have a huge data set (33K), each represented as a bit-vector of 275-dimensions. basically my data set can be represented as a 33000 x 275 matrix. I want to cluster these bit-vectors. I have tried single link hierarchical clustering on a small data set, 3000 x 275, the result is promising.
I know that single link hierarchical clustering algorithm is not scalable as the time complexity is $O(n^2)$. I am planning to apply divide-and-conquer approach, i.e., divide the dataset into chunks of equal size and cluster each chunks individually and finally merge the clustered chunks based on distance (if: $d(C1,C2)< t$; then: merge $C1$ and $C2$).
The time complexity for my new approach is $O(p)O(1) + O(pq)$, where $p$ is number of chunks and $q$ is the average number of clusters in each chunk.
Note: I assume that when hierarchical clustering is applied, each chunck will take same amount of time and its constant for all chunks, thus $O(n^2)$ will become $O(1)$.
I want to know, whether the above mentioned clustering approach is feasible and efficient. or is there any logic flaws in applying divide-and-conquer approach for clustering