Performance GPS Entfernung berechnen

[ayibogan]

HI,
es geht um GPS Daten von verschiedenen Clients (z.B. Handyapps).
Im System sind z.B. 1000 Personnen registriert (können auch mehr sein).
Person x sendet seine Koords alle 10 Sekunden an den Server und bekommt als Response alle Koords von anderen Personnen in einer bestimmten Reichweite.
D.h. Alle 10 Sekunden müssen für 1000 Personnen serverseitig 1000 mögliche Koords berechnet werden.

Die Formel für die Berechnung ist je nach Genauigkeitsgrad von relativ einfach bis sehr komplex.
Folgende Idee hätte ich zwar:
Erst werden alle Einträge aus der DB geholt und dann in einer Schleife für jeden einzelnen Client geprüft, ob die Entfernung des Iterator Punktes zum Client passt.

Um die potentiellen Clients etwas einzuschrenken:
Die Tabellen aufteilen , wie z.B. alle 1x.xx Koords in eine Tabelle, 2x.xx in eine andere Tabelle usw., so könnte ich 1000 Einträge in 10 Tabellen unterteilen. Und jedes mal 3 Tabellen durchgehen (da Koords in Grenzbereichen eine zulässige Entfernung zu Koords in der eins "höher oder unteren" Tabelle haben könnten).
So müsste ich statt 1000 Einträge 3x100 Einträge überprüfen. Bin mir aber auch net sicher vieviel bzw. ob diese eine bessere Performance mitbringen würde.

In der praxis werd ich wohl nicht mit sovielen gleichzeitgen Anfragen und Berchnungen zu tun haben, aber es geht um die Theorie mit einer starken Serverlast umzugehen.

Wie würdet ihr so ein Anwendungsfall realisieren?
Welche Datenbank und welche Datenbankverfahren würdet ihr empfehlen?
Für jegliche Anrregungen, weiterführende Literatur und Stichwörter wäre ich sehr dankbar.

 

[NBK]

Ich würde so ansetzen, dass ich die möglichen Koordinaten in Zellen aufteilen würde, wobei die Seitenlänge einer Zelle so lang sein müsste wie die gewünschte Maximaldistanz zwischen zwei Personen. Beim Speichern der Koordinaten müsste dann jeweils die zugehörige Zelle berechnet und mitgespeichert werden. Zum Suchen von in der Nähe befindlichen Personen müsste dann per Select nach Personen in der gleichen Zelle und in den acht benachbarten Zellen gesucht werden. Dadurch erhält man eine Liste aller möglichen Kandidaten. Kommt es nun auf eine exakte Berechnung an, so muss man natürlich alle diese Kandidaten einzeln prüfen, aber durch die Einteilung in Zellen hätte man die Anzahl der Fälle schon mal stark reduziert.

 

[ice-breaker]

du lädst aus der Datenbank die Daten anhand einer BoundingBox (schnell, recht genau) und filterst die bei Bedarf noch mit den genauen Formeln.
Die BoundingBox machst du auch komplett ohne Berechnung der Erdkrümung usw. einfach als ein Quadrat ausgehend von einem Punkt, das ist meist schon absolut ausreichend, brauchst du wirklich die ganz genauen Daten kannst du in Java dann die Daten noch filtern, aber alle einfach zu laden ist viel zu ineffizient.

 

[ayibogan]

Danke für die Antworten, glaube ihr meint das gleiche oder?
Wie ich das verstehe:
Eine Box bzw. Zelle hat ein min./max. latitude und ein min./max. longitude.
In de DB Abfrage hole ich dann alle Einträge die in diesen min./max. liegen und filtere diese gegebenfalls nochmals aus.

Wobei man anscheinend auch, irgendwie sowas machen kann, aber damit "(collect(the_geom)) " komme ich noch nicht ganz klar.

select st_bbox(collect(the_geom)) from <meine_Tabelle> where Bla=blubb group by irgendwas

gemoetrische Datenbanken ist grad das Stichwort wonach ich weiter suche.

 

[ayibogan]

...

 

[homer65]

HI,
Wie würdet ihr so ein Anwendungsfall realisieren?
Welche Datenbank und welche Datenbankverfahren würdet ihr empfehlen?
Für jegliche Anrregungen, weiterführende Literatur und Stichwörter wäre ich sehr dankbar.

Dafür würde ich überhaupt keine Datenbank benutzen, sondern lediglich einen zentralen Server, der die Daten in seinem RAM hält.
Die Benutzung einer Datenbank macht das nur unnötig langsam.

 

[ayibogan]

Dafür würde ich überhaupt keine Datenbank benutzen, sondern lediglich einen zentralen Server, der die Daten in seinem RAM hält.
Die Benutzung einer Datenbank macht das nur unnötig langsam.

Ich glaub für die Datenmengen die ich verwalte, wird der RAm net ausreichen oder zu Teuer werden

 

[homer65]

Ich glaub für die Datenmengen die ich verwalte, wird der RAm net ausreichen oder zu Teuer werden

Wieso? Du schriebst doch etwas von ca 1000 Personen. Dafür sollte der RAM doch sicherlich reichen, oder habe ich was falsch verstanden?

 

[ayibogan]

(können auch mehr sein).

Man bedenke dies, das Problem wäre wenn sich die Benutzer Anzahl erhöhen würde, zwar alles Theorie, aber was wenn es Plötzlich 1Mio User sind. Zudem was passiert wenn der Server abschmiert, dann sind alle Daten futsch. Die Koords sind ja eigentlich egal, da diese eh immer neu aktualisiert werden.
Evtl. meinst aber auch, das ich die "normalen Daten" wie UserID auf ner DB halte und die Koords im RAM.
Ehrlich gesagt weiß ich auch gar nicht wie das mit dem RAM halten funktioniert ( noch nie damit zu tun gehabt).


Was haltet ihr eigentlich von ObjektDatenbanken in diesem Zusammenhang?