Алгоритм Clarans (Clustering Large Applications based upon RANdomized Search) формулирует задачу кластеризации как случайный поиск в графе. В результате работы этого алгоритма совокупность узлов графа представляет собой разбиение множества данных на число кластеров, определенное пользователем. «Качество» полученных кластеров определяется при помощи критериальной функции. Алгоритм Clarans сортирует все возможные разбиения множества данных в поисках приемлемого решения. Поиск решения останавливается в том узле, где достигается минимум среди предопределенного числа локальных минимумов.
Среди новых масштабируемых алгоритмов также можно отметить алгоритм CURE — алгоритм иерархической кластеризации и алгоритм DBScan , где понятие кластера формулируется с использованием концепции плотности (density).
Основным недостатком алгоритмов BIRCH, Clarans, CURE, DBScan является то обстоятельство, что они требуют задания некоторых порогов плотности точек, а это не всегда приемлемо. Эти ограничения обусловлены тем, что описанные алгоритмы ориентированы на сверхбольшие базы данных и не могут пользоваться большими вычислительными ресурсами.
Над масштабируемыми методами сейчас активно работают многие исследователи, основная задача которых — преодолеть недостатки алгоритмов, существующих на сегодняшний день.