Nearest neighbor using BQ Scripting

Michael Entin
Dec 15, 2019 · 2 min read

We’ve already discussed Nearest Neighbors problem:

The general idea is to start with small search radius, and increase it if we fail to find anything. Since that article, we got BigQuery Scripting, so let’s use it to do this. This time we’ll solve single neighbor search — find nearest neighbor for a specific point, rather than finding neighbors for a set of points.

For demo purposes, we’ll search nearest road in US Tiger database. Note it is not a very good road dataset for actual use, but fine for demo. The search with a specific radius will look like this:

SELECT *
FROM `bigquery-public-data.geo_us_roads.us_national_roads`
WHERE ST_DWithin(center, road_geom, search_r)
ORDER BY ST_Distance(center, road_geom) DESC LIMIT 1

Where search_r is search radius, and center is the point for which we are trying to find a neighbor. We’ll start with search radius of 100 m and increase it 10x each time if we don’t find anything with current radius. The procedure will look like this:

CREATE OR REPLACE PROCEDURE demo.NearestRoad(
center GEOGRAPHY,
OUT road_id STRING,
OUT road_geom GEOGRAPHY)
BEGIN
DECLARE search_r FLOAT64; -- current search radius
DECLARE result STRUCT<road_id STRING, road_geom GEOGRAPHY>;
SET search_r = 100;
LOOP
SET result = (
SELECT STRUCT(road_id, road_geom)
FROM `bigquery-public-data.geo_us_roads.us_national_roads`
WHERE ST_DWithin(center, road_geom, search_r)
ORDER BY ST_Distance(center, road_geom) DESC LIMIT 1
);
IF result IS NOT NULL THEN
SET road_id = result.road_id;
SET road_geom = result.road_geom;
LEAVE;
END IF;
SET search_r = search_r * 10;
END LOOP;
END;

You can call it like this:

DECLARE id STRING;
DECLARE geom GEOGRAPHY;
CALL demo.NearestNeighbor(ST_GeogPoint(-122.191667, 47.685833),
id, geom);

Michael Entin

Written by

Hi, I'm TL of BigQuery GIS project. Posting small recipes and various notes for BQ GIS users.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade