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 \times 275$ matrix. I want to cluster these bit-vectors. I have tried single link hierarchical clustering on a small data set, $3000 \times 275$, and 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 a 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(C_1,C_2)< t$; then: merge $C_1$ and $C_2$).
The time complexity for my new approach is $O(p) + O(pq)$, where $p$ is the number of chunks and $q$ the average number of clusters in each chunk. Note: I assume that when hierarchical clustering is applied, each chuck 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.