Mit kd-tree Nearest Neighbour berechnen?



  • Ich habe eine Tabelle mit Städten (Lat,Lng,Name). Kann ich die einfach in einen kd-tree packen und dann zu einem gegebenen Punkt den nächstliegenden abfragen, oder muss ich erst das Koordinatensystem umrechnen?

    Gibt es dafür eine spezielle DB (MongoDB z.B.) oder einen besseren Index?



  • du musst die punkte erst in ein kartesisches koordinatensystem wandeln.



  • Wichtig istd abei eine längenerhaltende Transformation vorzunehmen, sonst stimmen die Ergebnisse nicht mehr. (Abstand auf der Kugel und Abstand in der Ebene sind im allgemeinen ziemlich verschieden)



  • Jester schrieb:

    Wichtig istd abei eine längenerhaltende Transformation vorzunehmen, sonst stimmen die Ergebnisse nicht mehr. (Abstand auf der Kugel und Abstand in der Ebene sind im allgemeinen ziemlich verschieden)

    Ich dachte, das ist ein ellipsoid? Hätte jetzt einfach in UTM gewandelt, aber damit komme ich nicht zurecht 😞

    Soll ich es vllt mal mit dem Gauss–Krüger versuchen? Habt ihr einen Link?



  • kleinr schrieb:

    Jester schrieb:

    Wichtig istd abei eine längenerhaltende Transformation vorzunehmen, sonst stimmen die Ergebnisse nicht mehr. (Abstand auf der Kugel und Abstand in der Ebene sind im allgemeinen ziemlich verschieden)

    Ich dachte, das ist ein ellipsoid?

    das macht es nicht einfacher -- im Gegenteil. Die Frage ist, stört Dich die Ungenauigkeit, die Du durch eine Standardprojektion erhältst? Für einen Großteil der Welt hält sich die Verzerrung ja in Grenzen, sodass die Ergebnisse nicht grob falsch werden. Wenn das nicht reicht musst Du eventuell die komplette Zerlegung auf der Kugel/dem Ellipsoid machen, d.h., eine für diesen Fall geeignete Ersatzdatenstruktur für den kd-tree finden.



  • Dachte, Du erzeugst normale x/y/z-Koordinaten und nimmst dann ganz normal den euklidischen Abstand, also kd-Baum. Wohl nicht Längenerhaltend im Vergleich zum echten Weg auf der Kugeloberfläche, aber wohl ich denke, der nächste Gerade-Nachbar ist auch der nächste Großkreis-Nachbar.

    Schummeln ist aber auch ganz ok, wenns genügend Städte gibt, ist die betrachtete Gegend ja recht flach. Wo es abkackt, an den Polen, wird nicht so viel los sein. Ärgerlich ist der wrap-around an der Datumsgrenze. Der bringt mich gerade vom Schummeln wieder ab.



  • volkard schrieb:

    Ärgerlich ist der wrap-around an der Datumsgrenze. Der bringt mich gerade vom Schummeln wieder ab.

    Wenn du nicht nur 2d sondern 3d verwendest, gibt es kein wrap-around, oder? Auch an den Polen gibt es dann kein Problem; es werden nur längere Distanzen ggf. Unterschätzt, da gradlinig gerechnet.

    Und im zweifel kann man natürlich immer noch seine Kugel/Ellipsoid mit Großkreisen kleinschneiden á la kd-tree (wobei für nearest neighbor-anfragen zumindest aus theoretischer sicht voronoi-diagramme deutlich besser geeignet sind).



  • der raum muss natuerlich 3d sein, nicht 2d, sonst koennte man bei Lat,Lng bleiben.

    der ganze trick besteht darin die distanzberechnung zwischen den staedten weiterhin richtig mit Lat,Lng auf planeten oberflaechen basierend durchzufuehren. der kd-tree basiert natuerlich auf auf kartesischen distanzen, diese sind aber >= der planetarisch bassierten, es wird also nie 'ueberschaetzt' in relation zu den echten planetaren distanzen sondern immer nur 'unterschaetzt'. deswegen funktioniert das ganze nearest neighbour problemlos.



  • rapso schrieb:

    der kd-tree basiert natuerlich auf auf kartesischen distanzen, diese sind aber >= der planetarisch bassierten, es wird also nie 'ueberschaetzt' in relation zu den echten planetaren distanzen sondern immer nur 'unterschaetzt'. deswegen funktioniert das ganze nearest neighbour problemlos.

    Verstehe, Du suchst also 1) den nächsten euklidischen Punkt, rechnest dessen echte Distanz aus und suchst dann 2) alle Zellen ab, die potenziell Punkte mit kleinerer planetarer Distanz ab -- das können dann aber schon einige sein.



  • Aber die euklidische Distanz ist doch immer kleiner als die planetare.

    die funktion, die die planetare auf die euklidische abbildet, sollte streng monoton sein. dann würde der kleinste euklidische aus dem kd-baum auch dem kleinsten planetaren entsprechen. ich sehe keinen bedarf einer nachsuche.



  • Jester schrieb:

    Verstehe, Du suchst also 1) den nächsten euklidischen Punkt, rechnest dessen echte Distanz aus und suchst dann 2) alle Zellen ab, die potenziell Punkte mit kleinerer planetarer Distanz ab -- das können dann aber schon einige sein.

    nein, du aenderst am nearest neighbour search mit kd-tree nichts, du rechnest einfach nur mit groesseren distanzen als es die euklidischen distanzen waeren.

    esseiden ich uebersehe was.



  • rapso schrieb:

    Jester schrieb:

    Verstehe, Du suchst also 1) den nächsten euklidischen Punkt, rechnest dessen echte Distanz aus und suchst dann 2) alle Zellen ab, die potenziell Punkte mit kleinerer planetarer Distanz ab -- das können dann aber schon einige sein.

    nein, du aenderst am nearest neighbour search mit kd-tree nichts, du rechnest einfach nur mit groesseren distanzen als es die euklidischen distanzen waeren.

    esseiden ich uebersehe was.

    Im wesentlichen funktioniert die nearest-neighbor search im kd-tree ja genau so. Aber warum soll das dann noch korrekt sein und gleichzeitig wenige Zellen absuchen? Nimm mal ein Ellipsoid, das total flachgedrückt ist, sodass der Nord- und Südpol in 3D sehr nah beieinander liegen. Nimm weiter an, dass die Städte alle in Äquatornähe liegen -- also ziemlich weit weg und außerdem eine Stadt auf dem Nordpol steht. Wenn ich jetzt vom Südpol aus die nächste Stadt suche, dann ist euklidisch mit großen Abstand der Nordpol am nächsten. Für die korrekte Antwort muss ich aber bis zum Äquator suchen, und damit vermutlich mehr oder weniger alles anschauen was auf der Südhalbkugel liegt -- oder eben riskieren, dass ich eine falsche Antwort bekomme.

    Klar, das Beispiel funktioniert so auf der Kugel erstmal nicht. Daraus folgt ja aber nicht, dass das Verfahren auf der Kugel sofort gut ist. Irgendwie fehlt mir der entscheidende Unterschied, warum es bei dem einen funktionieren soll und beim anderen nicht. Zumindest bräuchte man also noch irgendein Argument, das für die Kugel greift aber nicht für das Ellipsoid.

    Disclaimer: Mir ist klar, dass das eine eher theoretische Betrachtung ist (das ist nunmal mein Beruf). In der Praxis mit halbwegs gutartig verteilten Städten (und entsprechend dicht bevölkerten Regionen) wird das ziemlich sicher in 99,9% der Fälle richtig liegen.



  • Jester schrieb:

    Wenn ich jetzt vom Südpol aus die nächste Stadt suche, dann ist euklidisch mit großen Abstand der Nordpol am nächsten.

    du suchst nicht den euklidschen abstand, deine abstandsfunktion kann nur planetare distanzen.

    gehen wir mal den algorithmus durch wie er in wikipedia steht:

    http://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search schrieb:

    1.Starting with the root node, the algorithm moves down the tree recursively, in the same way that it would if the search point were being inserted (i.e. it goes left or right depending on whether the point is less than or greater than the current node in the split dimension).
    2.Once the algorithm reaches a leaf node, it saves that node point as the "current best"

    wir gehen also bis zum leaf vom nordpol.

    3. The algorithm unwinds the recursion of the tree, performing the following steps at each node:
    - 1. If the current node is closer than the current best, then it becomes the current best.

    also

    if(PlanetaryDistance(Current,Me)<PlanetaryDistance(CurrentBest,Me))
     CurrentBest=Current;
    

    und du hast eine andere stadt am aequator.
    ..

    Irgendwie fehlt mir der entscheidende Unterschied, warum es bei dem einen funktionieren soll und beim anderen nicht. Zumindest bräuchte man also noch irgendein Argument, das für die Kugel greift aber nicht für das Ellipsoid.

    es funktioniert bei beiden.

    ich versuche mal einen beweis.
    1. jede node im kd-tree garantiert dir, dass jeder punkt im nachbarsektor mindestens die gleiche euklidische distanz hat zu deinem punkt wie die euklidische distanz zur node (zur splitting plane in 3d) ist.
    2. hast du eine distanzfunktion die zwischen zwei punkten im raum eine distanz zurueckliefert die groessergleich der euklidische distanz ist, dann wird diese distanz groessergleich sein zur summe der euklidische distanzen der beiden punkte zur grenz-node sein die diese beiden punkte in zwei sektoren unterteilt.

    das impliziert umgekehrt, dass wenn du mit deiner distanzfunktion 'nichtmal' die grenz-node erreichst, kein punkt im nachbarsektor naeher sein wird.

    besser kann ich es glaube ich nicht.



  • volkard schrieb:

    Aber die euklidische Distanz ist doch immer kleiner als die planetare.

    die funktion, die die planetare auf die euklidische abbildet, sollte streng monoton sein. dann würde der kleinste euklidische aus dem kd-baum auch dem kleinsten planetaren entsprechen. ich sehe keinen bedarf einer nachsuche.

    habs gerade durchgerechnet, fuer die erde scheint das zu stimmen wenn man mit einem pol-zu-pol radius von 6353km und am aequator radius von 6384km arbeitet. (fuer Jesters planeten nicht 🙂 ).



  • Jester schrieb:

    Klar, das Beispiel funktioniert so auf der Kugel erstmal nicht. Daraus folgt ja aber nicht, dass das Verfahren auf der Kugel sofort gut ist. Irgendwie fehlt mir der entscheidende Unterschied, warum es bei dem einen funktionieren soll und beim anderen nicht. Zumindest bräuchte man also noch irgendein Argument, das für die Kugel greift aber nicht für das Ellipsoid.

    Die Symmetrie.
    Wenn ich zwei Punkte mit Euklidischem Abstand s habe, dann haben die einen entsprechenden planetaren Abstand b=f(s). Die ist lageunabhängig, hat keine Polproblematik.
    Den planetaren Abstand könnte man sogar ausrechnen. Bildchen/Formel: http://de.wikipedia.org/wiki/Kreissegment
    f(s)=2*r*asin(s/(2r))
    Das würde ich von WolframAlpha mal schauen lassen, ob's im Bereich 0 < s < 2
    r monoton verläuft. Heute keine Bandbreite für sowas.
    Und wenns monoton ist, wobon ich sicher ausgehen, dann gilt: Kleinere euklidische Abstände machen kleinere planetare Abstände. Mithin ist mein nächster euklidischer Nachbar auch mein nächster planetarer Nachbar.

    edit: Jo, musste nur ein Netzwerkkabel ziehen, um die Switching-Loop aufzuöäsen. 🙄

    Ableitung:
    http://www.wolframalpha.com/share/clip?f=d41d8cd98f00b204e9800998ecf8427evtjopukoqh
    Und für den erlaubten s-Bereich ist der untere Buch zwischen 0 und 1, also auch der Term in der Wurzel also auch die Wurzel und deren Kehrwert ist positiv. Positive Ableitung=>Strenge Monotonie.



  • rapso schrieb:

    volkard schrieb:

    Aber die euklidische Distanz ist doch immer kleiner als die planetare.

    die funktion, die die planetare auf die euklidische abbildet, sollte streng monoton sein. dann würde der kleinste euklidische aus dem kd-baum auch dem kleinsten planetaren entsprechen. ich sehe keinen bedarf einer nachsuche.

    habs gerade durchgerechnet, fuer die erde scheint das zu stimmen wenn man mit einem pol-zu-pol radius von 6353km und am aequator radius von 6384km arbeitet. (fuer Jesters planeten nicht 🙂 ).

    Da siehst Du mal in was für unwirtlichen Umgebungen wir Theoretiker leben müssen (http://xkcd.com/669/). 😃

    Ich hab grad wenig Zeit und weiß noch nicht wann ich dazu komme mir das alles im Detail durchzulesen. Auf jeden Fall danke für eure Beiträge.


Log in to reply