# Geography and the Nearest Neighbor Search

Performing searches on geographic coordinates (latitude and longitude) seems to be a requirement on many of the projects I have been doing lately. One of the most common is the nearest neighbor search which will find the location(s) nearest to the users current location. Most distance calculations involving geographic coordinates make use of the haversine formula.

## Nearest Neighbor Search in MySQL

See the MySQL implementation below. For a great explanation of this code, refer to geo-search.pdf.

-- Stored Procedure Parameters DECLARE @mylat DOUBLE; DECLARE @mylat DOUBLE; DECLARE @dist INT; -- my current location SET @mylat=122.4058; SET @mylon=37.7907; -- limiting distance SET @dist=10; -- calculate lon and lat for the rectangle: DECLARE lon1 FLOAT; SET lon1 = @mylon – dist / abs(cos(radians(@mylat)) * 69); DECLARE lon2 FLOAT; SET lon2 = @mylon + dist / abs(cos(radians(@mylat)) * 69); DECLARE lat1 FLOAT; SET lat1 = @mylat - (dist / 69); DECLARE lat2 FLOAT; SET lat2 = @mylat + (dist / 69); SELECT *, 3956 * 2 * ASIN(SQRT( POWER(SIN((@mylat - abs(dest.lat)) * pi() / 180 / 2), 2) + COS(@mylat * pi() / 180 ) * COS(abs(dest.lat) * pi() / 180) * POWER(SIN((@mylon – dest.lon) * pi() / 180 / 2), 2) )) AS distance FROM hotels dest -- having distance < @dist –- Don’t do this... The WHERE clause below is way more efficient. WHERE -- Use the bounding box method to prune resultset before calculating distance. dest.lon BETWEEN lon1 AND lon2 AND dest.lat BETWEEN lat1 AND lat2 ORDER BY distance LIMIT 7

## Nearest Neighbor Search in SQL Server 2012

If you are using SQL Server 2012, the Geography types make this search much easier (and more efficient). See here for more info.

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);

## Nearest Neighbor Search with Linq

From .Net, you can take advantage of this functionality with Linq as in the example below. A detailed explaination of the above example can be found here.

private Facility GetNearestLocation(DbGeography myLocation) { var q1 = from l in context.Location let distance = l.Geocode.Distance(jobsite) where distance < 500 * 1609.344 // within 500 miles orderby distance select f; return q1.FirstOrDefault(); }

### Further reference:

Convert Lat/Long to Geography Point

Creating High Performance Spatial Databases

Calculating the Bearing from One Point to Another

BeginningSpatial.com