Clustering Lat / Longs in einer Datenbank

Question

Ich versuche, jemand zu sehen, ob weiß, wie einige Breite / Länge Ergebnisse clustern, eine Datenbank, die Anzahl der Ergebnisse über den Draht an die Anwendung gesendet zu reduzieren.

Es gibt eine Reihe von Ressourcen, wie Cluster, entweder auf der Client-Seite oder in der Server (Anwendung) Seite .. aber nicht in der Datenbank Seite: (

Dies ist eine ähnliche Frage , von einem anderen fragte S. O. Mitglied. Die Lösungen sind Server-Seite basiert (dh. C # -Code hinter).

Hat jemand etwas Glück oder Erfahrung mit der Lösung dieses hatte, aber in einer Datenbank? Gibt es da draußen Datenbank-Guru, sind nach einer hawt und sexy DB Herausforderung?

Bitte helfen:)

EDIT 1: Klarstellung - durch Clustering, ich bin der Hoffnung, zu einer Gruppe x Anzahl von Punkten in einem einzigen Punkt, für eine Fläche. Also, wenn ich sagen Cluster alles in einem 1 Meile / 1 km Platz, dann werden alle Ergebnisse, dass ‚Quadrat‘ sind GROUP'D in ein einziges Ergebnis (sagen wir ... die Mitte des Platzes).

EDIT. 2: Ich bin mit MS SQL 2008, aber ich bin offen zu hören, wenn es andere Lösungen in anderer DB

Answer 1

Ich würde wahrscheinlich eine modifizierte Version * von k -Mittel Clustering des kartesischen (zB WGS-84 ECF) Koordinaten für Ihre Punkte verwenden. Es ist einfach zu implementieren und konvergiert schnell und passt sich an Ihre Daten, egal wie es aussieht. Darüber hinaus können Sie wählen k Ihre Bandbreitenanforderungen entsprechen, und jeder Cluster die gleiche Anzahl von zugehörigen Punkten (mod k).

würde ich eine Tabelle von Clusterzentren machen, und ein Feld auf die ursprüngliche Datentabelle hinzufügen, um anzuzeigen, was clustern es auch gehörte. Sie würden wollen offensichtlich das Clustering in regelmäßigen Abständen aktualisieren, wenn Sie Ihre Daten überhaupt dynamisch ist. Ich weiß nicht, ob Sie das mit einer gespeicherten Prozedur & Trigger tun könnten, aber vielleicht.

* Die „Änderung“ wäre die Länge der berechneten Schwerpunktsvektoren anzupassen, so dass sie auf der Oberfläche der Erde sein würden. Sonst würde man mit einem Haufen Punkten mit negativer Höhe am Ende (wenn der Artikel wieder auf LLH umgewandelt).

Answer 2

Wenn Sie sich auf geographische Lage Clustering, und ich kann es sich nicht vorstellen, etwas anderes :-) ist, können Sie die „Cluster-ID“ in der Datenbank zusammen mit den lat / long-Koordinaten.

Was ich damit meine, dass ist die Weltkarte in (zum Beispiel) eine 100x100-Matrix (10.000 Cluster) und jede Koordinate teilen wird zu einem dieser Cluster zugeordnet.

Dann können Sie erkennen, ganz in der Nähe von Koordinaten durch die in angrenzenden Feldern auswählen.

die in den gleichen Platz und mäßig schließen diejenigen Auswahl

Die Größe der Quadrate (und damit die Anzahl von ihnen) wird entschieden werden, wie genau Sie müssen das Clustering sein. Natürlich, wenn Sie nur eine 2x2-Matrix haben, könnten Sie eine Häufung von Koordinaten erhalten, die ein langer Weg voneinander entfernt sind.

Yo immer die Grenzfälle haben wie zwei Punkte nahe beieinander, aber in verschiedenen Clustern (ein nördlichste in seinem Cluster, der andere südlichste in seiner), aber man konnte die Clustergröße ODER einstellen post- verarbeitet die Ergebnisse auf der Client-Seite.

Answer 3

Ich habe eine ähnliche Sache für eine geographische Anwendung, wo ich, ich könnte Punktmengen leicht zwischenzuspeichern, um sicherzustellen wollte. Mein geohashing Code sieht wie folgt aus:

def compute_chunk(latitude, longitude)
  (floor_lon(longitude) * 0x1000) | floor_lat(latitude)
end

def floor_lon(longitude)
  ((longitude + 180) * 10).to_i
end

def floor_lat(latitude)
  ((latitude + 90) * 10).to_i
end

Alles hat wirklich von dort einfach. Ich hatte einen Code für alle die Stücke von einem bestimmten Punkt zu einem bestimmten Radius greifen, die in einem einzigen memcache multiget übersetzen würde (und einige Code verfüllen, dass, wenn es fehlt).

Answer 4

movielandmarks.com verwendete ich den Clustering-Code von Mike Purvis , einer der Autoren von Beginning Google maps Anwendungen mit PHP und AJAX . Es baut Bäume von Clustern / Punkten für verschiedene Zoomstufen mit PHP und MySQL, es in der Datenbank gespeichert, so dass Rückruf sehr schnell ist. Einige davon können Sie sogar nützlich sein, wenn Sie eine andere Datenbank verwenden.

Answer 5

Warum mehrere Ansätze nicht testen?

1. übersetzen die weka Bibliothek in .NET CLI mit IKVM.NET
2. fügen Sie eine Baugruppe in Folge aus dem Code und weka.dll (Verwendung ILMerge) in der Datenbank

einige Tests Stellen, das ist. Keine spezifischen Clustering funktioniert besser als jeder andere.

Answer 6

Ich glaube, können Sie MSSQL räumliche Datentypen . Wenn sie auf andere Arten räumlicher Daten ähnlich sind Ich weiß, sie werden Ihre Punkte in einem Baum von Rechtecken speichern, und dann können Sie zu den niedrigen aufgelösten Rechtecken gehen zu implizitem Cluster zu erhalten.