Поиск местоположения / близости на большом наборе записей

Скажем, у меня есть таблица базы данных, представляющая пользователей с потенциально миллионами записей (желаемое за действительное). Эта таблица содержит всю информацию о каждом пользователе, включая информацию о его местонахождении:

• город
• Округ / штат и т. Д.
• Страна
• широта
• Долгота
• Geohash на основе значений широты / долготы.

Я хотел бы реализовать функцию, при которой вошедший в систему пользователь может искать других пользователей, которые находятся поблизости.

В идеале я хотел бы получить, скажем, 20 пользователей, которые географически ближе всего к пользователю, затем следующие 20, следующие 20 и т. Д. Поэтому, по сути, я хочу иметь возможность упорядочить свою таблицу пользователей по расстояние от определенный момент.

Подход 1

У меня есть некоторый предыдущий опыт работы с формулой haversine, которую я использовал для расчета расстояния между одной точкой и несколькими сотнями других. Этот подход был бы идеальным для относительно небольшого набора записей, но я боюсь, что он станет невероятно медленным с таким большим набором записей.

Подход 2

Кроме того, я провел некоторые исследования в области геохеширования, и я понимаю, как вычисляется хеш, и я получил теорию о том, как он представляет местоположение и как теряется точность при более коротких разрешениях. Я, конечно, мог бы захватить пользователей, которые расположены вблизи географической области пользователя, путем захвата пользователей, которые имеют начало, похожее на их геохэш (основываясь на указанной мной точности, и, возможно, просматривая соседние регионы), но это не решает проблему. необходимости сортировки по местоположению. Этот подход также не подходит для краевых случаев, когда 2 пользователя могут быть очень близко друг к другу, но лежать близко к краям 2 областей, представленных геохешем.

Любые идеи / предложения по подходу будет принята с благодарностью. Я не ищу код в частности, но ссылки на хорошие примеры и ресурсы были бы полезны.

Спасибо,
Джонатон

редактировать

Подход 3

После некоторых размышлений я нашел другое потенциальное решение для рассмотрения. После получения информации о местоположении каждого пользователя я буду хранить информацию о местоположении (город / район, область, страна, широта, долгота, возможно, геохэш) в отдельной таблице (скажем, locations). Я бы тогда подключил пользователя к локации по внешнему ключу. Это дало бы мне гораздо меньший набор данных для работы. Чтобы найти соседних пользователей, я мог бы просто найти другие местоположения, которые находятся близко к местоположению пользователя, а затем использовать их идентификаторы для поиска других пользователей. Возможно, какое-то кэширование могло бы быть реализовано путем сохранения списка идентификаторов соседних местоположений для каждого местоположения.