[scikit-learn] clustering on big dataset

Hi all, I wonder if there is any method to do exact clustering (hierarchy cluster) on a huge dataset where it is impossible to use distance matrix. I am considering KD-tree but every time it needs to rebuild it, consuming lots time. Any ideas?