Gfoss -- Geographic Free and Open Source Software - Italian mailing list

Re: VirtualKNN e max_distance

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

5 messages Options

a.furieri

Re: VirtualKNN e max_distance

On Sat, 29 May 2021 07:11:42 -0700 (MST), pigreco wrote:
> Forse le query non sono scritte in modo ottimale, ma secondo me un
> parametro
> max_distance nelle virtualKNN aiuterebbe molto
>

Toto' scusami tanto per la sincerita' forse brutale,
ma introdurre un parametro MaxDistance nel KNN e'
un completo nonsense logico.

mi spiego meglio: se l'approccio KNN ha qualcosa di
meritevole e' proprio nel fatto che ti consente di
lavorare su datasets di cui ignori completamente
la distribuzione spaziale delle features.
non importa se in alcuni casi troverai distanze
minime di pochi metri ed in altri di migliaia di
chilometri, il KNN ti trovera' sempre e comunque
quali sono le features piu' vicine le une alle
altre.

se invece hai gia' un'idea di massima di una
"ragionevole" distanza massima entro cui speri
di trovare delle possibili corrispondenze,
allora l'approccio KNN e' del tutto ridondante,
perche' una banalissima query basata sull'uso
convenzionale dello SpatialIndex imponendo
il raggio di distanza atteso nel codice della
tua query SQL sara' sempre sicuramente piu'
performante.

le due cose (KNN e MaxDistance) non stanno
assieme, sono mutuamente esclusive; o l'uno
o l'altra.

riassumendo: se conosci a priori un raggio di
distanza "ragionevole" allora la tua query puo'
essere riscritta come segue facendo del tutto
a meno ti tirare in ballo il KNN:

CREATE TABLE civici10m AS
SELECT p.id AS id_punto, s.id AS id_strada, Min(ST_Distance(s.geom,
p.geom)) AS distance,
ST_shortestline(p.geom, s.geom) as geom
FROM civici AS p
LEFT JOIN strade AS s ON (ST_Distance(s.geom, p.geom) < 10.0 AND s.id
IN (
SELECT rowid
FROM SpatialIndex
WHERE f_table_name = 'strade'
AND f_geometry_column = 'geom'
AND search_frame = ST_Buffer(p.geom, 10.0)))
GROUP BY p.id;

giusto per avere un'idea dei tempi di esecuzione
con datasets "pesantucci" ho testato la query
nelle condizioni seguenti:

a) grafo stradale ITER.NET di regione toscana
(oltre 400mila archi)
i punti di fermata degli autobus toscani
sparsi su tutta le regione (circa 38mila)
la query gira in meno di 10 sec

b) solito grafo stradale
i numeri civici della toscana (poco piu'
di 1 milione e mezzo)
qua evidentemente i dimensionamenti si
fanno sentire, ma comunque se la cava
in circa 4 minuti, che definirei un
tempo decisamente confortevole.

ciao Sandro

piccolo approfondimento tecnico: il KNN e'
un modulo molto sofisticato che va ad
intrufolarsi direttamente dentro alla
struttura interna degli R*Tree che sono
alla base dello SpatialIndex.
non e' necessariamente un fulmine di
velocita' perche' per esplorare tutti
i nodi dell'albero (almeno della parte
piu' interessante) occorre tempo, pero'
e' completo e sicuramente trova tutti
i possibili candidati.

in tutti gli altri casi l'approccio classico
di tipo dicotomico e' sicuramente preferibile.

_______________________________________________
[hidden email]
http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
Questa e' una lista di discussione pubblica aperta a tutti.
I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.
764 iscritti al 23/08/2019

Maurizio Trevisani

Re: VirtualKNN e max_distance

Si, credo che tu abbia ragione.

Il sab 29 mag 2021, 16:11 pigreco <[hidden email]> ha scritto:

> Buongiorno,
> non so se è il modo giusto e la ML corretta per chiedere, forse, una
> Feature
> Request per SpatiaLite,
> in caso negativo chiedo scusa per il runore.
>
> Ko studiato e usato le favolose VirtualKNN presenti in spatialite [0] per
> calcoli di distanze minime tra punti e linee su grandi dataset (milioni di
> righe) e ho notato che l'approccio classico dell'uso degli indici spaziali
> è
> enormemente più performante rispetto all'uso dei VirtualKNN (2 sec contro
> 100 secondi) questo è dovuto anche al fatto che non esiste, nelle
> virtualKNN, l'opzione max_distance e quindi calcola le distanze su tutte le
> righe.
>
> queste le due query a confronto, stessi dati in input e stessi output:
> - geo-tabella `route` linestring 32632 con 116674 feature
> - geo-tabella `scuole` point 32632 con 5529 feature
>
> uso VirtualKNN:
>
> CREATE TABLE t_scuole_100mKNN AS
> SELECT d.chiave_uni, d.fid as id_route, d.distance as distance,
> ST_shortestline(d.geometry, s.geometry) as geom
> FROM
> (SELECT a.fid as fid, a.distance as distance, zz.chiave_uni as
> chiave_uni,zz.geometry
> FROM knn as a
> JOIN
> scuole as zz
> WHERE f_table_name = 'route'
> AND f_geometry_column = 'geometry'
> AND ref_geometry = zz.geometry
> AND max_items = 1) d,
> route s
> WHERE ST_Distance(s.geometry, d.geometry) <= 100 and id_route = s.ogc_fid
> ORDER BY d.chiave_uni;
> SELECT
> RecoverGeometryColumn('t_scuole_100mKNN','geom',32632,'LINESTRING','XY');
>
> output 1737 righe
> impiega circa 100 secondi
>
> uso spatialIndex classico
>
> CREATE TABLE t_scuole_100mMBR AS
> SELECT a.ogc_fid as id_route, Min(ST_Distance(a.geometry, zz.geometry)) AS
> distance,
> zz.chiave_uni as chiave_uni, st_shortestline (a.geometry, zz.geometry)
> as geom
> FROM route as a, scuole as zz
> WHERE ST_Distance(a.geometry, zz.geometry) <= 100 AND a.ogc_fid IN (
> SELECT rowid
> FROM SpatialIndex
> WHERE f_table_name = 'route'
> AND search_frame = BuildCircleMbr(ST_X(zz.geometry),
> ST_Y(zz.geometry), 100))
> GROUP by zz.chiave_uni;
> SELECT
> RecoverGeometryColumn('t_scuole_100mMBR','geom',32632,'LINESTRING','XY');
>
> output 1737 righe
> impiega circa 2 secondi
>
> Forse le query non sono scritte in modo ottimale, ma secondo me un
> parametro
> max_distance nelle virtualKNN aiuterebbe molto
>
> grazie
>
> [0] https://www.gaia-gis.it/fossil/libspatialite/wiki?name=KNN
>
> -----
> https://pigrecoinfinito.wordpress.com/
> --
> Sent from:
> http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/
> _______________________________________________
> [hidden email]
> http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
> Questa e' una lista di discussione pubblica aperta a tutti.
> I messaggi di questa lista non hanno relazione diretta con le posizioni
> dell'Associazione GFOSS.it.
> 764 iscritti al 23/08/2019

_______________________________________________
[hidden email]
http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
Questa e' una lista di discussione pubblica aperta a tutti.
I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.
764 iscritti al 23/08/2019

Maurizio Trevisani

Re: VirtualKNN e max_distance

In reply to this post by a.furieri

Devi scrivere sulla mailing list di spatialite.
Ciao,
Maurizio

Il sab 29 mag 2021, 16:11 pigreco <[hidden email]> ha scritto:

a.furieri

Re: VirtualKNN e max_distance

On Sat, 29 May 2021 12:51:54 -0700 (MST), pigreco wrote:

> Maurizio Trevisani wrote
>> Devi scrivere sulla mailing list di spatialite.
>> Ciao,
>> Maurizio
>
> Buonasera,
> ormai penso sia tardi, la mia idea è stata bocciata.
>
> le prossime volte scriverò in lista spatialite.
>

Toto' e Maurizio,

non vorrei che la mia risposta precedente sia suonata
troppo perentoria.

se ritente che un KNN basato sul concetto di MaxDistance
possa essere utile e' una cosa assolutamente praticabile,
ma deve essere ben chiaro che non avra' nulla a che fare
con il KNN attuale perche' sara' basata su criteri del
tutto diversi. in altre parole, non sara' una modifica
dell'attuale, ma una implementazione nuova di pacca a
partire da zero.

schematizzando per quanto possibile: il KNN attuale e'
basato su una interfaccia molto speciale di SQLite che
consente di traversare la struttura ad albero R*Tree
a basso livello. non c'e' nessuno spazio per introdurre
un concetto di MaxDistance, c'e' solo da esplorare
tutti i rami dell'albero potenzilament interessanti,
che e' un'oparazione che fornisce risultati perfetti
ma che ovviamente richiede del tempo.

quello che invece e' ipotizzabile e' un approccio
radicalmente diverso, che lasci perdere le API ultra
sofisticate di SQLite e che lavori internamente a
forza di query SQL "normali" basate sullo SpatialIndex
tradizionale. ed in questo caso il criterio della
MaxDistance nota a priori diventa un requisito
ineluttabile per ottenere una ragionevole velocita'
di esecuzione.

dal punto di vista dell'utente cambia poco (giusto
un parametro in piu, la MaxDistance), ma dal punto
di vista del codice cambia assolutamente tutto, non
si salva neppure una riga dell'esistente.

--------------------

detto di striscio: il KNN sta causando diversi
problemi agli utenti Java, Python, PHP e C#,
specie su Windows.

tutti questi linguaggi hanno dei connettori per
SQLite che quasi sempre utilizzano la propria
libsqlite3.dll privata interna che spesso e' di
una versione differente da quella utilizzata
da mod_spatialite, e magari e' stata compilata
con opzioni differenti.
una combinazione che non porta a nulla di buono
in termini di stabilita' e compatibilita'.

l'unica causa che scatena tutti questi conflitti
e' proprio il KNN che dipende in modo critico dal
supporto della libsqlite3. tutto funziona bene
se la libsqlite3 utilizzata a runtime e' esattamente
la stessa usata in compilazione (come accade p.es.
per SpatialiteGUI e suppongo anche per QGIS),
altrimenti si avranno sicuramente problemi piu'
o meno seri.

capite dunque che a me personalmente farebbe anche
molto comodo "fare fuori" il KNN attuale sostituendolo
con un KNN2 basato sulla MaxDistance, perche' sarebbe
un modo soddisfacente per tutti per eliminare un
pasticcio di architettura.

ma per arrivarci dobbiamo necessariamente trasferire
questa nostra discussione sulla ML di spatialite; e
mi serve il vostro appoggio, perche' non sembri un
mio capriccetto personale.

vogliamo provarci ?

ciao Sandro

_______________________________________________
[hidden email]
http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
Questa e' una lista di discussione pubblica aperta a tutti.
I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.
764 iscritti al 23/08/2019

Maurizio Trevisani

Re: VirtualKNN e max_distance

Non sono in grado di valutare complessità e prestazioni, ma un parametro
max distanza mi sembra metta insieme sia la ricerca per vicinanza che una
intersezione spaziale con un buffer (appunto di max distanza) per scartare
risultati "troppo lontani".
Ma il vantaggio in termini di individuazione dei risultati desiderati va
considerato alla luce dello sforzo implementativo e se le prestazioni che
si ottengono risultino comparabili o migliori della combinazione di knn ed
intersection.

Un abbraccio,
Ciao,
Maurizio

