Ich habe eine sehr große Menge von GPS-Koordinaten in einer Datenbank. Der häufigste Verwendungszweck für diese Daten wäre eine Umgebungsuche, d.h. gib mir die 10 Einträge aus der Datenbank mit der kleinsten Entfernung zu einer vorgegebenen Koordinate.

Ich könnte einfach die Entfernung zu allen Koordinaten berechnen, doch es gibt bestimmt eine effizientere Lösung. Irgendeine Datenstruktur? Eine speziele Datenbank?

Falls die Lösung des Problems ein theoretisches Konstrukt ist (z.B. Datenstruktur), wäre der Übergang ins praktische wichtig. D.h. gibt es da schon irgendwelche Libraries dafür?

EDIT:
- Koordinaten sind als Doubles in einer MySql-DB gespeichert, das kann ich aber ändern da ich volle Admin-Rechte auf der DB habe
- Die für die Umgebungssuche verwendeten Koordinaten befindet sich nicht in der DB, sie werden von einem mobilen Client geliefert

Einmal ist interessant, ob deine DB "lebt" oder ob sie konstant bleibt? Je konstanter, desto mehr kannst du mit verberechneten Werten arbeiten.

Wenn du in einem High-Performance Umfeld arbeitest, kann ich Oracle empfehlen. Deren Spatial-Erweiterungen sind sehr ausgereift. Allerdings ist die Lizenz nicht gerade billig und du müsstest deine DB wechseln.

Wenn du die Berechnung per Hand machen möchtest, gibt es noch mehr als das schon angesprochene Gitter (nennt sich auch UniformGrid), welches aber sehr schlecht skaliert. Hast du z.B. eine starke Häufung deiner Punkte in einem Quadranten, gewinnst du kaum etwas.
Es wäre jetzt etwas aufwendig, alle Optimierungsstrukturen aufzuzeigen, viele werden übrigens auch in der Computergrafik (mit einer Tiefendimension mehr) erfolgreich verwendet. Ich nenn hier nur mal einige:

UniformGrid, AdaptiveGrid, BoundingBoxes, kd-Trees, QuadTrees, R-Trees und Varianten, mehrdimensionales Hashing und alle BinaryTrees.


Auch wenn das jetzt viel klingt, schau mal in die Doku deiner DB, normalerweise sind da schon einige vorimplementiert und für die DB optimiert. Wenn du es selber machen willst, empfehle ich dir einen BoundingBoxes-Ansatz mit einem beliebiges Tree kombiniert. Damit wirst du schon recht effektiv.

wenn die aktuelle Vergleichsposition stets variabel ist, kommmst du um Rechnerei nicht herum.
Aber lass doch einfach die Datenbank rechnen.

die notwendige formel lautet:
r * arccos[sin(lat1/57.2958) * sin(lat2/57.2958) + cos(lat1/57.2958) * cos(lat2/57.2958) * cos(lng2/57.2958 -lng1/57.2958)]

wobei r der erdradius ist, also
r=3437,75 seemeilen
r=6378,16 kilometer
r=3963,2 meilen

jenachdem was du für eine einheit "herausbekommen" möchtest.

ich geme mal davon aus, du hast eine datenbanktabelle [hier a] in der du lat und lng Werte gespeichert hhast
probier es mal damit (getestet auf mysql, aber sicher auch auf andere DBs portierbar):

@set lat1 = [deine GPS-Lat-Variable]
@set lng1 = [deine GPS-Lng-Variable]
@set max_dist = [der maximale Umkreis]
@set max_treffer = [maximale anzahl treffer]

select a.* , round((6378.16 * acos(((sin(@lat1 / 57.2958) * sin(a.lat / 57.2958)) + ((cos(@lat1 / 57.2958) * cos(a.lat / 57.2958)) * cos((a.lng / 57.2958) - (@lng1 / 57.2958))))),2) AS `entf_km` 
from a 
where (6378.16 * acos(((sin(@lat1 / 57.2958) * sin(a.lat / 57.2958)) + ((cos(@lat1 / 57.2958) * cos(a.lat / 57.2958)) * cos((a.lng / 57.2958) - (@lng1 / 57.2958))))) < @max_dist
order by entf_km asc
limit @max_treffer

Ich hoffe, ich hab mich nicht mit den klammern versehen.

Wäre es eine Option, die Abstände gleich mit in der Datenbank abzulegen? Dann bräuchtest du dir nur zum gegebenen Punkt die aufwärts sortierten 10 kleinsten Werte geben zu lassen. Das ganze hängt aber vermutlich von der Menge der GPS-Punkte ab.

Vielleicht ist Dir mit http://www.opengeodb.de/ geholfen.
Das macht eigentlich ziemlich genau was Du suchst und bietet bereits eine Umkreissuche - allerdings basierend auf PHP und MySQL.
Ein Beispiel gibts hier (siehe unten auf der Seite "Orte im Umkreis von 10 km").

Selbst wenn es Dir als Programm an sich nicht weiterhelfen sollte, lassen sich da bestimmt einige Anreize entnehmen, wie dort die Speicherung und Berechnung gelöst wurde.
Zum Beispiel gibt es zur Entfernungsberechnung da auch schon einige Hinweise.

Wie du schon sagtest wäre es mühsehlig die Entfernung jeden Punktes zum Standort Punkt auszurechnen und sich dann eine Liste zurück geben zu lassen.
Aus diesem Grund spannt man ein Rechteck über den Standort der Kantenlänge X und lässt sich alle Punkte innerhalb des Rechtecks zurückgeben (bei zu wenig Punkten Kantenlänge erhöhen und nochmal abfragen).
Hat man dann X Punkte in dem Rechteck, berechnet man die Abstände zum Standort und sortiert diese. (im Buch "PHP 5 und MySQL 5" von Michael Kofler,Bernd Öggl steht dazu was bei den GIS-Funktionen)

SELECT X(b.pt) as X, Y(b.pt) Y, b.city
FROM cities as a, cities AS b
WHERE MBRCONTAINS(POLYFROMTEXT(''), b.pt);

-- und dann die Entfernung berechnen

SELECT X(b.pt) AS x, Y(b.pt) AS y, b.city,
    ROUND(GLENGTH(LINESTRINGFROMWKB(LINESTRING(ASBINARY(a.pt),ASBINARY(b.pt))))) AS dist
FROM cities AS a, (
    SELECT * FROM cities
    WHERE MBRContains(PolyFromText(''), pt)
) AS b
HAVING dist < $radius ORDER BY dist;

-- Alternativ auch mit Distance() möglich, ja nach MySQL Version

Ist etwas kompliziert, aber ich hoffe es hilft dir etwas.

Grüßle

Idealer Weise ordnet man jedem Punkt ein "Planquadrat" zu (Zum Beispiel 1° * 1°). Jedes Quadrat bekommt eine eindeudige Nummer. Sucht man nun nach POIs in der Nähe, muß man nur das eigene Quadrat und wenige benachbarten Quadrate absuchen. Das läßt sich mit "between", "in", "or" oder "union" noch halbwegs schnell erledigen.
Wahrscheinlich ist aber ein Planquardrat von 1°*1° nicht optimal für alle Suchradien. Deshalb sollten man mehrere, verschieden große Raster verwenden, z.B. 250km, 50km, 10km, 2km, 400m. Bei einem Suchradius von z.B. 3km kann man sich dann entscheiden, ob man eine größere Anzahl von Planquaraten der Größe 2km durchsucht oder nur das eine mit 10km Kantenlänge. Das hängt zum Beispiel davon ab, oder der Ausgangspunkt nahe am Rand des 10km Quadrats liegt.
Sollte kein Radius vorgegeben sein, sucht man eben erst die kleinen Quadrate ab und wenn dort nichts zu finden ist, immer größere.
P.S. Die "Planquadrate" sind natürlich nicht quadratisch, aber der besseren Anschauung wegen, benutze ich den Begriff trotzdem.