6

Can you do k-nearest neighbors algorithm (k-NN) queries on MySQL for example, to find the nearest point in PostgreSQL with PostGIS, I can run a kNN query on the spatial index with <->

SELECT ST_AsText(geom), city
FROM person.address
ORDER BY geom <-> 'POINT(-121.626 47.8315)'
FETCH FIRST 7 ROWS ONLY;

SQL Server has a similar method,

DECLARE @g geography = 'POINT(-121.626 47.8315)';

SELECT TOP(7) SpatialLocation.ToString(), City
FROM Person.Address  
WHERE SpatialLocation.STDistance(@g) IS NOT NULL  
ORDER BY SpatialLocation.STDistance(@g);

Both PostgreSQL and SQL Server have KNN. What is the MySQL equivalent of <-> to do KNN on their spatial index?


If you don't know what KNN is, you can see a description of it here

The KNN system works by evaluating distances between bounding boxes inside the PostGIS R-Tree index.

Because the index is built using the bounding boxes of geometries, the distances between any geometries that are not points will be inexact: they will be the distances between the bounding boxes of geometries.

The kicker here is that the KNN approach,

  1. Does not require you to confine the query to a distance with a WHERE clause
  2. Does not calculate all of the distances between all of the points
  3. Can find the nearest point on the index.

This question is specifically about the method in which the job gets done. I realize I can get the same result, with substantially more work by calculating the distance from each point to every other point*, then ORDERing, and LIMITing.

0

1 Answer 1

3

In short, neither MySQL or MariaDB do. They do use R-Trees so it doesn't sound impossible to implement. I haven't seen this feature request in either of their bug trackers.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.