Рассчитайте расстояние между почтовыми индексами… И пользователями.

https://stackoverflow.com/questions/3983325

09-10-2019
|

Вопрос

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

Я создал сайт знакомств (давно исчез) примерно в 2000 году, и одной из задач было вычислить расстояние между пользователями, чтобы мы могли представить ваши «совпадения» в радиусе X миль.Чтобы просто сформулировать проблему, учитывая следующую схему базы данных (примерно):

ТАБЛИЦА ПОЛЬЗОВАТЕЛЕЙ Идентификатор пользователя UserName (Имя пользователя) Почтовый индекс

ТАБЛИЦА ПОЧТОВЫХ ИНДЕКСОВ Почтовый индекс Широта Долгота

При объединении USER и ZIPCODE в USER.ZipCode = ZIPCODE.ZipCode.

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

Мы использовали Данные переписи 2000 года, в котором есть таблицы почтовых индексов и их приблизительной широты и долготы.

Мы также использовали Формула Хаверсина вычислить расстояния между любыми двумя точками на сфере...на самом деле довольно простая математика.

Вопрос, по крайней мере для нас, 19-летних студентов колледжа, на самом деле заключался в том, как эффективно вычислять и/хранить расстояния от всех участников до всех остальных участников.Один из подходов (тот, который мы использовали) заключался бы в импорте всех данных и расчете расстояния ОТ каждого почтового индекса ДО каждого другого почтового индекса.Затем вы сохраните и проиндексируете результаты.Что-то вроде:

SELECT  User.UserId
FROM    ZipCode AS MyZipCode
        INNER JOIN ZipDistance ON MyZipCode.ZipCode = ZipDistance.MyZipCode
        INNER JOIN ZipCode AS TheirZipCode ON ZipDistance.OtherZipCode = TheirZipCode.ZipCode
        INNER JOIN User AS User ON TheirZipCode.ZipCode = User.ZipCode
WHERE   ( MyZipCode.ZipCode = 75044 )
        AND ( ZipDistance.Distance < 50 )

Проблема, конечно, в том, что в таблице ZipDistance будет МНОГО строк.Он не совсем неработоспособен, но он действительно большой.Кроме того, требуется полная предварительная работа над всем набором данных, что также не является неуправляемым, но не обязательно желательным.

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

Решение

Хорошо, во-первых, вам не обязательно использовать здесь формулу Хаверсина.Для больших расстояний, когда менее точная формула дает большую ошибку, пользователей не волнует, составляет ли совпадение плюс или минус несколько миль, а для более близких расстояний ошибка очень мала.На сайте представлены более простые (для расчета) формулы. Географическое расстояние Статья в Википедии.

Поскольку почтовые индексы не имеют ничего общего с равномерным расположением, любой процесс, который разделяет их равномерно, сильно пострадает в районах, где они плотно сгруппированы (хорошим примером является восточное побережье возле округа Колумбия).Если вы хотите визуальное сравнение, посмотрите http://benfry.com/zipdecode и сравните префикс почтового индекса 89 с 07.

Гораздо лучший способ справиться с индексацией этого пространства — использовать такую структуру данных, как Четырехдерево или R-дерево.Эта структура позволяет выполнять пространственный и дистанционный поиск по данным, которые расположены неравномерно.

Вот как выглядит Quadtree:

Quadtree

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

Конечно, поскольку это довольно распространенное дело, кто-то другой уже сделал за вас тяжелую часть.Поскольку вы не указали, какую базу данных используете, расширение PostgreSQL ПостГИС послужит примером.PostGIS включает возможность создания пространственных индексов R-дерева, которые позволяют выполнять эффективные пространственные запросы.

После того как вы импортировали данные и построили пространственный индекс, запрос расстояния будет выглядеть следующим образом:

SELECT zip
FROM zipcode
WHERE
geom && expand(transform(PointFromText('POINT(-116.768347 33.911404)', 4269),32661), 16093)
AND
distance(
   transform(PointFromText('POINT(-116.768347 33.911404)', 4269),32661),
   geom) < 16093

Я позволю вам пройти остальную часть урока самостоятельно.

http://unserializableone.blogspot.com/2007/02/using-postgis-to-find-points-of.html

Вот еще несколько ссылок, которые помогут вам начать.

