Clustering Lat / Longs in un database

Question

Sto cercando di vedere se qualcuno sa come raggruppare alcuni risultati Lat / Long, usando un database, per ridurre il numero di risultati inviati via cavo all'applicazione.

Esistono numerose risorse su come eseguire il clustering, sul lato client O sul lato server (applicazione) .. ma non sul lato database :(

Questa è una domanda simile , posta da un collega S.O. membro. Le soluzioni sono basate sul lato server (es. Codice C # dietro).

Qualcuno ha avuto fortuna o esperienza nel risolvere questo problema, ma in un database? Ci sono dei guru del database là fuori che sono alla ricerca di una sfida DB sexy e sexy?

per favore aiutate :)

MODIFICA 1: Chiarimento: per raggruppamento, spero di raggruppare x numero di punti in un singolo punto, per un'area. Quindi, se dico raggruppare tutto in un quadrato di 1 miglio / 1 km, allora tutti i risultati in quel 'quadrato' sono GRUPPO in un unico risultato (diciamo ... al centro del quadrato).

EDIT 2: sto usando MS Sql 2008, ma sono aperto a sapere se ci sono altre soluzioni in altri DB.

Answer 1

Probabilmente userei una versione modificata * di k -means raggruppamento usando le coordinate cartesiane (es. WGS-84 ECF) per i tuoi punti. È facile implementare & amp; converge rapidamente e si adatta ai tuoi dati, qualunque sia l'aspetto. Inoltre, puoi scegliere k per soddisfare i tuoi requisiti di larghezza di banda e ogni cluster avrà lo stesso numero di punti associati (mod k).

Realizzerei una tabella di centroidi di cluster e aggiungerei un campo alla tabella di dati originale per indicare anche a quale cluster apparteneva. Ovviamente vorresti aggiornare periodicamente il cluster se i tuoi dati sono per nulla dinamici. Non so se potresti farlo con una procedura memorizzata & amp; trigger, ma forse.

* La "modifica" sarebbe regolare la lunghezza dei vettori del centroide calcolati in modo che si trovassero sulla superficie della terra. Altrimenti ti ritroveresti con un mucchio di punti con altitudine negativa (quando riconvertito in LLH).

Answer 2

Se stai raggruppando in una posizione geografica e non riesco a immaginare che sia qualcos'altro :-), potresti memorizzare l'ID cluster "quot" nel database insieme alle coordinate lat / long.

Ciò che intendo con ciò è dividere la mappa del mondo in (per esempio) una matrice 100x100 (10.000 cluster) e ciascuna coordinata viene assegnata a uno di quei cluster.

Quindi, puoi rilevare coordinate molto vicine selezionando quelle nello stesso quadrato e chiudendole moderatamente selezionando quelle nei quadrati adiacenti.

La dimensione dei tuoi quadrati (e quindi il loro numero) sarà decisa dalla precisione del clustering. Ovviamente, se hai solo una matrice 2x2, potresti ottenere un raggruppamento di coordinate che sono molto distanti.

Yo avrà sempre i casi limite come due punti vicini ma in diversi cluster (uno più a nord nel suo cluster, l'altro più a sud nel suo) ma è possibile regolare la dimensione del cluster O post- elaborare i risultati sul lato client.

Answer 3

Ho fatto una cosa simile per un'applicazione geografica in cui volevo assicurarmi di poter memorizzare facilmente i set di punti nella cache. Il mio codice di geohashing è simile al seguente:

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

Tutto è diventato davvero facile da lì. Avevo un po 'di codice per afferrare tutti i blocchi da un determinato punto a un determinato raggio che si traduceva in un singolo multiget memcache (e un po' di codice per riempire quello quando mancava).

Answer 4

Per movielandmarks.com ho usato il codice cluster dal Mike Purvis , uno degli autori di Inizio delle applicazioni Google Maps con PHP e AJAX . Costruisce alberi di cluster / punti per diversi livelli di zoom utilizzando PHP e MySQL, memorizzandoli nel database in modo che il richiamo sia molto veloce. Alcuni di questi potrebbero esserti utili anche se stai utilizzando un database diverso.

Answer 5

Perché non testare più approcci?

1. traduci la weka nella CLI .NET con IKVM.NET
2. aggiungi un assembly risultante dal tuo codice e weka.dll (usa ilmerge) nel tuo database

Fai dei test, cioè. Nessun cluster specifico funziona meglio di chiunque altro.

Answer 6

Credo che tu possa usare i tipi di dati spaziali di MSSQL . Se sono simili ad altri tipi di dati spaziali che conosco, memorizzeranno i tuoi punti in un albero di rettangoli, quindi puoi andare ai rettangoli a risoluzione inferiore per ottenere cluster impliciti.