Gauß'sche Umkreissuche in der Matrix

[Markus*]

Hey Forum!
Ich möchte aus eine Datenmenge von Koordinaten all diejenigen ermitteln, die eine gewisse Nähe zueinander aufweisen. In meiner Testdatenmenge hab ich erstmal 5000 Einträge mit random-Werten zwischen 0 und 10000 in x und y sowie einer fortlaufenden ID erzeugt.

Nun hab ich erstmal stumpf folgendes Query eingetippt

SELECT gp.id, gpx.id
FROM positions gp, positions gpx
WHERE gpx.x +20 > gp.x
AND gpx.x -20 < gp.x
AND gpx.y +20 > gp.y
AND gpx.y -20 < gp.y
AND gpx.id != gp.id

was mir auch wie zu erwarten ein sinnvolles Resultat ausgibt, wenn auch 12 <-> 3 und zusätzlich auch noch 3 <-> 12 gefunden wird, was erstmal unkritisch ist. Wie allerdings auch zu erwarten war, dauert das Ganze ne Weile. Hat jemand ne intelligente Idee, wie man sowas besser lösen kann?

Thanks und Gruß!

[Tom]

Hello,

heißt das, dass Du zu jedem Eintrag den Umkreis absuchen willst?

Kennt Dein DBMS auch "between"?

Liebe Grüße aus Syburg bei Dortmund

Tom vom Berg

[Markus*]

Hello,

Jo, hallo!

heißt das, dass Du zu jedem Eintrag den Umkreis absuchen willst?

Genau - ich will gucken ob und welche koordinaten sich in der Nähe von jedem punkt befinden. Laut dem kleinen Gauß wärend dafür also n*(n-1) operationen notwendig. Bei im Testfall 5000 Punkten also 12495000 vergleiche.

Und MySQL 5 kennt BETWEEN, ja!

Gruß!

[Cheatah]

Hi,

Laut dem kleinen Gauß wärend dafür also n*(n-1) operationen notwendig. Bei im Testfall 5000 Punkten also 12495000 vergleiche.

ich unterstelle mal, dass der kleine Gauß einen anderen Algorithmus verwendet als ein handelsübliches, zudem Index-taugliches DBMS.

Cheatah

[Markus*]

ich unterstelle mal, dass der kleine Gauß einen anderen Algorithmus verwendet als ein handelsübliches, zudem Index-taugliches DBMS.

Ganz sicher, dennoch wüßte ich gerne ob jemand ne idee für ein Datenmodell hat, sowas geschickt einzufädeln um es mittels handelsüblichem, indextauglichem DBMS bearbeiten zu können.

Gruß!

[Bademeister]

Hi Markus**

Also mir ist noch nicht hundertprozentig klar, was Du eigentlich willst.

Genau - ich will gucken ob und welche koordinaten sich in der Nähe von jedem punkt befinden.

Das willst Du wahrscheinlich nicht, denn die Menge dieser Punkte ist mit hoher Wahrscheinlichkeit leer. Willst Du fuer JEDEN Punkt nacheinander eine Liste aller Punkte, die nah dran sind? Wenn dem so ist, dann

1. macht es durchaus Sinn, dass Du wie in Deinem Beispiel 3 <--> 12 und 12 <-, 3 findest (wenn denn 3 und 12 Punkte waeren).

2. waere ein jeweiliger Index fuer die Spalten der Koordinaten wahrscheinlich sehr hilfreich fuer die Effizienz der Abfrage

Denke uebrigens daran, dass der "Abstand", den Du als Bedingung in Deiner Abfrage umsetzt, nicht der Euklidische ist.

Viele Gruesse,
der Bademeister

* ich habe uebrigens die zu Markus* gehoerige Fussnote vermisst ;-)

[Markus** :-)]

Hi Markus**

Ja, Hallo!

Also mir ist noch nicht hundertprozentig klar, was Du eigentlich willst.

Ich möchte von jedem der 5000 Punkte wissen, welche anderen Punkte sich in dessen Umgebung befinden. Ist eigentlich ganz einfach! :)

1. macht es durchaus Sinn, dass Du wie in Deinem Beispiel 3 <--> 12 und 12 <-, 3 findest (wenn denn 3 und 12 Punkte waeren).

3 und 12 sind punkte, genau!

Viele Gruesse,
der Bademeister

* ich habe uebrigens die zu Markus* gehoerige Fussnote vermisst ;-)

OK

Gruß

[steckl]

Hi,

SELECT gp.id, gpx.id
FROM positions gp, positions gpx
WHERE gpx.x +20 > gp.x
AND gpx.x -20 < gp.x
AND gpx.y +20 > gp.y
AND gpx.y -20 < gp.y
AND gpx.id != gp.id

