Nearest-Neighbor Searching

WherobotsDB supports nearest-neighbor searching on geospatial data by providing a geospatial k-Nearest Neighbors (kNN) join method. This method involves identifying the k-nearest neighbors for a given spatial point or region based on geographic proximity, typically using spatial coordinates and a suitable distance metric like Euclidean or great-circle distance.

ST_KNN

Introduction: join operation to find the k-nearest neighbors of a point or region in a spatial dataset. Format: ST_KNN(R: Table, S: Table, k: Integer, use_sphere: Boolean, search_radius: Double)

R represents the queries side table.
S represents the objects side table.
K denotes the number of nearest neighbors to retrieve.
use_sphere selects the distance model. false uses planar (Euclidean) distance in the geometries’ coordinate units. true uses great-circle (haversine) distance on a sphere, in meters.
search_radius is an optional parameter that defines the maximum distance within which neighbors will be searched. It is expressed in the same units as the selected distance model: coordinate units (degrees for EPSG:4326 data) when use_sphere is false, meters when use_sphere is true.

Queries side table contains geometries that are used to find the k-nearest neighbors in the object side table. How non-point geometries (lines, polygons) are measured depends on the distance model:

use_sphere = false (planar): distances are the true minimum distance between the two geometries (boundary to boundary). A parcel polygon touching a river has distance 0. This is the mode to use for exact nearest-feature searches.
use_sphere = true (sphere): each non-point geometry is reduced to its centroid before the distance is computed, so results are approximate for large or elongated geometries.

In case there are ties in the distance, the result will include all the tied geometries only when the following sedona config is set to true:

spark.sedona.join.knn.includeTieBreakers=true

The ST_KNN join does an inner join for the query side table (Table R). It returns only pairs where there is at least one matching neighbor within the k nearest neighbors. If a query point has no valid neighbor (e.g., because k is too large), it is excluded from the result.

Known limitations

ST_KNN join is a new syntax we introduced to Spatial SQL and therefore it has a few known limitations. But we are actively working on solving them.

Filter Pushdown Considerations

When using ST_KNN with filters applied to the resulting DataFrame, some of these filters may be pushed down to the object side of the kNN join. This means the filters will be applied to the object side reader before the kNN join is executed. If you want the filters to be applied after the kNN join, ensure that you first materialize the kNN join results and then apply the filters. For example, you can use the following approach: Scala Example:

val knnResult = knnJoinDF.cache()
val filteredResult = knnResult.filter(condition)

SQL Example:

CREATE OR REPLACE TEMP VIEW knnResult AS
SELECT * FROM (
  -- Your KNN join SQL here
) AS knnView;
CACHE TABLE knnResult;
SELECT * FROM knnResult WHERE condition;

Handling SQL-Defined Tables in ST_KNN Joins

When creating DataFrames from hard-coded SQL select statements in WherobotsDB, and later using them in ST_KNN joins, WherobotsDB may attempt to optimize the query in a way that bypasses the intended kNN join logic. Specifically, if you create DataFrames with hard-coded SQL, such as:

val df1 = sedona.sql("SELECT ST_Point(0.0, 0.0) as geom1")
val df2 = sedona.sql("SELECT ST_Point(0.0, 0.0) as geom2")

val df = df1.join(df2, expr("ST_KNN(geom1, geom2, 1)"))

WherobotsDB may optimize the join to a form like this:

SELECT ST_KNN(ST_Point(0.0, 0.0), ST_Point(0.0, 0.0), 1)

As a result, the ST_KNN function is handled as a User-Defined Function (UDF) instead of a proper join operation, preventing WherobotsDB from initiating the kNN join execution path. Unlike typical UDFs, the ST_KNN function operates on multiple rows across DataFrames, not just individual rows. When this occurs, the query fails with an UnsupportedOperationException, indicating that the KNN predicate is not supported. Workaround: To prevent the optimization from bypassing the kNN join logic, the DataFrames created with hard-coded SQL select statements must be materialized before performing the join. By caching the DataFrames, you can instruct the engine to avoid this undesired optimization:

