Clustering Lat / Longs dans une base de données

Question

J'essaie de voir si quelqu'un sait comment regrouper certains résultats Lat / Long à l'aide d'une base de données, afin de réduire le nombre de résultats envoyés par fil à l'application.

Il existe un certain nombre de ressources sur la mise en cluster, soit du côté client OU du côté serveur (application) .. mais pas du côté base de données: (

C’est une question similaire , posée par un collègue. membre. Les solutions sont basées sur le serveur (code C # derrière).

Quelqu'un at-il eu de la chance ou de l'expérience dans la résolution de ce problème, mais dans une base de données? Existe-t-il des gourous de bases de données qui poursuivent un défi hawt and sexy DB?

aidez s'il vous plaît:)

EDIT 1: Clarification - par regroupement, j'espère regrouper x nombre de points en un seul point, pour une zone. Donc, si je dis que tout est regroupé dans un kilomètre carré, tous les résultats de ce carré sont groupés en un seul résultat (disons ... au milieu du carré).

EDIT 2: J'utilise MS SQL 2008, mais je suis ouvert à toute possibilité de savoir s'il existe d'autres solutions dans d'autres DB.

Answer 1

J'utiliserais probablement une version * modifiée de k -means regroupement en utilisant les coordonnées cartésiennes (par exemple, WGS-84 ECF) de vos points. Il est facile à mettre en œuvre & amp; converge rapidement et s'adapte à vos données, peu importe à quoi elles ressemblent. De plus, vous pouvez choisir k en fonction de vos besoins en bande passante, et chaque cluster aura le même nombre de points associés (mod k).

Je ferais une table des centroïdes de cluster et ajouterais un champ à la table de données d'origine pour indiquer à quel cluster il appartenait également. Vous voudrez évidemment mettre à jour la mise en cluster périodiquement si vos données sont du tout dynamiques. Je ne sais pas si vous pouvez le faire avec une procédure stockée & amp; déclencheur, mais peut-être.

* La " modification " serait d’ajuster la longueur des vecteurs centroïdes calculés pour qu’ils se trouvent à la surface de la Terre. Sinon, vous vous retrouveriez avec un tas de points d’altitude négative (lorsqu’ils sont reconvertis en LLH).

Answer 2

Si vous effectuez un regroupement géographique, et que je ne peux imaginer que ce soit autre chose :-), vous pouvez stocker le " identifiant de cluster ". dans la base de données avec les coordonnées lat / long.

Ce que je veux dire par là, c'est diviser la carte du monde en (par exemple) une matrice 100 x 100 (10 000 grappes) et chaque coordonnée est assignée à l'une de ces grappes.

Ensuite, vous pouvez détecter des coordonnées très proches en les sélectionnant dans le même carré et modérément proches en sélectionnant celles situées dans des carrés adjacents.

La taille de vos carrés (et donc leur nombre) dépendra de la précision du classement. Évidemment, si vous n’avez qu’une matrice 2x2, vous pourriez obtenir un regroupement de coordonnées très éloignées.

Yo aura toujours les cas extrêmes tels que deux points rapprochés mais dans des clusters différents (l’un au nord dans son cluster, l’autre au sud dans son) mais vous pouvez ajuster la taille du cluster OU traiter les résultats côté client.

Answer 3

J'ai fait la même chose pour une application géographique où je voulais m'assurer de pouvoir facilement mettre en cache des ensembles de points. Mon code de géolocalisation ressemble à ceci:

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

Tout est vraiment facile à partir de là. J'avais un code pour récupérer tous les morceaux d'un point donné à un rayon donné qui se traduirait par un seul multiget memcache (et un code permettant de renvoyer le fichier lorsqu'il le manquait).

Answer 4

Pour movielandmarks.com , j'ai utilisé le code de clustering de Mike Purvis , l'un des auteurs de Début des applications Google Maps avec PHP et AJAX . Il construit des arbres de clusters / points pour différents niveaux de zoom en utilisant PHP et MySQL, en les stockant dans la base de données afin que le rappel soit très rapide. Certaines peuvent vous être utiles même si vous utilisez une base de données différente.

Answer 5

Pourquoi ne pas tester plusieurs approches?

1. traduisez la bibliothèque weka dans la CLI .NET avec IKVM.NET
2. ajoutez un assemblage résultant de votre code et de weka.dll (utilisez ilmerge) dans votre base de données

Faites des tests, c’est-à-dire. Aucune classification spécifique ne fonctionne mieux que quiconque.

Answer 6

Je pense que vous pouvez utiliser les types de données spatiales de MSSQL . S'ils ressemblent à d'autres types de données spatiales que je connais, ils stockeront vos points dans une arborescence de rectangles. Vous pourrez ensuite accéder aux rectangles de résolution inférieure pour obtenir des clusters implicites.