Другие советы

Я бы просто создал таблицу ZIP_CODE_DISTANCES и предварительно выпустил расстояния между всеми 42K Zipcodes в США, которые находятся в радиусе 20-25 миль друг от друга.

create table zip_code_distances
(
from_zip_code mediumint not null,
to_zip_code mediumint not null,
distance decimal(6,2) default 0.0,
primary key (from_zip_code, to_zip_code),
key (to_zip_code)
)
engine=innodb;

Только включая Zipcodes в радиусе 20-25 миль друг от друга уменьшает количество рядов, которые вам необходимо хранить в таблице расстояний с максимум 1,7 миллиарда (42K ^ 2) - 42 тыс. До гораздо более управляемых 4 миллионов или около того.

Я загрузил файл DataFile ZipCode из Интернета, в котором содержались продоры и широты всех официальных Zipcodes в США в формате CSV:

"00601","Adjuntas","Adjuntas","Puerto Rico","PR","787","Atlantic", 18.166, -66.7236
"00602","Aguada","Aguada","Puerto Rico","PR","787","Atlantic", 18.383, -67.1866
...
"91210","Glendale","Los Angeles","California","CA","818","Pacific", 34.1419, -118.261
"91214","La Crescenta","Los Angeles","California","CA","818","Pacific", 34.2325, -118.246
"91221","Glendale","Los Angeles","California","CA","818","Pacific", 34.1653, -118.289
...

Я написал быструю и грязную программу C#, чтобы прочитать файл и вычислять расстояния между каждым ZipCode, но вывод только Zipcodes, которые попадают в радиус 25 миль:

sw = new StreamWriter(path);

foreach (ZipCode fromZip in zips){

    foreach (ZipCode toZip in zips)
    {
        if (toZip.ZipArea == fromZip.ZipArea) continue;

        double dist = ZipCode.GetDistance(fromZip, toZip);

        if (dist > 25) continue;

        string s = string.Format("{0}|{1}|{2}", fromZip.ZipArea, toZip.ZipArea, dist);
        sw.WriteLine(s);
    }
}

Результирующий выходной файл выглядит следующим образом:

from_zip_code|to_zip_code|distance
...
00601|00606|16.7042215574185
00601|00611|9.70353520976393
00601|00612|21.0815707704904
00601|00613|21.1780461311929
00601|00614|20.101431539283
...
91210|90001|11.6815708119899
91210|90002|13.3915723402714
91210|90003|12.371251171873
91210|90004|5.26634939906721
91210|90005|6.56649623829871
...

Затем я бы просто загрузил эти данные расстояния в свою таблицу ZIP_CODE_DISTANCES, используя Infile Data, а затем использовал их для ограничения пространства поиска моего приложения.

Например, если у вас есть пользователь, чей ZipCode составляет 91210, и он хочет найти людей, которые находятся в пределах радиуса в 10 миле, тогда вы можете просто сделать следующее:

select 
 p.*
from
 people p
inner join
(
 select 
  to_zip_code 
 from 
  zip_code_distances 
 where 
  from_zip_code = 91210 and distance <= 10
) search
on p.zip_code = search.to_zip_code
where
 p.gender = 'F'....

Надеюсь это поможет

Редактировать: расширенный радиус до 100 миль, что увеличило количество расстояний на почтовом коде до 32,5 миллиона строк.

Быстрая проверка производительности для ZipCode 91210 Средства выполнения 0,009 секунды.

select count(*) from zip_code_distances
count(*)
========
32589820

select 
 to_zip_code 
from 
 zip_code_distances 
where 
 from_zip_code = 91210 and distance <= 10;

0:00:00.009: Query OK

Вы можете ярлык расчет, просто предполагая коробку вместо круглого радиуса. Затем при поиске вы просто вычислите нижнюю/верхнюю границу LAT/LON для данной точки+"радиуса", и пока у вас есть индекс на столбцах LAT/LON, вы можете оттянуть все записи, которые довольно легко попадают в коробку Анкет

Вы можете разделить свое пространство на регионы примерно одинакового размера - например, приблизительно землю как бакибол или икосаэдр. Регионы могут даже немного перекрываться, если это проще (например, сделайте их круглыми). Запишите, в какой области (ы) есть каждый почтовый индекс. O (n^2) проблема как расчет всех пар почтового индекса, но для меньшего не.

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

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

