(Reverse) Geospatial Nearest Neighbour Searches

Finding the k nearest butchers? (Photo by henry perks on Unsplash)

I have occasionally been asked for Geospatial Nearest Neighbour searches and its inverse the Reverse Nearest Neighbour. So I thought, I spend a couple of minutes to write a simple, but general purpose, SQLScript and provide it to you within this blog post. So this is gonna be a quick read and I hope, you will find some use for the scripts.

k-Nearest Neighbour

Problem Statement

Given a table of geometries (i.e. points). Find the k geometries, that are closest to a given geometry (i.e. point).

Exemplary Use Case

You want to visit The Brandenburg Gate in Berlin and are searching for an accommodation nearby. You use a k-Nearest Neighbour Search on the AirBnB listings of Berlin to find the 10 (k=10) closest listings. (…this dataset has also been used in my previous blogs)

Stored Function

CREATE OR REPLACE FUNCTION KNN 
(
	ref_geom ST_GEOMETRY, 
	nb_geom_tab NVARCHAR(100), 
	nb_id_col NVARCHAR(50), 
	nb_geom_col NVARCHAR(50),
	k INTEGER
)
RETURNS TABLE (ID NVARCHAR(100), SHAPE ST_GEOMETRY)
AS BEGIN
	
	DECLARE geom_list TABLE (ID NVARCHAR(100), SHAPE ST_GEOMETRY);
	
	EXECUTE IMMEDIATE 
		'SELECT CAST(' || :nb_id_col || ' AS NVARCHAR(100)) AS ID, ' || :nb_geom_col || ' as SHAPE FROM ' || :nb_geom_tab 
	INTO geom_list;
	
	RETURN 
		SELECT TOP :k ID, SHAPE
		FROM :geom_list
		ORDER BY :ref_geom.ST_DISTANCE(SHAPE) ASC;
END;

Usage

Find the 10 closest AirBnB listings to The Brandenburg Gate. Note that the function should return k records.

SELECT * 
FROM 
    KNN( 
        ST_GEOMFROMTEXT('POINT(13.37770 52.51634)',1000004326), 
        'LISTINGS_AIRBNB_BERLIN', 
        'ID', 
        'SHAPE', 
        10
    );

Reverse k-Nearest Neighbour

Problem Statement

Given a table of geometries (i.e. points). Find the geometries, where a given geometry (i.e. point) is one of the k closest geometries.

Exemplary Use Case

You are the owner of an AirBnB listing in Berlin and would like to improve your marketing. For this reason, you would like to know, for which landmarks/points of interest your listing is shown to prospects as one of the 10 (k=10) closest listings.

Stored Function

CREATE OR REPLACE FUNCTION RKNN 
(
	ref_geom ST_GEOMETRY, 
	nb_geom_tab NVARCHAR(100),
	nb_geom_col NVARCHAR(50),
	poi_geom_tab NVARCHAR(100), 
	poi_id_col NVARCHAR(50), 
	poi_geom_col NVARCHAR(50), 
	k INTEGER
)
RETURNS TABLE (ID NVARCHAR(100), SHAPE ST_GEOMETRY)
AS BEGIN
	
	DECLARE nb_geom_list TABLE (SHAPE ST_GEOMETRY);
	DECLARE poi_geom_list TABLE (ID NVARCHAR(100), SHAPE ST_GEOMETRY);
		
	EXECUTE IMMEDIATE 'SELECT ' || :nb_geom_col || ' as SHAPE FROM ' || :nb_geom_tab INTO nb_geom_list;
	EXECUTE IMMEDIATE 'SELECT CAST(' || :poi_id_col || ' AS NVARCHAR(100)) AS ID, ' || :poi_geom_col || ' as SHAPE FROM ' || :poi_geom_tab INTO poi_geom_list;
	
	RETURN
		SELECT ID, SHAPE
		FROM
		(
			SELECT ID, SHAPE, MAX(DIST) AS MAXDIST
			FROM 
			(
				SELECT a.ID, a.SHAPE, a.SHAPE.ST_DISTANCE(b.SHAPE) AS DIST, RANK() OVER (PARTITION BY a.ID ORDER BY a.SHAPE.ST_DISTANCE(b.SHAPE) ASC) AS RNK
				FROM :poi_geom_list a, :nb_geom_list b
			)
			WHERE RNK <= :k
			GROUP BY ID, SHAPE
		)
		WHERE ref_geom.ST_DISTANCE(SHAPE) <= MAXDIST;
END;

Usage

Find the landmarks, where my AirBnB is listed as one of the 10 closest AirBnBs. Note that the function can return any number of records (i.e. probably not k).

SELECT * 
FROM 
    RKNN(
        ST_GEOMFROMTEXT('POINT(13.38023 52.51614)',1000004326), 
        'LISTINGS_AIRBNB_BERLIN', 
        'SHAPE', 
        'POIS_BERLIN', 
        'OSM_ID', 
        'WAY', 
        10
    );

Summary

The two above outlined functions can be used to do a simple k-Nearest Neighbour or Reverse k-Nearest Neighbour search in SAP HANA. The functions are designed to work independent of the underlying dataset and should be usable for your data without modification.

Well, maybe you need to fix bugs…. Did I mention that there is no warranty?