val df1 = sedona.sql("SELECT ST_Point(0.0, 0.0) as geom1").cache()
val df2 = sedona.sql("SELECT ST_Point(0.0, 0.0) as geom2").cache()

val df = df1.join(df2, expr("ST_KNN(geom1, geom2, 1)"))

Materializing the DataFrames with .cache() ensures that the correct kNN join path is followed and it prevents the optimization that would treat ST_KNN as a simple UDF.

SQL Example

Suppose we have two tables QUERIES and OBJECTS with the following data: QUERIES table:

ID  GEOMETRY            NAME
 POINT(1 1)	        station1
 POINT(10 10)	    station2
 POINT(-0.5 -0.5)	station3

OBJECTS table:

ID  GEOMETRY            NAME
POINT(11 5)         bank1
POINT(12 1)         bank2
POINT(-1 -1)        bank3
POINT(-3 5)         bank4
POINT(9 8)          bank5
POINT(4 3)          bank6
POINT(-4 -5)        bank7
POINT(4 -2)         bank8
POINT(-3 1)         bank9
POINT(-7 3)         bank10
POINT(11 5)         bank11
POINT(12 1)         bank12
POINT(-1 -1)        bank13
POINT(-3 5)         bank14
POINT(9 8)          bank15
POINT(4 3)          bank16
POINT(-4 -5)        bank17
POINT(4 -2)         bank18
POINT(-3 1)         bank19
POINT(-7 3)         bank20

Example 1: Query Without search_radius Parameter

SELECT
    QUERIES.ID AS QUERY_ID,
    QUERIES.GEOMETRY AS QUERIES_GEOM,
    OBJECTS.GEOMETRY AS OBJECTS_GEOM
FROM QUERIES JOIN OBJECTS ON ST_KNN(QUERIES.GEOMETRY, OBJECTS.GEOMETRY, 4, FALSE)

Explanation: This query performs a k-Nearest Neighbor (kNN) join between the QUERIES table and the OBJECTS table. For each geometry in the QUERIES table, the function ST_KNN identifies the 4 nearest geometries (based on spatial distance) from the OBJECTS table. FALSE indicates that the spheroid distance model is not being used. Instead a planar distance model is being applied, and distances are in the geometries’ coordinate units (degrees for EPSG:4326 data). Since the search_radius parameter is not provided, there are no constraints on the maximum distance between the query and the objects. Output:

+--------+-----------------+-------------+
|QUERY_ID|QUERIES_GEOM     |OBJECTS_GEOM |
+--------+-----------------+-------------+
|3       |POINT (-0.5 -0.5)|POINT (-1 -1)|
|3       |POINT (-0.5 -0.5)|POINT (-1 -1)|
|3       |POINT (-0.5 -0.5)|POINT (-3 1) |
|3       |POINT (-0.5 -0.5)|POINT (-3 1) |
|1       |POINT (1 1)      |POINT (-1 -1)|
|1       |POINT (1 1)      |POINT (-1 -1)|
|1       |POINT (1 1)      |POINT (4 3)  |
|1       |POINT (1 1)      |POINT (4 3)  |
|2       |POINT (10 10)    |POINT (9 8)  |
|2       |POINT (10 10)    |POINT (9 8)  |
|2       |POINT (10 10)    |POINT (11 5) |
|2       |POINT (10 10)    |POINT (11 5) |
+--------+-----------------+-------------+

Example 2: Query With search_radius Parameter

SELECT
    QUERIES.ID AS QUERY_ID,
    QUERIES.GEOMETRY AS QUERIES_GEOM,
    OBJECTS.GEOMETRY AS OBJECTS_GEOM
FROM QUERIES JOIN OBJECTS ON ST_KNN(QUERIES.GEOMETRY, OBJECTS.GEOMETRY, 4, FALSE, 3.0)

Explanation: This query is similar to Example 1 but this example includes an additional parameter, search_radius = 3.0. With this parameter, only neighbors within 3.0 units of each query geometry are considered. The search_radius acts as a filter, removing any object geometries that are farther than the specified radius. When search_radius is applied, the query may return fewer than K neighbors if there aren’t enough points within the radius. Output:

