<table cellspacing="12" width="100%">
<tr><td colspan="2">
<table width="100%" bgcolor="#f0f0f8">
<tr><td align="center">
<h1>VirtualKNN: a quick intro</h1>

<table width="100%"><tr>
<td width="33%" align="left"></td>
<td align="center"><a to
<td width="33%" align="right"></td>

<table bgcolor="#d0e0ff" width="100%">
<tr><td align="center">
<b>Credits</b><br>
Development of has been entirely funded by
<a Region</a> - Territorial and Environmental Information System<br>
<a Toscana</a> - Settore Sistema Informativo Territoriale ed Ambientale.

<hr><br>
<table width="100%" bgcolor="#ffffdf" cellspacing="4" cellpadding="8">
<tr><td><b>What is the KNN (<i>K-Nearest Neighbors</i>) problem
<tr><td>Imagine a set of arbitrary geometries; which may well be, a very huge dataset containing some millions of features.<br>
Now imagine that for for whatever reason you are interested in quickly identifying all features within a  close spatial proximity to an arbitrary location.<br>
This is the typical <b>KNN</b>
<tr><td>Just few practical real world examples:
<ul>
<li>Suppose while using a smartphone app: your current geographic location is well known by the integrated GPS sensor, so you are simply expecting that the app will immediately tell where you are (and the exact location of) the nearest fuel stations (hotels, restaurants etc).</li>
<li>Suppose a zoological/ecological study: you know where are located the nesting areas of some rare water bird species, also the location of all rivers, lakes, ponds and marshlands in the area you are interested in.<br>
Now you are attempting to get a reasonable association between nesting areas and feeding zones based on minimal distance criteria.</li>
</ul>

<tr><td>Whereby, in both cases you can't safely identify a reasonable <i><u>minimal so to usefully restrict your search by, since you can't make any valid assumption about the geographic dispersion of your targets.<br>
The distances may noticeably vary from case to case, and you haven't any idea about this, since it strictly depends on the actual location of the search origin and on the statistical dispersion of the targets to be
</table><br>
<hr><br>
<table width="100%">
<tr><td valign="middle">
You can <a a sample db-file exactly corresponding to the practical examples we'll use in this first tutorial.<br><br>
This dataset corresponds to a collection of about <b>30.000 airports</b> scattered all over the world; the original input shapefile was downloaded from <a
The reference system is <b>4326 WGS84</b> (based on <i>longitude</i> and <i>latitude</i> angles).
<br><br><br><br>
The map on the right shows the geographic context of this first KNN example.</td>
<td><img alt="Tyrrhenian Sea"></td>
</table><br>
<h2>A first, simple and very inefficient, approach</h2>
<verbatim>
SELECT geonameid, name, country,
    Min(ST_Distance(MakePoint(10, 43), geom, 1)) / 1000.0 AS dist_km
FROM airports;
--------------------------------
6299623	| Marina Di Campo | IT | 33.043320

SELECT geonameid, name, country,
    Min(ST_Distance(MakePoint(10, 43), geom, 1)) / 1000.0 AS dist_km
FROM airports
WHERE geonameid NOT IN (6299623);
---------------------------------
6299392 | Bastia-Poretta | FR | 65.226573

SELECT geonameid, name, country,
    Min(ST_Distance(MakePoint(10, 43), geom, 1)) / 1000.0 AS dist_km
FROM airports
WHERE geonameid NOT IN (6299623, 6299392);
---------------------------------
6299628 | Pisa / S. Giusto | IT	| 82.387014

SELECT geonameid, name, country,
    Min(ST_Distance(MakePoint(10, 43), geom, 1)) / 1000.0 AS dist_km
FROM airports
WHERE geonameid NOT IN (6299623, 6299392, 6299628);
---------------------------------
6299630 | Grosseto Airport | IT | 91.549773

SELECT geonameid, name, country,
    Min(ST_Distance(MakePoint(10, 43), geom, 1)) / 1000.0 AS dist_km
