Используйте что-то похожее на метод, который вы описали в своем вопросе, чтобы получить приблизительный набор результатов, затем уменьшите это приблизительное значение, выполнив правильные вычисления. Если вы правильно выберете размер своей сетки (то есть, сколько вы округлите свои координаты), вы можете, по крайней мере, надеяться сократить объем работы, выполняемой до приемлемого уровня, хотя вам придется управлять размером сетки.
Например, расширение earthdistance для PostgreSQL работает путем преобразования пар широта / длинна в (x, y, z) декартовых координат, моделируя Землю как единую сферу. PostgreSQL имеет сложную систему индексации, которая позволяет индексировать эти координаты или блоки вокруг них в R-деревья, но вы можете объединить что-то, что по-прежнему полезно без этого.
Если вы возьмете (x, y, z) в три раза и округлите - т.е. умножите на некоторый коэффициент и укоротите до целого числа - тогда у вас будет три целых числа, которые вы можете объединить, чтобы получить «имя блока», которое идентифицирует блок в вашей "сетке", в которой находится точка.
Если вы хотите найти все точки в пределах X км от некоторой целевой точки, вы генерируете все «имена ящиков» вокруг этой точки (как только вы преобразуете свою целевую точку в тройную (x, y, z) как ну, это просто) и уберите все ящики, которые не пересекают поверхность Земли (обманщик, но вам скажет использование формулы x^2+y^2+z^2=R^2 в каждом углу), в итоге вы получите список ящиков, которые могут быть целевые так что просто ищите все точки, соответствующие одному из этих полей, что также даст вам несколько дополнительных очков. Таким образом, в качестве заключительного этапа вам необходимо рассчитать фактическое расстояние до вашей целевой точки и устранить некоторые (опять же, это можно ускорить, работая в декартовых координатах и конвертируя целевой радиус большого круга в секущее расстояние).
Перепутывание сводится к тому, что вам не нужно искать слишком много ящиков, но в то же время не приносите слишком много дополнительных очков. Я считаю полезным индексировать каждую точку на нескольких разных сетках (например, разрешения 1 км, 5 км, 25 км, 125 км и т. Д.). В идеале вы хотите искать только одно поле, помните, что оно увеличивается как минимум до 27, как только ваш целевой радиус превышает размер вашей сетки.
Я использовал эту технику для построения пространственного индекса с использованием Lucene, а не для расчетов в базах данных SQL. Это работает, хотя есть некоторые сложности, чтобы настроить его, и индексы требуют времени для генерации и довольно велики. Использование R-дерева для хранения всех координат является гораздо более приятным подходом, но потребовало бы больше пользовательского кодирования - этот метод в основном просто требует быстрого поиска в хеш-таблицах (поэтому, вероятно, будет работать хорошо со всеми базами данных NoSQL, которые являются ярость в наши дни, и должна использоваться в базе данных SQL тоже).