Il dom 30 mag 2021, 00:01 <[hidden email]> ha scritto:

> On Sat, 29 May 2021 12:51:54 -0700 (MST), pigreco wrote:
> > Maurizio Trevisani wrote
> >> Devi scrivere sulla mailing list di spatialite.
> >> Ciao,
> >> Maurizio
> >
> > Buonasera,
> > ormai penso sia tardi, la mia idea è stata bocciata.
> >
> > le prossime volte scriverò in lista spatialite.
> >
>
> Toto' e Maurizio,
>
> non vorrei che la mia risposta precedente sia suonata
> troppo perentoria.
>
> se ritente che un KNN basato sul concetto di MaxDistance
> possa essere utile e' una cosa assolutamente praticabile,
> ma deve essere ben chiaro che non avra' nulla a che fare
> con il KNN attuale perche' sara' basata su criteri del
> tutto diversi. in altre parole, non sara' una modifica
> dell'attuale, ma una implementazione nuova di pacca a
> partire da zero.
>
> schematizzando per quanto possibile: il KNN attuale e'
> basato su una interfaccia molto speciale di SQLite che
> consente di traversare la struttura ad albero R*Tree
> a basso livello. non c'e' nessuno spazio per introdurre
> un concetto di MaxDistance, c'e' solo da esplorare
> tutti i rami dell'albero potenzilament interessanti,
> che e' un'oparazione che fornisce risultati perfetti
> ma che ovviamente richiede del tempo.
>
> quello che invece e' ipotizzabile e' un approccio
> radicalmente diverso, che lasci perdere le API ultra
> sofisticate di SQLite e che lavori internamente a
> forza di query SQL "normali" basate sullo SpatialIndex
> tradizionale. ed in questo caso il criterio della
> MaxDistance nota a priori diventa un requisito
> ineluttabile per ottenere una ragionevole velocita'
> di esecuzione.
>
> dal punto di vista dell'utente cambia poco (giusto
> un parametro in piu, la MaxDistance), ma dal punto
> di vista del codice cambia assolutamente tutto, non
> si salva neppure una riga dell'esistente.
>
> --------------------
>
> detto di striscio: il KNN sta causando diversi
> problemi agli utenti Java, Python, PHP e C#,
> specie su Windows.
>
> tutti questi linguaggi hanno dei connettori per
> SQLite che quasi sempre utilizzano la propria
> libsqlite3.dll privata interna che spesso e' di
> una versione differente da quella utilizzata
> da mod_spatialite, e magari e' stata compilata
> con opzioni differenti.
> una combinazione che non porta a nulla di buono
> in termini di stabilita' e compatibilita'.
>
> l'unica causa che scatena tutti questi conflitti
> e' proprio il KNN che dipende in modo critico dal
> supporto della libsqlite3. tutto funziona bene
> se la libsqlite3 utilizzata a runtime e' esattamente
> la stessa usata in compilazione (come accade p.es.
> per SpatialiteGUI e suppongo anche per QGIS),
> altrimenti si avranno sicuramente problemi piu'
> o meno seri.
>
> capite dunque che a me personalmente farebbe anche
> molto comodo "fare fuori" il KNN attuale sostituendolo
> con un KNN2 basato sulla MaxDistance, perche' sarebbe
> un modo soddisfacente per tutti per eliminare un
> pasticcio di architettura.
>
> ma per arrivarci dobbiamo necessariamente trasferire
> questa nostra discussione sulla ML di spatialite; e
> mi serve il vostro appoggio, perche' non sembri un
> mio capriccetto personale.
>
> vogliamo provarci ?
>
> ciao Sandro
>
>
>
>
> _______________________________________________
> [hidden email]
> http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
> Questa e' una lista di discussione pubblica aperta a tutti.
> I messaggi di questa lista non hanno relazione diretta con le posizioni
> dell'Associazione GFOSS.it.
> 764 iscritti al 23/08/2019