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

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