Проследяване на GPS точки и намиране на най-близките им съседи?

Имам списък с 1 милион (бавно) движещи се точки по земното кълбо (съхранени като географска ширина и дължина). От време на време всяка точка изисква списък от 100 най-близки други точки (с конфигурируем максимален диапазон, ако това помага).

За съжаление, SELECT * SORT BY compute_geodetic_distance() LIMIT 100 е твърде бавен, за да се изпълнява от всяка точка отново и отново. Така че моят въпрос: как да се справя с това ефективно? Има ли по-добри алгоритми/структури от данни/... известни за това? Или това е единственият начин и трябва да разгледам разпределението на натоварването на сървъра?

(Забележка: това е за приложение за Android и точките са потребители, така че в случай, че пропускам специфично за android решение, не се колебайте да го кажете!)


mysql android algorithm gps nearest-neighbor
person user1111929    schedule 12.06.2013    source източник
comment
@eggyal, това не е проблем с 2D индексиране, за да се намалят един милион до стотици операции.   -  person AlexWien    schedule 12.06.2013

Отговори (4)


arrow_upward
1
arrow_downward

За вашата задача са измислени геопространствени бази данни.
Има Oracle Spatial (скъпо) и PostGres (безплатно).
Тези бази данни съхраняват милионите ви точки в географски индекс, четворно дърво (Oracle). Подобно запитване не изисква почти никакво време.

Някои хора, като мен, предпочитат да напуснат базата данни и сами да изградят quadtree.

Операциите търсене и вмъкване са лесни за изпълнение. Актуализирането/изтриването може да бъде по-сложно. (Най-евтиното, свързано с усилията за внедряване, е изграждането на ново квадратно дърво всяка минута)

С помощта на квадродърво можете да изпълнявате стотици или хиляди такива най-близки 100 точки в рамките на секунда.

person AlexWien    schedule 12.06.2013
comment
@eggyal, защото е сортиране. намаляването от един милион на няколко трябва да бъде направено преди това, например в клауза where с помощта на пространствено разширение. - person AlexWien; 12.06.2013
comment
Виждам, че коментарът, в който се споменава, че MySQL също има пространствени разширения, е изчезнал. Така че публикувам това отново, тъй като го намирам за ценна информация. - person user1111929; 13.06.2013
comment
Бихте ли ми обяснили как мога да направя хиляди такива най-близки 100 точки в рамките на секунда? За дадена точка curr сега избирам най-близките 100 точки по SELECT user_id, GLENGTH(LINESTRINGFROMWKB(LINESTRING(ASBINARY(curr),ASBINARY(pt)))) AS distance ORDER BY distance LIMIT 100, но това всъщност е доста бавно. Може би нещата биха били по-бързи, ако мога да добавя клауза WHERE, но не виждам начин да определя предварително дали най-близките 100 точки ще бъдат в обхват от 5 км или от 5000 км. - person user1111929; 15.06.2013
comment
Въпросът е наистина ли искате 100-те най-близки точки, дори ако само 50 точки са в рамките на 100 км? (където разстоянието ‹ x). Ако не сте намерили достатъчно, можете да дублирате разстоянието x в клаузата where. За точния ви въпрос би било по-добре да заредите целите координати в основната памет и да използвате свое собствено четворно дърво. В такъв случай знаете кога да спрете. - person AlexWien; 15.06.2013
comment
Опасявам се, че радиус от 100 километра често ще дава само 1-2 точки в селските райони. А радиусът от 1000 км потенциално може да включва половината потребителска база. Относно изграждането на собствено дърво в паметта: може ли това да се направи по някакъв начин в PHP? И ако не, как мога да го накарам да взаимодейства с останалата част от моето приложение, което е написано на PHP/MySQL от страната на сървъра? - person user1111929; 15.06.2013
comment
Като алтернатива, има ли начин да направите двоично търсене, за да намерите правилния радиус? Започнете с COUNT() за 100 км и в зависимост от резултата отидете на 50 или 200 км? След това пребройте отново и стигнете до 25 или 75, или 150 или 400? Или сложността на COUNT() не е по-добра от тази на SELECT в тези четворни дървета? (т.е. проблем ли е да се направи COUNT(), който връща 500 000?) - person user1111929; 15.06.2013
comment
Тук в So е добър отговор, който е полезен за много приложения. Номерът е да изчислите от даден радиус maxLatitude, minLatitude, maxLongitude и minLongitude и да ги използвате в клаузата where. Това ще намали търсенето ви. Тогава с това можете да направите двоично търсене, както казахте. - person AlexWien; 15.06.2013

arrow_upward
0
arrow_downward

Архитектурно бих уредил всяка „точка“ да се обажда до сървър с тяхното местоположение, когато се промени повече от определена сума. На сървъра можете да извършите тежката работа по изчисляване на разстоянието между точката, която се е преместила, и всяка от другите точки и за всяка от другите точки да актуализирате техния списък от 100 най-близки точки, ако е необходимо. След това можете да натискате промените в най-близкия списък със 100 на дадена точка, когато се случват (тривиално, ако използвате App Engine, Android push се поддържа).

Това намалява необходимото количество работа до абсолютен минимум:

  • Отчитайте промяна на местоположението само когато дадена точка се премести достатъчно далеч
  • Преизчислете разстоянията само при получаване на доклад
  • Не изграждайте отново най-близкия списък от 100 за точка всеки път, съставете списъка веднъж, след което преценете дали точка, която се е преместила, ще бъде добавена или премахната от списъка на всяка друга точка.
  • Уведомявайте точка само за промени в нейния списък с топ 100, за да запазите честотната лента.

Има алгоритми, които можете да използвате, за да направите това супер-ефективно, а проблемът също има усещане за разклонение/съединяване, което ви позволява да хвърлите конски сили към проблема.

person Phil Haigh    schedule 12.06.2013

arrow_upward
0
arrow_downward

Трябва да разделите земята на зони и след това да използвате алгоритъм за вътрешни точки, за да разберете в кои зони се намира телефонът. Всяко възможно подмножество от зони ще определи по уникален начин 100-те най-близки възли до справедливо приближение. Можете да получите точен набор от 100 възела, като проверите разстоянието един по един спрямо кандидат възлите, които (отново) се определят от подмножеството от зони.

person Tyler Durden    schedule 12.06.2013

arrow_upward
0
arrow_downward

Вместо r-дърво или quadtree, т.е. пространствен индекс, можете също да използвате quadkey и чудовищна крива. Тази крива намалява размерите и напълно запълва пространството. Можете да изтеглите кривата на Хилберт от моя php клас от phpclasses.org. Можете да използвате проста колона varchar за quadkey и да търсите нивата отляво надясно. Добро обяснение е от уебсайта на Microsoft Bing maps quadkey.

person Gigamegs    schedule 26.08.2013