FROM airports
WHERE geonameid NOT IN (6299623, 6299392, 6299628, 6299630);
---------------------------------
6694495 | Corte | FR | 102.819778
</verbatim>
We could effectively execute a first SQL query using the <b>Min()</b> aggregate function in order to identify the closest airport to an arbitrary position located in the middle of the Tyrrhenian Sea.<br>
Then we could eventually repeatably execute the identical query, each time excluding all airports we've already identified in the previous processed steps.<br>
The final result will be the full list of the first five airports closest to the reference location ordered by increasing distance.
<br><br>
<table bgcolor="#d0ffb0" cellspacing="4" cellpadding="4" border="1">
<tr><td
<tr><td align="right">1</td><td align="right">6299623</td><td>Marina Di
<tr><td align="right">2</td><td
<tr><td align="right">3</td><td align="right">6299628</td><td>Pisa / S.
<tr><td align="right">4</td><td align="right">6299630</td><td>Grosseto
<tr><td align="right">5</td><td
</table><br>
Such a simple approach would be highly impractical, because it strictly requires to hand-write several <i>ad hoc</i> SQL queries one by one.<br>
Writing a fully automated SQL script isn't at all a simple task, and some kind of higher level scripting (e.g. Python) would be easily required in any realistic scenario.<br>
The automation of all required SQL queries isn't the most critical issue we have to face; the real, critical, bottle neck with this simple approach, is that each of these queries will cause an awful <a table scan</a><br>
This will be the cause of an intolerably sluggish performance, and the overall performance will quickly become worse as the dataset progressively increases in size.
<br><br>
<b>Conclusion</b>:<br>
Some easier and smarter approach is surely required: possibly one taking full profit from an <b>R*TRee Spatial Index</b> supporting the Geometries to be searched.<br><br>
<hr>
<h2>VirtualKNN</h2>
Starting since version <b>4.4.0</b> SpatiaLite supports a <b>VirtualKNN</b> <a Table</a> specifically intended as a complete and highly efficient solution to the <b>KNN</b> problem.
<verbatim>
CREATE VIRTUAL TABLE knn USING VirtualKNN();
</verbatim>
Every new db-file being created by <b>4.4.0</b> itself will always automatically define a <b>KNN</b> virtual table.<br>
You could eventually add full KNN support to any db-file created by any earlier version of SpatiaLite by manually executing the above SQL statement.<br>
<b>Note</b>: VirtualKNN necessarily requires 4.4.0 binary support, so any attempt to open a db-file including a VirtualKNN table by using some previous version (<= <b>4.3.0a</b>) will surely raise an error condition.
<h3>A first basically simple KNN query</h3>
<verbatim>
SELECT * FROM knn
WHERE f_table_name = 'airports' AND ref_geometry = MakePoint(10, 43);
</verbatim>
<table bgcolor="#d0ffb0" cellspacing="4" cellpadding="4" border="1">
<tr><td
sz=60 GEOMETRY</td><td align="right">3</td><td align="right">1</td><td align="right">6299623</td><td
sz=60 GEOMETRY</td><td align="right">3</td><td align="right">2</td><td align="right">6299392</td><td
sz=60 GEOMETRY</td><td align="right">3</td><td align="right">3</td><td align="right">6299628</td><td
</table><br>
<ul>
<li>a VirtualKNN query closely resembles a VirtualSpatialIndex query.
This is not surprising, since both of them are intended to be wrapped around an underlying <b>R*Tree Spatial
<li>Any valid VirtualKNN query must use a form such as:
<b>WHERE <i>knn-column</i> = <i>value</i> AND <i>knn-column</i> = <i>value</i>
<li>the input columns (the ones you can reference into a <b>WHERE</b> clause) are:
<ul>
<li><b>f_table_name</b> (<i>mandatory</i>)<br>
name of the GeoTable containing the Geometries to be searched.</li>
<li><b>f_geometry_column</b> (<i>optional</i>)<br>
name of the column of the above table containing the Geometries to be searched.
<ol>
<li>If the table identified by <b>f_table_name</b> just contains a single Geometry column you can safely omit the <b>f_geometry_column</b> argument (it will be automatically set).</li>
<li>If, however, the table identified by <b>f_table_name</b> contains two (or more) Geometry columns explicitly specifying the <b>f_geometry_column</b> argument is strictly required, so to get an unambiguous definition of the intended search context.</li>
<li>In both cases <b>f_table_name</b> and <b>f_geometry_column</b> must exactly match a properly defined Geometry column supported by a corresponding Spatial Index.</li>

