Finding nearest neighbors between two tables with point locations in SpatiaLite?

Question

I have started playing with SpatiaLite today and already stumbled upon a problem.

For each point location stored in tableOne I would like to select one, nearest (linear distance) point from tableTwo.

So far I came up with a clumsy solution that utilizes VIEW:

CREATE VIEW testview AS 
SELECT 
A.id , 
B.myValue, 
Distance(A.Geometry, B.Geometry) AS distance
FROM tableOne AS A, tableTwo AS B
WHERE distance < 10000
ORDER BY A.Id, distance;

And then:

SELECT * FROM testview
WHERE distance = (SELECT MIN(distance) FROM testview AS t WHERE t.id = testview.id)

seems to do the job.

Two questions:

Is there a way to perform such query without creating a VIEW?

Is there any other way to optimize this query for better performance? In a real world scenario tableOne will have hundreds-couple thousands records, and tableTwo - 1.3 million.

Answer 1

I have just tested this SQL and it works:

SELECT g1.OGC_FID As id1, g2.OGC_FID As id2, MIN(ST_Distance(g1.GEOMETRY,g2.GEOMETRY)) AS DIST
FROM table_01 As g1, table_02 As g2   
WHERE g1.OGC_FID <> g2.OGC_FID
AND ST_Contains(ST_Expand(g1.geometry,50),g2.geometry)
GROUP BY id1
ORDER BY id1

As you can read here "The naive way to carry out a nearest neighbour query is to order the candidate table by distance from the query geometry, and then take the record with the smallest distance".

Best regards,

Andrea

Answer 2

If you don't want to compute the distances between all the point combinations, you can use a spatial index on one of the table :

SELECT 
  A.id , 
  B.myValue, 
  MIN(Distance(A.Geometry, B.Geometry)) AS distance
FROM tableOne AS A, tableTwo AS B
WHERE A.ROWID IN (
  SELECT ROWID
  FROM SpatialIndex WHERE
    f_table_name = 'A' 
    AND search_frame = BuildCircleMbr(ST_X(B.Geometry), ST_Y(B.Geometry), 10000))
GROUP BY A.id, B.myValue

Answer 3

Since version 4.4.0 SpatiaLite supports a KNN virtual table index for nearest neighbor problems. Here is a query the finds the nearest line in a linestring table to each point in a point table.

SELECT k.* FROM knn k, points p
WHERE f_table_name = 'linestrings' 
AND ref_geometry = p.geometry
AND max_items = 1;

Answer 4

You can simplify your query like this.

SELECT 
   A.id , 
   B.myValue, 
   MIN(Distance(A.Geometry, B.Geometry)) AS distance
FROM tableOne AS A, tableTwo AS B
GROUP BY A.id, B.myValue

For a more generic solution, it might be worth trying to convert this PostGIS Nearest Neighbor function: http://blog.mackerron.com/2011/03/postgis-nearest-neighbour/