Каков наилучший способ запросить в базе данных записи в радиусе n миль от почтового индекса?

Question

У меня есть список записей в моей базе данных, и каждая запись связана с почтовым индексом.

Какова "наилучшая практика" для запроса всех записей в моей базе данных, чтобы найти все записи, которые находятся в пределах n миль от другого почтового индекса?

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

Это кажется ужасно дорогостоящим с точки зрения вычислений для такого распространенного запроса.

Я также рассматривал возможность предварительного вычисления для всех пар, но оно кажется слишком большим, чтобы его также рассматривать.В США насчитывается примерно ~ 40 000 почтовых индексов.Таким образом, база данных всех пар каждого почтового индекса будет составлять (40 000) ^ 2, или 1,6 миллиарда записей.

Я знаю, что это распространенная проблема на веб-сайтах, поэтому, надеюсь, кто-нибудь сможет указать мне правильное направление для наилучшего способа.Я использую SQL Server 2008 и если там есть готовые решения, то это здорово, потому что я действительно не хочу заново изобретать колесо в данном случае.

---

Связанный с этим Вопрос: Получение всех почтовых индексов в радиусе действия (это мне не помогло)
Кроме того, я знаю об этом Кузница источника проект, но он заброшен и больше не используется.

Answer 1

Я бы запустил запрос, который вернул бы все записи, заключенные в квадратные скобки в квадратном конверте, охватывающем радиальный круг поиска (minlat < лат < макслат и минлонг < длинный < maxlong), а затем обработайте это, чтобы вернуть только точки внутри самой окружности радиуса.(Убедитесь, что ваши поля lat и long проиндексированы).

Если вы хотели понарошку, SQL server поддерживает пространственные индексы.

Answer 2

Я бегу сайт, который должен выполнять этот запрос примерно раз в секунду для каждого пользователя, и вот что я узнал:

Прежде всего, убедитесь, что ваша таблица местоположений имеет индексы в широте и Lon.Это разница между временем отклика 20 мс и 15 с, если у вас миллионы записей.

Начните с запроса в виде ограничительной рамки, чтобы получить набор местоположений для работы.Затем рассчитайте по ним расстояния, отсортируйте, и если вы придираетесь к точности, отфильтруйте несколько.

Честно говоря, я бы не стал беспокоиться о предварительном вычислении чего бы то ни было.Как я уже сказал, я выполняю этот тип запроса к таблице местоположений с 6 000 000 записями, и обычно он возвращает результаты в <50 мс.В зависимости от ваших потребностей, это действительно должно быть достаточно быстро.

Удачи вам!

Answer 3

На самом деле это очень трудная для решения проблема.Я бы порекомендовал вам немного подшутить, предварительно создав базу данных.Создайте сетку любой близости, которую вам нужно найти, например, возьмите каждые 10 миль в каждом направлении, добавьте запись в базу данных для каждого почтового индекса для этой точки сетки и расстояния, а затем, когда поступает запрос, вы сначала переводите точку запроса в одну из ваших точек сетки.Теперь вы можете довольно легко посмотреть расстояние.

Это решение в основном означает обмен пространства на время, так что вы можете быстро получить довольно большую базу данных.Хорошая новость заключается в том, что:это очень простые данные для индексации.

Answer 4

Вам следует взглянуть на GeoNames.org.Вы можете запросить ихвеб-сервис для того, что вы ищете, или вы можете расширить свою базу данных.