was mir auch wie zu erwarten ein sinnvolles Resultat ausgibt

Ist das wirklich das was du willst?
Angenommen du willst alle Punkte in der Nähe von (0;0), dann würde deine Abfrage z.B. den Punkt (19;19) liefern, aber nicht den Punkt (21;0). Wobei der Abstand von (0;0) zu (19;19) (~27) größer ist als von (0;0) zu (21;0) (=21).
Es heißt ja Um_kreis_suche und nicht Um_quadrat_suche. Oder hast du das nur zur Vereinfachung so gemacht?

mfG,
steckl

[Markus**]

Es heißt ja Um_kreis_suche und nicht Um_quadrat_suche. Oder hast du das nur zur Vereinfachung so gemacht?

Ja, das ist nur um es einfacher zu halten. Um_kreis_suche ist evtl. auch nicht ganz korrekt gesagt. :)

Gruß!

[Daniel Thoma]

Hallo Markus*,

Prinzipiell muss man dazu natürlich jeden Punkt mit jedem vergleichen, was zu von Dir schon festgestellten quadratischen Komplexität führt. Im allgemeinen Fall kann man daran nichts ändern, allerdings gelten vermutlich zwei Dinge, die das etwas einfacher machen sollten:
Die Punkte sind mehr oder weniger gleichmäßig über eine große (quadratische) Fläche verteilt und der Umkreis (oder vielmehr das Umquadrat) ist relativ dazu klein.

Im Folgenden nehmen wir mal an, die Gesamtfläche und die Umkreisfläche seien Quadrate.
Wenn wir nun irgend eine Teilfläche betrachten und dafür jeweils die Punkte im Umkreis betrachten wollen, so müssen wir nur die Punkte auf der Teilfläche mit allen Punkten vergleichen, die höchstens so weit von der Teilfläche wegliegen, wie der Umgebungsabstand angibt.
Wir nutzen quasi aus, dass Punkte, die viel zu weit weg von unserer Teilfläche sind, erst gar nicht in Frage für die Umgebung eines Punktes auf der Teilfläche kommen.
Wählen wir unsere Teilfläche gleich der Gesammtfläche, gewinnen wir natürlich nichts, wählen wir sie so, dass gerade ein Punkt drauf liegt, gewinnen wir auch nichts, aber irgendwo dazwischen könnten wir mit weniger Vergleichen durchkommen.

Betrachten wir also zunächst die Komplexität dieses Algorithmus:
n: Anzahl der Punkte
s: Seitenlänge der Gesamtfläche
d: Umgebungsseitenlänge
l: Seitenlänge einer Teilfläche

x = (s / l)²: Anzal der Teilflächen, die auf die Gesammtfläche passen.
y = (s / d)²: Anzahl der Umgebungsflächen, die auf die Gesammtfläche passen.

Für jede Teilfläche müssen wir die Punkte darauf vergleichen: n²/x² - n/x Schritte
Für jede Teilfläche müssen wir die Punkte mit den Punkten der angrenzenden acht Umgebungsflächen vergleichen: 8 * n/x * n/y
Für jede Teilfläche müssen wir die Punkte darauf bestimmen: n Schritte
Für die Komplexität ergibt sich also:
f(n) = (8 * n/x * n/y + n²/x² - n/x + n) * x = 8 * n²/y + n²/x - n + n*x

Nun müssen wir bestimmen, welches l bzw x optimal ist (mittels der Ableitung von f(n) nach x):
df/dx (n) = - n²/x² + n = 0
n*x² = n²
x² = n
x = n^(1/2)
somit:
(s/l)² = n^(1/2)
s/l = n^(1/4)
l = s / n^(1/4)
Nun haben wir das optimale x bzw. l und können das in f(n) einsetzen:

g(n) = 8 * n²/y + n²/n^(1/2) - n + n * n^(1/2) = 8 * n² / y - n

Nun haben wir die Komplexität, wenn wir die Teilflächen optimal wählen.
Wie man sieht, kann ein großes y bzw. kleines d die Anzahl der Schritte verringern. Jetzt müssen wir natürlich noch wissen, wie klein d sein muss, damit dieser Algorithmus besser ist, als der naive Ansatz:
8 * n² / y - n < n² - n
8 * d² / s² < 1
d² < s²/8
d < s/8^(1/2) ~= 0.35*s

Wenn also der Abstand kleiner als 1/3 der Gesamtseitenlänge ist, ist unser neuer Algorithmus besser.

Bleibt noch die Frage, wie man das elegant in SQL realisiert.
Die einfachste Variante ist sicher, für jede Teilfläche ein Query durchzuführen (sinnvollerweise mit einem Perpared Statement oder als Stored Procedure).

