[Gfoss] VirtualKNN e max_distance

Local Chapters GFOSS.it
1

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] SpatiaLite: KNN

-----

--
Sent from: http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/

2

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.

3

a.furieri wrote

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

Non occorre scusarsi, la mia è una deformazione dovuta all'uso di QGIS.
Nella QGIS 3.16 Hannover sono state introdotte delle nuove funzioni, una di
questa è 'overlay_nearest' [0] che fa (quasi) le stesse cose della
virtualKNN e ha il parametro max_distance.

grazie mille per la risposta rapida e ricca di indicazioni.

[0]
https://docs.qgis.org/3.16/en/docs/user_manual/working_with_vector/functions_list.html#overlay-nearest

-----
https://pigrecoinfinito.wordpress.com/
--
Sent from: http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/

4

Si, credo che tu abbia ragione.

Il sab 29 mag 2021, 16:11 pigreco <pigrecoinfinito@gmail.com> 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/
_______________________________________________
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

5

Devi scrivere sulla mailing list di spatialite.
Ciao,
Maurizio

Il sab 29 mag 2021, 16:11 pigreco <pigrecoinfinito@gmail.com> 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/
_______________________________________________
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

6

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.

grazie

-----
https://pigrecoinfinito.wordpress.com/
--
Sent from: http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/

7

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

8

a.furieri wrote

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 ?

Buongiorno,
per me va bene.

Se siete d'accordo scrivo lo stesso oggetto e testo della mail nel gruppo
spatialite internazionale.

grazie

saluti

-----
https://pigrecoinfinito.wordpress.com/
--
Sent from: http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/

9

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 <a.furieri@lqt.it> 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

_______________________________________________
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

10

a.furieri wrote

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

Fatto,

https://groups.google.com/g/spatialite-users/c/kLG4LQGbGKs

grazie per tutto, anche se non andasse in porto :slight_smile:

-----
https://pigrecoinfinito.wordpress.com/
--
Sent from: http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/