Performance GeoCodes Entfernung

[medium]

Hallo,

ich habe in der DB einige (viele) GeoKordinaten Einträge.
Nun will ich Einträge, die eine max. Entfernung zu einem bestimmten fix Punkt haben ausgeben.
Die Koords sind dynamisch d.h. können sich immer wieder ändern.
Zurzeit kann ich das nur bewerkstelligen, wenn ich erst alle Einträge aus der DB hole und dann in einer Schleife einzeln überprüfe, ob die Entfernung des Iterator Punktes zum fix Punkt in Ordnung ist.
Das ist mir aber aufjedenfall nicht performant genug, leider fällt mir auch nix anderes ein.

Die Formel zur Entfernungsberchnung wäre ca.:
(x und y = eine double mit 5-10 Stellen nachm Komma)
r = 6378,137
e = ARCCOS[ SIN(x1)*SIN(x2) + COS(x1)*COS(x2)*COS(y2-y1) ]
Entfernung = e * r
D.h. bei 1000 Einträge müsste ich 1000x diese Formel berechnen.


Hätte jemand ne Idee mit welcher Methodik man an die Sache ran gehen sollte?

[Christian Marquardt]

Die Berechnung erfolgt immer, wenn die Koordinaten eingefügt oder geändert werden. Somit müssten sie immer stimmen

[ngomo]

Geht es vielleicht als Fläche?

Trigonometrie ist schon etwas länger her... 6378,137 sieht mir nach dem Radius der Erde aus. Und die Formel mit den Winkelfunktionen scheint für die Entfernung zweier Punkte auf einer Kugel wichtig zu sein.

Nachdem Du schon mit x- und y-Koordinaten arbeitest, könntest Du deine Koordinaten nicht auf eine Ebene projizieren, bei dem Dein Fixpunkt die Koordinaten 0/0 hat? Dann ließe sich die Entfernung mit dem Satz des Pythagoras berechnen. Das hätte den Vorteil, dass sich die Berechung in Grundrechenarten ausdrücken lässt, welche sich direkt in SQL ausführen lassen. D.h. Du lässt Die Datenbank jedes Mal die Berechung ausführen und musst das nicht im Java-Code machen. Ein SQL-Statement, das das macht, sieht dann ungefähr so aus (aus dem Gedächtnis, nicht getestet): SELECT * FROM Punkte p HAVING MAX(p.x*p.x + p.y*p.y).

Das hat zwar den Vorteil, dass Du dann nicht die komplette Tabelle als Liste zurück bekommst und im Java-Code darüber iterieren musst. Aber möglicherweise ist die Berechnung durch die Datenbank für Deinen Anwendungsfall zu langsam. Wenn Du also auf Lesespeed angewiesen bist, dann müsstest Du -wie schon von Christian geschrieben- die Entfernung beim Insert und Update berechnen und abspeichern.

Gruß ngomo

[medium]

Das Problem ist, dass ich die Entfernung von jedem Punkt zu allen anderen Punkte brauche, sozusagen eine N:M Beziehung.
Also ich hab keinen festen Fixpunkt, an den sich alle anderen Punkte orientieren.

Aber möglicherweise ist die Berechnung durch die Datenbank für Deinen Anwendungsfall zu langsam.

Hatte gehofft, dass die DB Berechnung in diesem Fall schneller wäre. Ich denke ma die genauo Berechnung mit cos,sin usw. wird zu rechenaufwändig, aber auch mit die Berechnung mit Grundrechenarten wäre trotzdem bei einer großen Mengen sehr Aufwendig.
Überelge grad ob ich die Tabellen aufteilen könnte, wie z.B. alles 1x.xx in eine Tabelle, 2x.xx in eine andere Tabelle, so könnte ich z.B. Einträge mit 1000 Einträge in 10 Tabellen unterteilen. Und jedes mal 3 Tabellen durchgehen (da Koords in Grenzbereichen eine zulässige Entfernung zu Koord in der ein "höher" Tabelle haben könnte).
So müsste ich statt 1000 Einträge 3x100 Einträge überprüfen. Bin mir aber auch net sicher vieiel bzw. ob diese eine bessere Performance mitbringen würde.

[Christian Marquardt]

Nun will ich Einträge, die eine max. Entfernung zu einem bestimmten fix Punkt haben ausgeben.

vs.

Also ich hab keinen festen Fixpunkt, an den sich alle anderen Punkte orientieren.

Kannst du dich entscheiden?

Seit wann stellt eine Berechnung von 1000 Koordinaten für einen Server/Rechner ein Problem dar?

[medium]

ja hab auch gemerkt, dass ich die Frage etwas umständlich gestellt habe.

Es geht um GPS Daten von Personnen.
Also als Bsp.:
Im System sind 1000 Personnen registriet
Person x sendet seine Koords alle 10 Sekunden an den Server (und ist somit der "fixpunkt") und bekommt als Response alle Koords von anderen Personnen in seiner Reichweite.
D.h. Alle 10 Sekunden müssen für 1000 Personnen 1000 mögliche Koords berechnet werden.

[Christian Marquardt]

Apple? IPhone jetzt mit Java?

Wenn die Ausgangsdaten tatsächlich so sind (alle 10 Sek. 1000 Leute), dann würde ich für ordentlich Power auf den Server sorgen und mich mit Clustering beschäftigen

[medium]

Genau, im IPhone ist der Client der dem Server die Daten übermittelt.
Der Andriod tut das genauso.
Der Client wird nicht in Java geschrieben, sondern je nach für das Handy "übliche" Sprache.
Im Server läuft dann ein - in Java geschriebener - WebService der auf eine DB mithilfe von JPA zugreift.

P.s: Bin hier natürlich nicht auf de Suche nach der perfekten Lösung für mein spezielel Anforderung, sondern nach weiterführende Themen, die ich mir in diesem Zusammenhang durchlesen kann.
Wie z.B. Clustering.

[Christian Marquardt]

War ja oben mit IPhone mehr als Gag gedacht, aber dass das nun grausame Realität wird. Wer braucht auf dem IPhone alle 10 Sek. die Daten von 1000 anderen Leuten? Völlig unsinnig. Was nützt da eine Berechnung per Luftlinie?

Gegen den Willen der Anwender GEO-Daten aufzeichnen. Nunja, demnächst werden die GEO-Daten direkt mit dem Einkaufsdaten abgeglichen und jeder kann dann im Internet sehen, wann er XXXX wo war, was eingekauft hat, welche Bilder/Videos von ihm gemacht wurden. Wer nicht freiwillig bei Gesichtsbuch ist, ist auotmatisch verdächtig.

Schöne neue Welt. Irgendwie wird alles, was dem Kommerz in die Hände fällt zum negativen gekehrt.

Also ich unterstütze das nicht

[medium]

Gegen den Willen der Anwender GEO-Daten aufzeichnen

Naja soll ja nicht gegen den Willen der Anwender sein. Sondern ein Spiel in dem Leute die das App einschalte mit anderen interaktiv Spielen können. Und wenn Sie das App auschalten ist das Spiel vorbei
Sehe da eigentl. nichts verwerfliches.

Und das gleichzeitig 1000 Leute "mein" Spiel anmachen werden, ist mehr als unwahrscheinlich, aber wenn ich was Progge, dann sollte wenigstens theoretisch auch auf Performance achten

[Christian Marquardt]

Vielleicht solltest du mit realistischen Zahlen anfangen....

Sonst würde ich mit 7 Mrd Menschen alle 10 Sek proggen....Dann bist du vorbereitet

[medium]

Es geht mir doch um den Lernfaktor...

Sonst würde ich mit 7 Mrd Menschen alle 10 Sek proggen....Dann bist du vorbereitet

In einem Unternehmen werde ich bestimmt nie mit so einer Anforderung konfrontiert, aber dass mal ein Anwendungsfall eine Berechnung für 1000 Anfragen pro 10 sek. hat, ist mehr als realisitsch...

[Christian Marquardt]

Dann wird auch eine entsprechende Infrastruktur vorhanden sein bzw. aufgebaut werden müssen, die du jetzt nicht hast und somit auch nicht simulieren kannst