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

Question

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

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

USER TABLE UserId UserName ZipCode

ZIPCODE TABLE ZipCode Latitude Longitude

С присоединением USER и ZIPCODEUSER.ZipCode = ZIPCODE.ZipCode.

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

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

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

Вопрос, по крайней мере для нас, 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 будет много строк.Это не совсем неработоспособно, но оно действительно большое.Кроме того, требуется полная предварительная работа со всем набором данных, что также не является неуправляемым, но не обязательно желательным.

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

Answer 1

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

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

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

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

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

Конечно, поскольку это довольно распространенная вещь, кто-то другой уже сделал за вас тяжелую часть.Поскольку вы не указали, какую базу данных вы используете, в качестве примера будет использовано расширение PostgreSQL PostGIS .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

Вот некоторые другие ссылки, с которых можно начать.

• http://www.bostongis.com/PrinterFriendly.aspx?content_name=postgis_tut02
• http://www.manning.com/obe/PostGIS_MEAPCH01.pdf
• http://postgis.refractions.net/docs/ch04.html

Answer 2

Я бы просто создал таблицу zip_code_distances и предварительно вычислил расстояния между всеми почтовыми индексами 42K в США, которые находятся в радиусе 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;

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

Я загрузил файл данных почтового индекса из Интернета, в котором содержались значения долготы и широты всех официальных почтовых индексов США в формате 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 # для чтения файла и вычисления расстояний между каждым почтовым индексом, но только для выходных почтовых индексов, которые попадают в радиус 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, используя файл загрузки данных, а затем использовал его для ограничения пространства поиска моего приложения.

Например, если у вас есть пользователь с почтовым индексом 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'....

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

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

быстрая проверка производительности для почтового индекса 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

Answer 3

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

Answer 4

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

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

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

Answer 5

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

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

Answer 6

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

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, чтобы использовать его на своем собственном хостинге.

source: http://stanhub.com/find-distance-between-two-postcodes-zipcodes-driving-time-in-current-traffic-using-google-maps-api/

Answer 7

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

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

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

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

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

4) Откажитесь от всех точек B, где расстояние A -> B> X.

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

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

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

Я подозреваю, что использование таблицы ZipDistance не обеспечит долгосрочного прироста производительности.Количество строк просто становится действительно большим.Если вы вычислите расстояние от каждого почтового индекса до любого другого почтового индекса (в конечном итоге), то результирующее число строк из 40000 почтовых индексов будет ~ 1,6B.Ух ты!

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

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

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

2) Формула Haversine.

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

Answer 8

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

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