Близость поиска - PullRequest
Новая
       13

Близость поиска

21 голосов
/ 04 ноября 2008

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

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

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

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

Ответы [ 3 ]

11 голосов
/ 04 ноября 2008

Мы используем это, чтобы набрать много тысяч очков. Важно, если вы выполняете это в SQL, чтобы иметь индекс для столбца Широта и Долгота. Мы пытались сделать это в SQL 2008 с пространственными индексами, но мы действительно не увидели ожидаемого повышения производительности. Хотя, если вы хотите вычислить в пределах определенного расстояния от ZIP, вам нужно подумать, собираетесь ли вы использовать 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
9 голосов
/ 04 ноября 2008

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

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

2 голосов
/ 04 ноября 2008

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

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

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

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

...