<li><b>ref_geometry</b> (<i>mandatory</i>)<br>
any arbitrary Geometry (<b>POINT</b>, <b>LINESTRING</b>, <b>POLYGON</b> or whatever else) intended to represent the origin of the KNN search.<br>
Should necessarily be in the same SRID of the target Geometries to be searched.</li>
<li><b>max_items</b> (<i>optional</i>)<br>
maximum number of rows to be returned into the resultset.<br>
The valid range is from <b>1</b> to <b>1024</b> (higher values will require a longer time to be processed).<br>
By default only the first <b>3</b> nearest Geometries will be identified.</li>

<li>the output columns (the ones containing values retrieved by the KNN search) are:
<ul>
<li><b>pos</b> (<i>INTEGER</i>)<br>
relative rank (sorted by distance): the closest item will be <b>#1</b>, the second closest item will be <b>#2</b> and so on.</li>
<li><b>fid</b> (<i>INTEGER</i>)<br>
the unique <b>ROWID</b> value of the corresponding feature into the searched GeoTable.</li>
<li><b>distance</b> (<i>DOUBLE</i>)<br>
the minimum distance between the corresponding feature into the searched GeoTable and the origin defined by <b>ref_geometry</b>.
<ol>
<li>When the defined SRID uses a <b>planar<b> (aka <i>projected<i>) reference system, all distances will be returned in the units defined by the projection (meters, feet, chains etc.).</li>
<li>When using a <b>geographic</b> type (<i>longitude</i> and <i>latitude</i> <b>degrees</b>), all distances will always be measured in <b>meters</b>, and the most precise geodetic formulas will be automatically applied.</li>


