Поиск близости

Как приложение выполняет поиск по близости? Например, пользователь вводит почтовый код, а затем приложение перечисляет все компании в пределах 20 миль, заказанных по близости.

Я хочу построить что-то подобное в PHP и MySQL. Правильно ли этот подход?

Получить адреса для местоположений, которые меня интересуют и хранят в моей базе данных
Геокодировать все адреса с помощью службы геокодирования Google
Напишите запрос базы данных, который включает формулу Хаверсина, чтобы выполнить поиск по близости и упорядочить

Это нормально? На шаге 3 я собираюсь рассчитать близость для каждого запроса. Лучше ли иметь таблицу PROXIMITY, в которой указано расстояние между каждым бизнесом и несколькими ссылочными позициями?

Ответ 1

Если есть достаточное количество записей для скорости, это способ их индексации заранее.

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

Ответ 2

Мы используем это, чтобы сделать много тысяч очков. Важно, если вы выполняете это в SQL, чтобы иметь индекс в столбце Широта и долгота. Мы попытались сделать это в SQL 2008 с пространственными индексами, но мы действительно не видели увеличения производительности, которого мы ожидали. Хотя, если вы хотите рассчитать на определенном расстоянии от ZIP, вам нужно подумать о том, собираетесь ли вы использовать ZIP-центр или многоугольное представление почтового индекса.

Haversine forumla - хорошее место для начала.

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

SELECT
        [DistanceRadius]=
        69.09 *
        DEGREES(
          ACOS(
            SIN( RADIANS(latitude) )*SIN( RADIANS(@ziplat) ) 
           +
            COS( RADIANS(latitude) )*COS( RADIANS(@ziplat) ) 
           *
            COS( RADIANS(longitude - (@ziplon)) )
          )
        )
        ,*
        FROM
            table

    ) sub
WHERE
    sub.DistanceRadius < @radius

Ответ 3

Мы делаем это примерно для 1200 местоположений. Я бы просто использовал формулу Хаверсина "на лету", хотя в зависимости от вашего приложения лучше было бы хранить его в PHP вместо SQL. (Наша реализация в .net, поэтому ваше перемещение может меняться).

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

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

Мы действительно посмотрели на сохранение всех возможных комбинаций в нашей базе данных. На самом деле это звучит так, будто это может быть большой магазин данных, но это действительно не в большом объеме вещей. С индексами это может быть довольно быстро, и вам не нужно беспокоиться об оптимизации алгоритмов и т.д. Мы решили против этого, потому что у нас было уравнение в С#, и это позволило нам кэшировать информацию, необходимую для выполнения всех вычислений в бизнес-уровня. Либо все будет работать отлично, это вопрос вашего предпочтения.