Difference between SDO_NN and BallTree Sklearn for Nearest Neighbors

Question

I am trying to find nearest n/w nodes from multiple buildings in an area, I have 2 geodataframes/Tables in Oracle DB, buildings have point geometries with ID's and Nodes have point geometries with Node ID's,

Eg: I want to find the nearest N nodes from 1 building- I have ~100000 Nodes, so to find the nearest nodes I am experimenting with 2 techniques, Oracle Spatial Functions and GeoPandas/BallTree in Python

1. Finding the Nearest points using Ball Tree from Sklearn, Code - https://stackoverflow.com/questions/62198199/k-nearest-points-from-two-dataframes-with-geopandas

closest_stops = nearest_neighbor(buildings, stops, return_dist=True)

This gives me fast results and works on the complete set of Data

2. Finding Nearest points using SDO_NN in Oracle DB: Link - https://docs.oracle.com/database/121/SPATL/sdo_nn.htm#SPATL1032

SDO_NN(geometry1, geometry2, param [, number]);

My code

SDO_NN(S.LOCATION, ORACLE_SPATIAL_STUDIO.SGTECH_PTF(N.LONGITUDE, N.LATITUDE), 'DISTANCE = '2000' UNIT=FOOT SDO_NUM_RES=1', 1 ) = 'TRUE'

The question is I observed for some buildings the 1st Nearest points out of the ~100000 Nodes is exactly the same for both Techniques in Meters/Feet, although there are some instances where the 1st nearest Point is completely off for the BallTree Algorithm, Eg:

Building Location Result from BallTree - 110m Result from SDO_NN - 185m

In reality on Google Maps, the distance is completely off from the calculations and also the result from SDO_NN looks closer

I understand that here BallTree uses the haversine metric to measure the distance, but I would like to understand the difference between both and which can be trusted for real world applications such as Network Deployment Routes ,etc.

Best case scenario is getting the Nearest Node based on Accessibility/Roadway distance but I believe that's challenging with my current setup.

Any Ideas on the Distance calculations here? Any Suggestions on which technique I can rely on?

Answer 1

BallTree is very fast, you can change the distance metric in BallTree to metric='euclidean' and check again.

tree = BallTree(candidates, leaf_size=15, metric='euclidean')

Also since your coordinates are in EPSG:4326 (WGS84) its always better to convert to a projected coordinate system which gives distances in meters directly. You can convert your coordinates to a UTM projection and once you do that both methods should give you same results for all cases as both will use Euclidean distance. I think the difference in results is only because of the different distance methods used.

Edit: Based on your comment I tried to verify the straight distance between the nearest point you found using BallTree method and the building and it seems that it is 827meters.

I feel that while you are constructing the BallTree and updating the distances back in the dataframe you are probably putting distances against incorrect index. While the distance of SDO_NN matches to that 185 meters you have calculated.

In the other Stackoverflow link you are referring to construct your balltree the index of geodatframe is being reset at this line

right = right_gdf.copy().reset_index(drop=True)

so make sure you are updating distances against correct indices.