Успешно решил задачу кластеризации точек на карте. Благодаря волшебным postgis’овским индексам — за приемлемое время.
Я так понимаю, для любой сложной проблемы есть два решения: обычный — когда ты долго пердолишь в математику, machine learning и еще хуй пойми что, и SQL’ный — когда ты нахуяриваешь еще индексов и O(N²) рассасывается сам собой.

Разработчики PostGIS успешно решили* проблему поиска ближайших соседей путем спонсирования разработчиков PostgreSQL, чтобы те подковыряли двумерные индексы. К сожалению, работает все это только для геометрических объектов, так что на больших расстояниях и на 180-м меридиане придется сосать хуи.

*нашли способ делать запросы за приемлемое время