Я бы использовал широту и долготу. Например, если у вас есть широта 45 и долготу 45, и вам попросили найти совпадения в течение 50 миль, то вы можете сделать это, перемещая 50/69, которые в широте и 50/69 вниз в широте (1 град широта ~ 69 миль). Выберите почтовые индексы с широты в этом диапазоне. Долиты немного разные, потому что они становятся меньше, когда вы приближаетесь к полюсам.

Но при 45 градусах 1 долготу ~ 49 миль, так что вы можете перемещать 50/49 -го оставшегося в широте и 50/49 -й прямо в широте и выбрать все почтовые индексы из широты с этой долготой. Это дает вам все почтовые индексы в квадрате с длиной сто миль. Если вы хотите быть действительно точным, вы могли бы тогда использовать ведьму Haversine Formula, которую вы упомянули, чтобы отсеять молнии в углах коробки, чтобы дать вам сферу.

Не будет использована каждая возможная пара почтовых индексов. Я бы построил Zipdistance как таблицу «кеша». Для каждого запроса рассчитайте расстояние для этой пары и сохраните его в кэше. Когда приходит запрос на пару расстояний, сначала посмотрите в кэше, затем вычислите, если он недоступен.

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

Я знаю, что этот пост слишком старый, но проводя некоторые исследования для клиента, я нашел некоторую полезную функциональность Google Maps API и настолько прост в реализации, вам просто нужно передать URL -адрес Он вычисляет расстояние даже при трафике, вы можете использовать его с любым языком:

origins = 90210
destinations = 93030
mode = driving

http://maps.googleapis.com/maps/api/distancematrix/json?origins=90210&destinations=93030&mode=driving&language=en-en&sensor=false%22

Следуя ссылке, вы можете увидеть, что она возвращает JSON. Помните, что вам нужен ключ API, чтобы использовать это на своем собственном хостинге.

источник:http://stanhub.com/find-distance-between-two-postcodes-zipcodes-time-time-in-current-traffic-using-google-maps-api/

У меня есть проблема, работающая отлично, и почти все ответили. Я думал об этом с точки зрения старого решения вместо того, чтобы просто «начинать все сначала». Бабтек получает кивок для того, чтобы указать в самых простых терминах.

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

1) Рассмотрим точку А на сфере, представленную широтой и долготой. Выясните север, юг, восток и западные края коробки в 2 раза в милях с точкой A в центре.

2) Выберите всю точку в поле из таблицы ZipCode. Это включает в себя простой пункт с двумя между операторами, ограничивающими LAT и Long.

3) Используйте формулу Haversine, чтобы определить сферическое расстояние между точкой A и каждой точкой B, возвращаемой на шаге 2.

4) Отбросьте все точки B, где расстояние a -> b> x.

5) Выберите пользователей, где ZipCode находится в оставшемся наборе точек B.

Это довольно быстро для> 100 миль. Самый длинный результат составил ~ 0,014 секунды для расчета совпадения, и тривиально для запуска оператора SELECT.

Кроме того, как примечание, необходимо было реализовать математику в нескольких функциях и позвонить в SQL. После того, как я прошел определенное расстояние, соответствующее количество Zipcodes было слишком большим, чтобы перейти к SQL и использовать в качестве оператора, поэтому мне пришлось использовать таблицу температуры и присоединиться к полученным Zipcodes с пользователем на столбце ZipCode.

Я подозреваю, что использование таблицы Zipdistance не обеспечит долгосрочную эффективность. Количество рядов становится действительно большим. Если вы рассчитываете расстояние от каждого Zip до любого другого почтового индекса (в конце концов), то полученное количество строк из 40 000 почтовых индексов будет ~ 1,6B. Ах!

С другой стороны, я заинтересован в использовании встроенного типа географии SQL, чтобы увидеть, будет ли это проще, но старые добрые типы Int/Float подают нормально для этого образца.

Итак ... окончательный список онлайн -ресурсов, которые я использовал, для вашей простой ссылки:

1) Максимальная разница, широта и долгота.

2) Формула Хаверсин.

3) Длительное, но полное обсуждение всего процесса, который я нашел из Googling Stuff в ваших ответах.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow