MongoDB i odległość pomiędzy dwoma punktami

Potrzebna pomoc
1

Łamigłówka z MongoDB, MongoMappera (i rubiego):

Mam punkty reprezentowane przez model Place. Punkty mają współrzędne geograficzne w postaci liczb rzeczywistych lat i lng. Mając zadane współrzędne znaleść N najbliższych miejsc.


      lat, lng = [53.1, 21.3] # zadane współrzędne
      conditions = { :page => 1, :per_page => 20 }
      map = "function() { emit(this._id, {lat: this.lat, lng: this.lng}); }"
      reduce = <<BEGIN
function(key, values) {
  distance = 0;
  values.forEach(function(doc) {
   distance = (doc.lat - #{lat})*(doc.lat - #{lat}) + (doc.lng - #{lng})*(doc.lng - #{lng});
  });
  return distance;
};
BEGIN
    results = Place.collection.map_reduce(map, reduce).find({}, {:sort => "value ASC", :limit => conditions[:per_page]})
    conditions[:_id] = { "$in" => results.collect { |r| r["_id"]} }
    end
 
    Place.paginate(conditions)

Działa. Ktoś ma pomysł jak pozbyć się map-reduce?..

2

Jezusmaria, Hubert.
Longitude i latitude to kąty (tzn. trochę upraszczam, ale mniejsza), a nie współrzędne kartezjańskie na płaszczyźnie. Nie wolno używać pitagorejskiej formuły do liczenia odległości!
http://tomash.wrug.eu/2009/10/18/rails-tricks-part-3a-distance-based-search.html – tutaj jest mały wstęp i linki do wzoru Haversine’a.
Obiecałem sobie jeszcze w tym roku kalendarzowym dokończyć przynajmniej podnotkę o PostgreSQL. :wink:

To tak na wstępie, bo tak jak rozmawialiśmy na jabberze – o ile w MongoDB “where” można podać kawałek javascriptu do wykonania, o tyle w order już nie (mongowa jira ma na to otwarty ticket nawet, ale nikt go nie ruszał od miesięcy). Więc chyba pozostaje map-reduce.

3

Te wzorki z całą pewnością zaimplementowane są w gemie geokit (lub geokit-rails) - może będzie łatwiej wydłubać kawałek kodu Rubiego.

4

Jezusmaria, Hubert.
Longitude i latitude to kąty (tzn. trochę upraszczam, ale mniejsza), a nie współrzędne kartezjańskie na płaszczyźnie. Nie wolno używać pitagorejskiej formuły do liczenia odległości!
http://tomash.wrug.eu/2009/10/18/rails-tricks-part-3a-distance-based-search.html – tutaj jest mały wstęp i linki do wzoru Haversine’a.
Obiecałem sobie jeszcze w tym roku kalendarzowym dokończyć przynajmniej podnotkę o PostgreSQL. :wink:

To tak na wstępie, bo tak jak rozmawialiśmy na jabberze – o ile w MongoDB “where” można podać kawałek javascriptu do wykonania, o tyle w order już nie (mongowa jira ma na to otwarty ticket nawet, ale nikt go nie ruszał od miesięcy). Więc chyba pozostaje map-reduce.[/quote]
A to święte oburzenie, bo sądzisz, że to co napisałeś jest super poprawne, a to co napisał Hubert jest z gruntu złe?
Tak reasumując: obaj błądzicie i obaj macie rację.

5

Wzorki tak, ale jeszcze musisz mieć znajomość w jaki sposób policzono wartości współrzędnych tych punktów, bez tego dostajesz jakby jakieś liczby. To zupełnie jakbyś policzył odległość i wyszłoby, że 42… tylko nie znasz jednostki.
No i to co napisał Hubert nie jest wcale złe, zależy do czego.

6

W tym przypadku, żeby użyć ich do sortowania po odległości? Można. Choć dużo lepsza (bo tańsza obliczeniowo) będzie miara taksówkowa.

7

Chyba raczej jest tak, że aby użyć czegokolwiek do sortowania… to powinno się mieć to coś obliczone dobrze, ale ja tam się nie znam, w końcu posortować można wszystko.

8

Nie, nie trzeba. Wystarczy, że masz to “ponumerowane” we właściwej kolejności. Na przykład żeby posortować prostokąty według ich pola powierzchni nie musisz go obliczać. Wystarczy, że wiesz, że im dłuższa suma boków, tym powierzchnia większa.

9

[quote=SimonG]A to święte oburzenie, bo sądzisz, że to co napisałeś jest super poprawne, a to co napisał Hubert jest z gruntu złe?
Tak reasumując: obaj błądzicie i obaj macie rację.[/quote]
Napisz mi gdzie błądzę albo przeproś i przestań siać FUD jeśli nie wiesz.

Jezusmaria :confused:

Nie. Są miejsca na ziemi, gdzie bardzo duża różnica w długości geograficznej przekłada się na bardzo małą różnicę w realnych odległościach na płaszczyźnie (metrach). Like, bieguny.

Srsly, za takie teksty moja pani od matematyki z podstawówki by Cię opieprzyła, a pani w liceum kazała powtarzać rok.

10

http://skepticalteacher.files.wordpress.com/2009/08/facepalm.jpg

Srsly, za takie teksty moja pani od matematyki z podstawówki by Cię opieprzyła, a pani w liceum kazała powtarzać rok.[/quote]
:smiley:

11

Jezusmaria, Hubert.
Longitude i latitude to kąty (tzn. trochę upraszczam, ale mniejsza), a nie współrzędne kartezjańskie na płaszczyźnie. Nie wolno używać pitagorejskiej formuły do liczenia odległości![/quote]
Ale dlaczego nie wolno?! Odległości mam małe (w obrębie jednego miasta), nie obchodzą mnie jednostki (tylko posortowanie). Geokit też można przestawić w tryb :flat dla małych odległości jest to nawet wskazane bo redukuje obliczenia. Zamiast:

          begin
            units_sphere_multiplier(units) * 
                Math.acos( Math.sin(deg2rad(from.lat)) * Math.sin(deg2rad(to.lat)) + 
                Math.cos(deg2rad(from.lat)) * Math.cos(deg2rad(to.lat)) * 
                Math.cos(deg2rad(to.lng) - deg2rad(from.lng)))
          rescue Errno::EDOM
            0.0
          end

masz:

          Math.sqrt((units_per_latitude_degree(units)*(from.lat-to.lat))**2 + 
              (units_per_longitude_degree(from.lat, units)*(from.lng-to.lng))**2)
12

Ok, s/prostokąty/kwadraty/, nie pisać przed poranną kawą. :wink:

W każdym razie - w normalnych warunkach przy obliczaniu odległości do znalezienia kilku najbliższych punktów nie ma znaczenia, czy uwzględnisz krzywiznę ziemi, czy ją olejesz. Owszem, można się onanizować użyciem bardziej skomplikowanych wzorów, tylko po co? Ale kto wie - może kolega Hubert pisze portal społecznościowu dla polarników, fok i białych niedźwiedzi.

13

Ale to (tryb “flat”) naprawdę nie działa.
Już na naszej długości geograficznej (tj. na wysokości Polski-Niemiec – 52 st. N) jeden stopień szerokości geograficznej to zaledwie 68km – podczas kiedy na równiku 111km. To znaczy masz prawie dwukrotną różnicę wag w przypadku stosowania zaproponowanych metryk (swoją drogą określonych dla wymiarów odległości, a nie bezwymiarowych kątów, więc z punktu widzenia analizy jednostkowej zupełnie bez sensu) – a te metryki przecież traktują wymiary równoważnie.
Pobaw się tym: http://www.movable-type.co.uk/scripts/latlong.html (wbij 52N, a potem 0N).

EDIT: Hubert, jeśli w okolicach jednego miasta, to jasne – takie uproszczenie jest dopuszczalne.
U nas w Anounzie mamy odległości do 100km, gdzie tego typu akcja by nas zastrzeliła.

14

[quote=Tomash]Ale to (tryb “flat”) naprawdę nie działa.
(…)
U nas w Anounzie mamy odległości do 100km, gdzie tego typu akcja by nas zastrzeliła.[/quote]
Nie wiem czym jest Anounz, jedynce co wygooglałem to jakiś portal chyba ogłoszenowy w zupełnie dla mnie niezrozumiałym języku bez wersji angielskiej, więc być może to co napiszę, to w odniesieniu do tego serwisu brednie. Ale jak usiądziesz i na spokojnie przemyślisz wszystkie uwarunkowania, to dojdziesz do wniosku, że typowemu userówi nic po odległości punkt-punkt wyznaczonej w linii prostej z idealną precyzją. Dla typowego człowieka odległość punkt-punkt ma sens tylko w bardzo bliskim sąsiedztwie. Im skala większa, tym dokładność takiego pomiaru ma mniejsze znaczenie. W końcu co mnie obchodzi, czy z Pcima do San Fracisco jest geograficznie bliżej/dalej niż do Los Angeles? I tak się tam nie przemieszczę w lini prostej. Więc kategoryczne opinie “tak nie można robić” są po prostu bezsensowne.

I tak naprawdę nic to nie wniosło do tematu “jak to zrobić dobrze za pomocą MongoDB”…

15

Widzę małą zmianę stanowiska z “można użyć metryki taksówkarskiej” na “nie bądźmy kategoryczni”. Spoko, wezmę to za zawoalowane przyznanie się do błędu (skoro nie umiesz tego powiedzieć wprost).

I owszem, przy 50 czy 100km od “mojej” lokacji ma to znaczenie, bo wolałbym ogłoszenia naprawdę w zasięgu tych 50 czy 100km, a nie w odległości dwa razy większej.

PS. Underley, z całym szacunkiem, ale weź odśwież matmę zanim będziemy mieli kolejnego takiego flejma :wink:

16

OK, dobra, Tomash mnie przekonał, a może nie tyle przekonał co zmieniłem obliczenia żeby przestał na mnie tu krzyczeć ;). W sumie to będzie pomocne nawet jak ktoś postawi kropkę na biegunie czy cuś. Ale rzeczywiście tematem mojego zapytania nie było “jak to obliczyć” tylko jak zaprzęc do tego MongoDB / MongoMapper. I chyba tu nikt nie ma lepszej sugestii od mojego rozwiązania? :wink:

17

Jakbyśmy mieli lepszy pomysł, to byśmy o nim dyskutowali zamiast robić flejma o metrykach na sferze :wink:

Trzeba molestować kolesi od Mongo, bo sortowanie według customowej funkcji jest (IMHO) dość ważną funkcjonalnością.

18

Inny szalony hack (poptencjalnie wydajniejszy niż map-reduce), który przyszedł mi do głowy (ale nie działa).

Można by zrobić w zapytaniu klauzulę:

"$where" => "this.distance = calculate_distance_here()", "sort" => "this.distance"

I co jest najśmieszniejsze, to by działało. Ale w mongo >= 1.1 where już nie może modyfikować danych (nawet bez save) i to nie zadziała.

19

[quote=hubertlepicki]Inny szalony hack (poptencjalnie wydajniejszy niż map-reduce), który przyszedł mi do głowy (ale nie działa).

Można by zrobić w zapytaniu klauzulę:

"$where" => "this.distance = calculate_distance_here()", "sort" => "this.distance"

I co jest najśmieszniejsze, to by działało. Ale w mongo >= 1.1 where już nie może modyfikować danych (nawet bez save) i to nie zadziała.[/quote]
Ja wiem, że Tomash mnie zaraz za takie stwierdzenia powiesi, ale… ja bym użył sphinxa :wink:

Sphinx ma niesamowicie szybkie indeksowanie i wyciąganie rekordów włącznie z sortowaniem ich po odległości od podanego punktu.

Oczywiście nie trzeba od razu przebudowywać połowy aplikacji, używając thinking sphinxa wystarczy zaindeksować pola latitute i longitude i później sphinxa używać tylko do geolokalizacji. ThinkingSphinx my metodę search_for_ids, która zwraca id znalezionych rekordów, więc później to już można sobie wpiąć w jakiekolwiek inne zapytania (a samo indeksowanie rekordów z 2 polami będzie śmigało jak rączy jeleń).

Kłopot może być tylko z podpięciem sphinxa pod mongomappera, ale ponoć już ktoś to zrobił, więc można spróbować.

20

A interpretuj sobie jak Ci jest wygodnie. Ja zdania nie zmieniam - do znalezienie kilku najbliższych punktów i posortowania ich w kolejności od najdalszego do najbliższego w zupełności wystarczy metryka taksówkowa, nie trzeba bawić się w obliczanie odległości z uwzględnieiem “kulistości” Ziemi. Szczególnie jeśli punkty, które sortujesz znajdują się w obrębie jednego miasta/powiatu/województwa. Ba, nawet w obrębie kraju wielkości Polski wyniki nie będą na tyle różne od rzeczywistości, żeby robić sobie z tego problem.