</ul><br>
<hr>
<h3>A second example of a more sophisticated KNN query</h3>
<verbatim>
SELECT a.pos, b.name, b.country, a.distance / 1000.0 AS dist_km
FROM knn AS a
JOIN airports AS b ON (b.geonameid = a.fid)
WHERE f_table_name = 'airports' AND ref_geometry = MakePoint(10, 43) AND max_items = 5;
</verbatim>
<table bgcolor="#d0ffb0" cellspacing="4" cellpadding="4" border="1">
<tr><td
<tr><td align="right">1</td><td align="right">6299623</td><td>Marina Di
<tr><td align="right">2</td><td
<tr><td align="right">3</td><td align="right">6299628</td><td>Pisa / S.
<tr><td align="right">4</td><td align="right">6299630</td><td>Grosseto
<tr><td align="right">5</td><td
</table><br>
This second KNN query will return the same identical results we already got before by using the silly naive approach.<br>
The striking difference is that this KNN query successfully completed in just a fraction of a second, whilst executing the first inefficient queries required many seconds (and please consider that this one is a relatively small dataset).<br><br>
<b>Summary</b>: KNN queries are really efficient and fast, because they directly interact with the lowermost levels of the R*Tree Spatial Index implementation.<br><br>
<hr>
<h3>A third sample of KNN query</h3>
<verbatim>
SELECT a.pos AS rank, b.geonameid, b.name, b.country, a.distance / 1000.0 AS dist_km
FROM knn AS a
JOIN airports AS b ON (b.geonameid = a.fid)
WHERE f_table_name = 'airports' AND ref_geometry = MakePoint(-17.3, -44) AND max_items = 5;
</verbatim>
<table bgcolor="#d0ffb0" cellspacing="4" cellpadding="4" border="1">
<tr><td
<tr><td align="right">1</td><td align="right">7668433</td><td>Cabo Frio
<tr><td align="right">2</td><td
<tr><td align="right">3</td><td align="right">7730153</td><td>Umberto Modiano
<tr><td align="right">4</td><td align="right">3362355</td><td>Robben
<tr><td align="right">5</td><td align="right">6300622</td><td>S. P. Aldeia
</table><br>
This last KNN query is very similar to the previous one.<br>
This time we've placed the origin location somewhere in the South Atlantic blue deep waters (more or less midway from both Brazil and South Africa) and consequently the nearest airports are not really so near, because they are located many thousands Km away.
As you can easily check by yourself a KNN query will brilliantly perform even under such unusual conditions.<br><br>
<img alt="South Atlantic"><br><br>
<b>Summary</b>: KNN queries never assume any predefined distribution of the searched items, and will extract the correct results (sorted by distance), despite a very irregular sample distribution.<br><br>
<hr>
<h2>Advanced tutorial</h2>
You can <a a sample db-file exactly corresponding to the practical examples we'll use in this advanced tutorial.<br><br>
This is a much more demanding dataset corresponding to a collection of about <b>2.4 million house numbers</b>.<br>
The original input shapefile was downloaded from <a Region</a> (<b><i>Grafo Stradale and was subsequently rearranged into a more convenient form.<br>
The dataset is released under the <b>CC-BY-SA 4.0</b> license terms.<br>
The reference system is <b>3003 Monte Mario / Italy zone 1</b>; this is a <b>planar</b> (<i>projected</i>) reference system measured in <b>meters</b>.
<br>
<verbatim>
SELECT a.pos AS rank, a.fid AS fid, a.distance AS dist_m, d.prov AS province,
       d.nome AS municipality, c.toponimo AS street_name, b.civico AS house_num,
       b.geom AS geom
FROM knn AS a
JOIN civici AS b ON (b.rowid = a.fid)
JOIN toponimi AS c ON (c.fid = b.id_toponimo)
JOIN comuni AS d ON (d.fid = c.id_comune)
WHERE a.f_table_name = 'civici' AND a.ref_geometry = MakePoint(1733003, 4816332, 3003) AND a.max_items = 10;

SELECT a.pos AS rank, a.fid AS fid, a.distance AS dist_m, b.prov AS province,
       b.comune AS municipality, b.toponimo AS street_name, b.civico AS house_num,
       b.geom AS geom
FROM knn AS a
JOIN vw_civici AS b ON (b.rowid = a.fid)
WHERE a.f_table_name = 'vw_civici' AND a.ref_geometry = MakePoint(1733003, 4816332, 3003) AND a.max_items = 10;
</verbatim>
The following map corresponds to the above queries: the origin point is positioned on a road junction in the central area of a densely populated town (Arezzo).<br>
Not surprisingly the ten nearest house numbers have been located within a radius of about 10m.<br><br>
<img alt="House Numbers #1">
<br><br>
Both queries will return the same identical results.<br>
A closer look will show you that the second query is based on a <b>Spatial View</b><br><br>
<b>Summary</b>: a VirtualKNN query can indifferently target either a GeoTable or a properly registered Spatial View.<br><br>
<verbatim>
SELECT a.pos AS rank, a.fid AS fid, a.distance AS dist_m, b.prov AS province,
       b.comune AS municipality, b.toponimo AS street_name, b.civico AS house_num,
       b.geom AS geom
FROM knn AS a
JOIN vw_civici AS b ON (b.rowid = a.fid)
WHERE a.f_table_name = 'civici' AND a.ref_geometry = MakePoint(1595625, 4767420, 3003) AND max_items = 20;
</verbatim>
The following map corresponds to the above query. Now the origin point is positioned in the Tyrrhenian Sea, about <b>26 km</b> from the Tuscany mainland, the Islands of Elba and Capraia.<br>
Here too VirtualKNN is capable to identify the nearest house numbers in just a fraction of a second.<br><br>
<img alt="House Numbers #2"><br><br>
<b>Summary</b>:  VirtualKNN is highly efficient and very fast. Even when querying such a huge dataset, while exploring the most contrasting (very high / low density) data distributions .<br><br>
<table width="100%"><tr>
<td width="33%" align="left"></td>
<td align="center"><a to
<td width="33%" align="right"></td>