Was in den Betrachtungen noch nicht eingeflossen ist, sind DB-Indexe.
Wenn der Verwendete Index das schnelle Selektieren nach Koordinatenbereichen ermöglich, als beispielsweise in logarithmischer Zeit, sollte schon der naive Ansatz relativ gut sein und diese Variante bringt nicht mehr viel (müsste man analysieren).
Ich weiß auch nicht, wie schlau Dein DBMS in Deinem Fall ist und ob es tatsächlich zunächst die komplette JOIN-Tabelle aufbaut. Evtl. bringt es schon was, die Bedinung als JOIN-Bedingung unterzubringen.

Grüße

Daniel

[Markus**]

Hallo Markus*,

Hallo Daniel!
Erstmal vielen Dank für Deine absolut geniale Antwort! Ich hab den Lösungsansatz mal weiterverfolgt und konnte leider keine großartige Verbesserung in Sachen Rechenzeit vollbringen. Fakt ist, dass es offenbar ein bißchen schneller ist, aber im Großen und Ganzen konnte ich die Verarbeitungszeit um 1/3 von 15 auf 10 sek. und nicht auf ein drittel reduzieren. Das liegt wohl am höheren Rechenaufwand innerhalb der Routine.

Allerdings habe ich noch einen ganz anderen Lösungsansatz verfolgt, der ein gutes Resultat erzielt. Und zwar habe ich für jede Zufallskoordinate (5000stk) auf meiner Testmatrix von 10000x10000 Punkten eine Art Matrize erstellt, die ich absolut simpel ohne großen Aufwand vergleichen kann. Damit komm ich auf durchaus aktzeptable Resultate, <= 1 sekunde.

Gruß, Markus**

[Daniel Thoma]

Hallo Markus**,

Fakt ist, dass es offenbar ein bißchen schneller ist, aber im Großen und Ganzen konnte ich die Verarbeitungszeit um 1/3 von 15 auf 10 sek. und nicht auf ein drittel reduzieren.

Die 1/3 bezogen sich nicht auf die Laufzeit, sondern auf das nötige Verhältnis von Gesammtseitenlänge zu Umgebungsseitenlänge, damit der Algorithmus besser ist.

Um den Bruchteil q der Laufzeit zu erreichen, muss eine engere Bedingung gelten:

8*n²*d²/s² = q*(n² - n)
8*n*d²/s² = q*(n - 1)
d²/s² = q/8 - q/(8*n)
Für "große" n gilt dann:
d²/s² ~= q/8
Im Fall von 2/3 müsste d/s ~= (2/(3*8))^1/2 = 1/12 ~= 0.083
Wäre bei Deinem Abstand von 20 also eine Seitenlänge von 240.
Kommt das bei Deinen Daten hin? Wäre eher überraschend, wenn das so gut stimmen würde ;-)

Allerdings habe ich noch einen ganz anderen Lösungsansatz verfolgt, der ein gutes Resultat erzielt. Und zwar habe ich für jede Zufallskoordinate (5000stk) auf meiner Testmatrix von 10000x10000 Punkten eine Art Matrize erstellt, die ich absolut simpel ohne großen Aufwand vergleichen kann. Damit komm ich auf durchaus aktzeptable Resultate, <= 1 sekunde.

Ich verstehe ehrlich gesagt nicht, was Du da jetzt tust.
Was ich mir vorstellen könnte, ist, dass die Testmatrix geordnet ist, dann kann man die Umgebung zu einem Punkt ja sehr schnell bestimmen, weil man nicht mit jedem Punkt vergleichen muss. Theoretisch sollte man aber ja schon verloren haben, wenn man diese Matrix überhaupt aufbaut.

Mir ist übrigens noch folgendes aufgefallen:
Wenn man annimmt, dass die Anzahl der Punkte im Umkreis konstant ist, gilt:
c = n/(s/d)²
(s/d)²=n/c
Damit ergibt sich für die Komplexität:
8*n²/(s/d)² - n = 8*n²*c/n - n = 8*c*n - n
Damit wäre der Algorithmus sogar linear in der Anzahl der Punkte bzw der Fläche des betrachteten Gebiets. Zumindest asymptotisch geht es also gar nicht mehr besser. (Da das gesuchte Ergebnis schon lineare Größe hat, kann der Algorithmus auch nicht schneller sein, da er schon für die Ausgabe diese Zeit benötigt).
Vergrößert man dagegen c (also im Prinzip die "Auflösung" der Daten), hat man, da n natürlich mit c wächst, wieder quadratische Komplexität.

Für die Praxis sagt das aber natürlich immer noch relativ wenig, vor allem, wenn man noch recht kleine Zahlen hat. Und 5000 Datensätze ist ja im Prinzip noch relativ wenig.

Grüße

Daniel