Re: [Gfoss] VirtualKNN in SpatiaLite 5

[a . furieri]

On Mon, 19 Apr 2021 12:37:29 -0700 (MST), pigreco wrote:

Altra sorpresona,
anche da me è velocissimo ma genera dati senza senso.



hai ragione, c'era una falla logica in qualle query;
occorre definire un buffer che "gonfi" il punto-incrocio,
altrimenti il filtro sullo spatial index prende in
considerazione solo quelle strade che casualmente
intersecano il BBOX del punto.

eccoti qua la versione riveduta e corretta:

CREATE TABLE wow AS
SELECT a.pk as fid, Min(ST_Distance(a.geom, zz.geom)) AS distance,
   zz.pk as pk_punti, st_shortestline (a.geom, zz.geom) as geom
FROM strade_palermo as a, inc2k18Palermo as zz
WHERE a.pk IN (
   SELECT rowid
   FROM SpatialIndex
   WHERE f_table_name = 'strade_palermo'
  AND search_frame = ST_Buffer(zz.geom, 0.01))
GROUP by zz.pk;

--

abbiamo cosi' introdotto due perditempo:
- la ST_ShortestLine
- la ST_Buffer
e comunque stiamo sempre sui 6-7 secondi.

N.B. il raggio del buffer e' fissato "a occhio"
(circa 1km), che almeno in questo caso pare
rappresentare un buon compromesso tra efficienza
e precisione dei risultati.

ecco dove sta il principale vantaggio dal KNN;
che non ti costringe mai a fare assunzioni piu'
o meno arbitrarie sui raggi di probabile distanza.

ciao Sandro.
___
Gfoss@lists.gfoss.it
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

Re: [Gfoss] VirtualKNN in SpatiaLite 5

[pigreco]

a.furieri wrote
> Sorpresona ... alla fine si scopre che il miglior tempo su
> SpatiaLite lo si ottiene usando l'approccio classicissimo
> lasciando perdere il KNN :-D
> 
> SELECT a.pk as fid, Min(ST_Distance(a.geom, zz.geom)) AS distance, 
> zz.pk as pk_punti
> FROM strade_palermo as a, inc2k18Palermo as zz
> WHERE a.pk IN (
>SELECT rowid
>FROM SpatialIndex
>WHERE f_table_name = 'strade_palermo' AND search_frame = zz.geom)
> GROUP by zz.pk;
> 
> chiude con un tempo superstellare di 0.409 secondi
> (si, avete letto bene: meno di mezzo secondo)

Altra sorpresona,
anche da me è velocissimo ma genera dati senza senso.

Per verificare graficamente ho generato questa tabella

CREATE TABLE wow AS
SELECT a.pk as fid, Min(ST_Distance(a.geom, zz.geom)) AS distance,zz.pk as
pk_punti,
 st_shortestline (a.geom, zz.geom) as geom
FROM strade_palermo as a, inc2k18Palermo as zz
WHERE a.pk IN (
   SELECT rowid
   FROM SpatialIndex
   WHERE f_table_name = 'strade_palermo' AND search_frame = zz.geom)
GROUP by zz.pk;

ma visualizzandola in QGIS, ecco cosa scopro:

 

MENTRE  sono corretti i risultati del VirtualKNN

saluti



-
https://pigrecoinfinito.wordpress.com/
--
Sent from: 
http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/
___
Gfoss@lists.gfoss.it
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

Re: [Gfoss] VirtualKNN in SpatiaLite 5

[a . furieri]

On Mon, 19 Apr 2021 19:36:25 +0200, Marco Curreli wrote:

On 19.04.21, a.furi...@lqt.it wrote:

On Mon, 19 Apr 2021 03:20:37 -0700 (MST), pigreco wrote:
>
> dati due tabelle, una con circa 3000 punti e un'altra con circa 
1

> linee
> (assi stradali); trovare, per ogni punto, l'asse stradale più 
vicino.