+--------+-----------------+-------------+
|QUERY_ID|QUERIES_GEOM     |OBJECTS_GEOM |
+--------+-----------------+-------------+
|2       |POINT (10 10)    |POINT (9 8)  |
|2       |POINT (10 10)    |POINT (9 8)  |
|3       |POINT (-0.5 -0.5)|POINT (-1 -1)|
|3       |POINT (-0.5 -0.5)|POINT (-1 -1)|
|3       |POINT (-0.5 -0.5)|POINT (-3 1) |
|3       |POINT (-0.5 -0.5)|POINT (-3 1) |
|1       |POINT (1 1)      |POINT (-1 -1)|
|1       |POINT (1 1)      |POINT (-1 -1)|
+--------+-----------------+-------------+

In this output: Some object points from the previous result set are missing because they fall outside the 3.0-unit search radius. For some queries (e.g., QUERY_ID = 2), fewer than 4 neighbors are returned since not enough points are within the specified radius. The search_radius ensures more focused results by excluding distant neighbors, which can be useful for scenarios requiring spatial proximity. Example 3: Exact Nearest Neighbors With Distances in Meters To attach the true nearest feature (with an exact distance in meters) to every geometry in a table, transform both sides to a projected, meter-based coordinate reference system, then run ST_KNN with use_sphere = false and k = 1. Planar distance on projected coordinates is the exact minimum distance between the two geometries, boundary to boundary.

SELECT
    p.id,
    f.feature_id,
    ST_Distance(p.geom_m, f.geom_m) AS distance_m
FROM (SELECT id, ST_Transform(geometry, 'EPSG:4326', 'EPSG:3311') AS geom_m FROM parcels) p
JOIN (SELECT feature_id, ST_Transform(geometry, 'EPSG:4326', 'EPSG:3311') AS geom_m FROM features) f
    ON ST_KNN(p.geom_m, f.geom_m, 1, false, 25000.0)

Pick a projected coordinate reference system appropriate for your region (here EPSG:3311, California Albers); see CRS Transformation. The optional search_radius (25000.0 meters here, written as a double literal) bounds the search and reduces the work the join has to do.

ST_AKNN

Introduction: join operation to find the k-nearest neighbors of a point or region in a spatial dataset. Format: ST_AKNN(R: Table, S: Table, k: Integer, use_sphere: Boolean, search_radius: Double) The ST_AKNN function is similar to ST_KNN, but it uses approximate algorithms to find the k-nearest neighbors. This can be useful for large datasets where exact kNN search is computationally expensive. The trade-off is that approximate algorithms may not always return the exact k-nearest neighbors, but they provide a good approximation in a reasonable amount of time.

Known limitations

Similar to ST_KNN, ST_AKNN join is a new syntax we introduced to Spatial SQL.

Filter Pushdown Considerations

Filter pushdown behavior in ST_AKNN is similar to that in ST_KNN. If filters are applied to the resulting DataFrame, they might be pushed down to the object side reader before the kNN join is executed. To apply filters after the join, ensure you materialize the kNN join results before applying any filters. SQL Example

SELECT
    QUERIES.ID AS QUERY_ID,
    QUERIES.GEOMETRY AS QUERIES_GEOM,
    OBJECTS.GEOMETRY AS OBJECTS_GEOM
FROM QUERIES JOIN OBJECTS ON ST_AKNN(QUERIES.GEOMETRY, OBJECTS.GEOMETRY, 4, FALSE)

Handling SQL-Defined Tables in ST_AKNN Joins

The same considerations for handling SQL-defined tables in ST_KNN joins apply to ST_AKNN joins. Ensure that DataFrames created from hard-coded SQL select statements are materialized before performing the join to prevent the engine from bypassing the kNN join logic.

Wherobots Cloud REST API

WherobotsDB

Vector tiles (PMTiles)

Havasu (Iceberg) table management

GeoStats and Map Matching

Rasterflow

Nearest-Neighbor Searching

ST_KNN

Known limitations

SQL Example

ST_AKNN

Known limitations

​ST_KNN

​Known limitations

​SQL Example

​ST_AKNN

​Known limitations

ST_KNN

Known limitations

SQL Example

ST_AKNN

Known limitations