Resource-unintensive (low complexity) methods for large-scale unsupervised clustering?

I'm working on an issue where I need to cluster user types on a scale in an unsupervised manner. I've been looking at the basics like KNN and K-means etc., but I found it hard to scale, as these methods are quite resource-intensive.

What are some highly scalable clustering methods that have a low complexity (big O)?