Con v.distance di GRASS è molto più veloce.



Sorpresona ... alla fine si scopre che il miglior tempo su
SpatiaLite lo si ottiene usando l'approccio classicissimo
lasciando perdere il KNN :-D

SELECT a.pk as fid, Min(ST_Distance(a.geom, zz.geom)) AS distance, 
zz.pk as pk_punti

FROM strade_palermo as a, inc2k18Palermo as zz
WHERE a.pk IN (
  SELECT rowid
  FROM SpatialIndex
  WHERE f_table_name = 'strade_palermo' AND search_frame = zz.geom)
GROUP by zz.pk;

chiude con un tempo superstellare di 0.409 secondi
(si, avete letto bene: meno di mezzo secondo)

conclusione: il KNN e' un metodo sofisticato basato sulle API
"advanced" di SQLite che consentono l'introspezione degli R*Tree.
nulla assicura che sia il metodo in grado di dare i risultati
migliori in assoluto.

sarebbe casomai interessante indagare come evolvono i tempi
quando si passa di risolvere problemi piu' complessi (tipo
svariati milioni di righe e di punti) ... magari nella
prossima vita, quando magari avremo piu' tempo libero
per divertici a fare benchmarking ;-)

ciao Sandro

___
Gfoss@lists.gfoss.it
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

Re: [Gfoss] VirtualKNN in SpatiaLite 5

[Marco Curreli]

On 19.04.21, a.furi...@lqt.it wrote:
> On Mon, 19 Apr 2021 03:20:37 -0700 (MST), pigreco wrote:
> > 
> > dati due tabelle, una con circa 3000 punti e un'altra con circa 1
> > linee
> > (assi stradali); trovare, per ogni punto, l'asse stradale più vicino.

Con v.distance di GRASS è molto più veloce.

Saluti,
   Marco 
___
Gfoss@lists.gfoss.it
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

Re: [Gfoss] VirtualKNN in SpatiaLite 5

[Totò Fiandaca]

Ciao Andrea,
con le nuove funzioni introdotte in QGIS 3.16 [0] e con lo stesso laptop
impiego 14 sec

[0] https://github.com/qgis/QGIS/pull/38405

saluti

Il giorno lun 19 apr 2021 alle ore 16:44 aborruso  ha
scritto:

> Ciao Totò,
> una curiosità off-topic: con le tue amate funzioni di QGIS, quanto dura lo
> stesso processo?
>
> Grazie
>
> -
> Andrea Borruso
>
> 
> twitter: https://twitter.com/aborruso
> website: https://medium.com/tantotanto
> 38° 7' 48" N, 13° 21' 9" E
> 
> --
> Sent from:
> http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/
> ___
> Gfoss@lists.gfoss.it
> 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



-- 
*Ing. Salvatore Fiandaca*
*mobile*.:+39 327.493.8955
*m*: *pigrecoinfin...@gmail.com *
*C.F*.: FNDSVT71E29Z103G
*P.IVA*: 06597870820
*membro QGIS Italia - http://qgis.it/ *
*socio GFOSS.it - *http://gfoss.it/
*blog:*
* https://pigrecoinfinito.com/  FB: Co-admin
- https://www.facebook.com/qgis.it/ **
 *
*TW:  **https://twitter.com/totofiandaca
*

43°51'0.54"N  10°34'27.62"E - EPSG:4326

“Se la conoscenza deve essere aperta a tutti,
perchè mai limitarne l’accesso?”
R. Stallman

Questo documento, allegati inclusi, contiene informazioni di proprietà di
FIANDACA SALVATORE e deve essere utilizzato esclusivamente dal destinatario
in relazione alle finalità per le quali è stato ricevuto. E' vietata
qualsiasi forma di riproduzione o divulgazione senza l'esplicito consenso
di FIANDACA SALVATORE. Qualora fosse stato ricevuto per errore si prega di
informare tempestivamente il mittente e distruggere la copia in proprio
possesso.
___
Gfoss@lists.gfoss.it
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

