Paul Ramsey

Finding the Nearest Neighbor

Won't you be my Neighbor?

Apps with maps, on phones and on the web, are frequently built around “nearest neighbor” queries, sifting through a database to find the records that are contextually appropriate given an input location.

  • Find me all the records that fit in the map!
  • Find me all the records within 1km of the user location!
  • Find me the 10 records nearest to the user!

For “records”, replace with “restaurants” or “gas stations” or “future close friends” depending on the application you are building.

All of these questions can be answered with SQL, and with the CartoDB SQL API it’s easy to send them to the database to get back the data your app needs!

Find Things Within a Box

The map window in an app defines a box, and it’s not uncommon to just want a list of things that are visible right now.

FROM mytable
WHERE ST_Intersects(
    ST_MakeEnvelope(%minlon, %minlat, %maxlon, %maxlat, 4326),

The query just builds a query envelope and then finds all the records that intersect it.

Find Things Within a Radius

Frequently an app will use a query point, either the center of a view, or the location of a zip code or other named place to center a radius query.

FROM mytable
    ST_Transform(CDB_LatLng(%lat, %lon), 3857),
    %radius / cos(%lat * pi()/180)

In order to do a distance calculation, this query uses the the_geom_webmercator column, which (surprise!) is in the Mercator projection (aka “EPSG:3857”). Because Mercator distorts features at the poles by stretching them larger, we have to scale up the distance the further north the query is, hence the trigonometry applied to the radius parameter.

Find the Nearest Things

Like the previous example, a query point can seed a list of “things nearest to the point”. Unlike the radius query, we don’t care how far away (or near) the results are, we just want the closest ones.

FROM mytable
ORDER BY the_geom_webmercator
  <-> ST_Transform(CDB_LatLng(%lat, %lon), 3857)
LIMIT %numrecords

The query returns the records in order of closest to furthest, stopping when the LIMIT number of records is reached. If you omit the LIMIT you’ll get the whole table back, in sorted order (ouch!).

About the author
Paul Ramsey

Related Posts

Ready to optimize your territories with Location Intelligence?

Close circle icon

Contact us

Please fill out the below form and we'll be in touch real soon.