CODEWITHSUNDEEP
sql-serverspatialnearest-neighbor
Pure.Krome
Pure.Krome

Reputation: 86957

How to calculate the "Nearest Neighbour" for multiple sources in SQL Server?

The "Nearest Neighbour" problem is very common when working with spatial data.

There's even some nice, simple documentation about how to do it with MS Sql Server in their docs!

I'm usually seeing examples where it's using 1x source Lat/Long and it returns the 'x' number of nearest neighbour Lat/Longs. Fine...

e.g.

USE AdventureWorks2012  
GO  
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);

In my case, I have multiple Lat/Long sources ... and for each source, need to return the 'x' number of nearest neighbours.

Here's my schema

Table: SomeGeogBoundaries
LocationId INTEGER PRIMARY KEY (it's not an identity, but a PK & FK)
CentrePoint GEOGRAPHY

Index:
Spatial Index on CentrePoint column. [Geography || MEDIUM, MEDIUM, HIGH, HIGH]

Sample data:

LocationId | CP Lat/Long
1          | 10,10
2          | 11,11
3          | 20,20

..

So for each location in this table, I need to find the closest.. say 5 other locations.

Update

So far, it looks like using a CURSOR is the only way .. but I'm open to more set based solutions.

Upvotes: 2

Views: 1453

Answers (1)

Ben Thul
Ben Thul

Reputation: 32697

You need to find the nearest neighbors within the same set?

SELECT *
FROM SomeGeogBoundaries as b
OUTER APPLY (
   SELECT TOP(5) CentrePoint
   FROM SomeGeogBoundaries as t
   WHERE t.CentrePoint.STInsersects(b.CentrePoint.STBuffer(100))
   ORDER by b.CentrePoint.STDistance(t.CentrePoint)
) AS nn

Two notes.

  1. The where clause in the outer apply is to limit the search to (in this case) points that are within 100 meters of eachother (assuming that you're using an SRID whose native unit of measure is meters). That may or may not be appropriate for you. If not, just omit the where clause.

  2. I think this is still a cursor. Don't fool yourself into thinking that just because there is nary a declare cursor statement to be seen that the db engine has much of a choice but to iterate through your table and evaluate the apply for each row.

Upvotes: 2

Related Questions