Re: [Gfoss] VirtualKNN in SpatiaLite 5

[aborruso]

Ciao Totò,
una curiosità off-topic: con le tue amate funzioni di QGIS, quanto dura lo
stesso processo?

Grazie

-
Andrea Borruso


twitter: https://twitter.com/aborruso
website: https://medium.com/tantotanto
38° 7' 48" N, 13° 21' 9" E

--
Sent from: 
http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/
___
Gfoss@lists.gfoss.it
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

Re: [Gfoss] VirtualKNN in SpatiaLite 5

[Totò Fiandaca]

Grazie per la rapida risposta,
il mio laptop è del 2015 (Processore AMD FX-7500 Radeon R7, 10 Compute
Cores 4C+6G, 2100 Mhz, 4 core, 4 processori logici; 8 GB RAM e SSD) con win
10.

Non trovo quasi nessuna differenza in termini di tempo tra le due query
soluzioni proposte,  strano!

Grazie per avermi dato fiducia sull'uso dei VirtualKNN e per la nota
metodologia.

saluti



Il giorno lun 19 apr 2021 alle ore 14:04  ha scritto:

> On Mon, 19 Apr 2021 03:20:37 -0700 (MST), pigreco wrote:
> > Buongiorno a tutte/i
> > ho usato in passato i VirtualKNN di SpatiaLite soprattutto nei
> > trigger, ma
> > ora volevo usarlo per risolvere il seguente quesito:
> >
> > dati due tabelle, una con circa 3000 punti e un'altra con circa 1
> > linee
> > (assi stradali); trovare, per ogni punto, l'asse stradale più vicino.
> >
> > Per risolvere questo problema ho pensato di usare spatialite 5 e la
> > tabella
> > KNN.
> >
> > Ho importato i due vettori in un geodatabase sqlite (creato con QGIS
> > 3.19
> > master, che ha implementato spatialite 5.0.1)  e ho lanciato la
> > seguente
> > query:
> >
> > SELECT a.fid as pk_strade, a.distance as distance, zz.pk as pk_punti
> >   FROM knn as a
> >   JOIN
> >   inc2k18Palermo as zz
> >   WHERE f_table_name = 'strade_palermo'
> >   AND f_geometry_column = 'geom'
> >   AND ref_geometry = zz.geom
> >   AND max_items = 1
> >
> > la query restituisce un output e quindi creo la relativa tabella
> > (create
> > table as ..), ma impiega circa 200 secondi (sia da db manager di QGIS
> > che da
> > spatialite_gui 2.1.0 beta 1);
> >
>
> che ci impieghi sempre lo stesso tempo e' normale; il lavoro duro lo
> fa esclusivamente libspatialite, che venga incapsulata dentro a QGIS
> oppure dentro alla GUI e' assolutamente irrilevante.
>
> i tempi che riporti non mi tornano con quanto verifico sul mio PC;
> qua da me ci mette poco piu' di 1 minuto (60-70 secondi), che e'
> un valore abbastanza differente dal tuo.
>
> possibile spiegazione: il tuo HW e' molto piu' lento del mio.
> giusto per curiosita', io uso una workstation con un Intel i7
> che ha 8 cores fisici da 3.0 GHz, 32 GB RAM e un SSD.
>
>
> > volevo chiedere se faccio un uso corretto dei virtualKNN oppure ho
> > scritto
> > male la query?
> >
>
> si puo' scrivere meglio invertendo l'ordine delle tavole.
>
> SELECT a.fid as pk_strade, a.distance as distance, zz.pk as pk_punti
> FROM inc2k18Palermo as zz
> JOIN knn as a ON (f_table_name = 'strade_palermo'
>  AND f_geometry_column = 'geom'
>  AND ref_geometry = zz.geom
>  AND max_items = 1)
>
> riscritta in questa seconda forma gira in 45-50 secondi;
> la differenza non e' abissale, ma con un problema simile
> ma con maggiori dimensioni potrebbe facilmente diventare
> molto piu' consistente.
>
> nota metodologica:
> ==
> il query oprimizer di SQLite non e' particolarmente sofisticato;
> molto spesso indovina la strategia ottimale di accesso ai dati,
> ma qualche volta imbocca la strada sbagliata.
> capita soprattutto quando ci sono di mezzo le VirtualTables,
> che per SQLite sono "oggetti buffi" dal comportamento non
> predicibile, ed ai quali viene sempre assegnata la minima
> priorita' possibile.
>
> visto che sia lo SpatialIndex che il KNN sono proprio basati
> sulle VirtualTable di tipo R*Tree, occorre sempre stare
> attenti a come si scrivono le query SQL, perche' potrebbe
> avere un notevole impatto sui tempi di esecuzione.
>
> le seconda forma toglie il query optimizer dall'imbarazzo,
> perche' diventa chiarissimo che la sequenza attesa e':
> 1. pescati una riga dagli incroci
> 2. e poi vatti a cercare via KNN la geometria piu' vicina.
>
> regola empirica a braccio: ogni volta che hai il sospetto
> che una query basata su R*Tree giri lenta prova sempre a
> riscrivere la tua query "rovesciata".
>
> ciao Sandro
> ___
> Gfoss@lists.gfoss.it
> 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



-- 
*Ing. Salvatore Fiandaca*
*mobile*.:+39 327.493.8955
*m*: *pigrecoinfin...@gmail.com *
*C.F*.: FNDSVT71E29Z103G
*P.IVA*: 06597870820
*membro QGIS Italia - http://qgis.it/ *
*socio GFOSS.it - *http://gfoss.it/
*blog:*
* https://pigrecoinfinito.com/  FB: Co-admin
- https://www.facebook.com/qgis.it/ **
 *
*TW:  **https://twitter.com/totofiandaca
*

43°51'0.54"N  10°34'27.62"E - EPSG:4326

“Se la conoscenza deve essere aperta a tutti,
perchè mai limitarne l’accesso?”
R. Stallman

Questo documento, allegati inclusi, contiene informazioni di proprietà di
FIANDACA SALVATORE e deve essere 

Re: [Gfoss] VirtualKNN in SpatiaLite 5

[a . furieri]

On Mon, 19 Apr 2021 03:20:37 -0700 (MST), pigreco wrote:

Buongiorno a tutte/i
ho usato in passato i VirtualKNN di SpatiaLite soprattutto nei 
trigger, ma

ora volevo usarlo per risolvere il seguente quesito:

dati due tabelle, una con circa 3000 punti e un'altra con circa 1 
linee

(assi stradali); trovare, per ogni punto, l'asse stradale più vicino.

Per risolvere questo problema ho pensato di usare spatialite 5 e la 
tabella

KNN.

Ho importato i due vettori in un geodatabase sqlite (creato con QGIS 
3.19
master, che ha implementato spatialite 5.0.1)  e ho lanciato la 
seguente

query:

SELECT a.fid as pk_strade, a.distance as distance, zz.pk as pk_punti
FROM knn as a
JOIN
inc2k18Palermo as zz
WHERE f_table_name = 'strade_palermo'
AND f_geometry_column = 'geom'
AND ref_geometry = zz.geom
AND max_items = 1

la query restituisce un output e quindi creo la relativa tabella 
(create
table as ..), ma impiega circa 200 secondi (sia da db manager di QGIS 
che da

spatialite_gui 2.1.0 beta 1);



che ci impieghi sempre lo stesso tempo e' normale; il lavoro duro lo
fa esclusivamente libspatialite, che venga incapsulata dentro a QGIS
oppure dentro alla GUI e' assolutamente irrilevante.

i tempi che riporti non mi tornano con quanto verifico sul mio PC;
qua da me ci mette poco piu' di 1 minuto (60-70 secondi), che e'
un valore abbastanza differente dal tuo.

possibile spiegazione: il tuo HW e' molto piu' lento del mio.
giusto per curiosita', io uso una workstation con un Intel i7
che ha 8 cores fisici da 3.0 GHz, 32 GB RAM e un SSD.


volevo chiedere se faccio un uso corretto dei virtualKNN oppure ho 
scritto

male la query?



si puo' scrivere meglio invertendo l'ordine delle tavole.

SELECT a.fid as pk_strade, a.distance as distance, zz.pk as pk_punti
FROM inc2k18Palermo as zz
JOIN knn as a ON (f_table_name = 'strade_palermo'
 AND f_geometry_column = 'geom'
 AND ref_geometry = zz.geom
 AND max_items = 1)

riscritta in questa seconda forma gira in 45-50 secondi;
la differenza non e' abissale, ma con un problema simile
ma con maggiori dimensioni potrebbe facilmente diventare
molto piu' consistente.

nota metodologica:
==
il query oprimizer di SQLite non e' particolarmente sofisticato;
molto spesso indovina la strategia ottimale di accesso ai dati,
ma qualche volta imbocca la strada sbagliata.
capita soprattutto quando ci sono di mezzo le VirtualTables,
che per SQLite sono "oggetti buffi" dal comportamento non
predicibile, ed ai quali viene sempre assegnata la minima
priorita' possibile.

visto che sia lo SpatialIndex che il KNN sono proprio basati
sulle VirtualTable di tipo R*Tree, occorre sempre stare
attenti a come si scrivono le query SQL, perche' potrebbe
avere un notevole impatto sui tempi di esecuzione.

le seconda forma toglie il query optimizer dall'imbarazzo,
perche' diventa chiarissimo che la sequenza attesa e':
1. pescati una riga dagli incroci
2. e poi vatti a cercare via KNN la geometria piu' vicina.

regola empirica a braccio: ogni volta che hai il sospetto
che una query basata su R*Tree giri lenta prova sempre a
riscrivere la tua query "rovesciata".

ciao Sandro
___
Gfoss@lists.gfoss.it
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

[Gfoss] VirtualKNN in SpatiaLite 5

[pigreco]

Buongiorno a tutte/i
ho usato in passato i VirtualKNN di SpatiaLite soprattutto nei trigger, ma
ora volevo usarlo per risolvere il seguente quesito:

dati due tabelle, una con circa 3000 punti e un'altra con circa 1 linee
(assi stradali); trovare, per ogni punto, l'asse stradale più vicino.

Per risolvere questo problema ho pensato di usare spatialite 5 e la tabella
KNN.

Ho importato i due vettori in un geodatabase sqlite (creato con QGIS 3.19
master, che ha implementato spatialite 5.0.1)  e ho lanciato la seguente
query:

SELECT a.fid as pk_strade, a.distance as distance, zz.pk as pk_punti
FROM knn as a 
JOIN 
inc2k18Palermo as zz 
WHERE f_table_name = 'strade_palermo' 
AND f_geometry_column = 'geom' 
AND ref_geometry = zz.geom 
AND max_items = 1 

la query restituisce un output e quindi creo la relativa tabella (create
table as ..), ma impiega circa 200 secondi (sia da db manager di QGIS che da
spatialite_gui 2.1.0 beta 1);

volevo chiedere se faccio un uso corretto dei virtualKNN oppure ho scritto
male la query?

ho letto e approfondito i virtualKNN da qui [0] dove gli esempi sono
relativi a singola ricerca e non a un intero dataset come nel mio caso.

allego db sqlite.

https://drive.google.com/file/d/1wi1VJgzgB3tKSePyRkaJc45fdAw6d2wM/view?usp=sharing

[0] https://www.gaia-gis.it/fossil/libspatialite/wiki?name=KNN

saluti


-
https://pigrecoinfinito.wordpress.com/
--
Sent from: 
http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/
___
Gfoss@lists.gfoss.it
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