search

jlmelville / rnndescent

R package implementing the Nearest Neighbor Descent method for approximate nearest neighbors
https://jlmelville.github.io/rnndescent/
GNU General Public License v3.0
10 stars 2 forks source link

Factor of 1/2 in TS-SS implementation? #8

Closed mhlinder closed 9 months ago

mhlinder commented 9 months ago

The original TS-SS paper expresses angles in degrees, which is different from the radians used in the code.

This is correctly accounted for in places like here, where the authors' "10 degrees" are converted to radians.

Equation (6) in the paper gives the equation (using angle theta_degrees in degrees)

SS(A, B) = pi * (ED(A, B) + MD(A, B))^2 * (theta_degrees/360)

I believe the corresponding equation for radians should be

SS(A, B) = pi *(ED(A, B) + MD(A, B))^2 * (theta_radians/(2*pi))
         = (ED(A, B) + MD(A, B))^2 * theta_radians / 2

However, in the implementation here, the factor of 1/2 is missing.

Is there a reason for that? Or should the value be scaled by 1/2?

jlmelville commented 9 months ago

The implementation of tsss is a pretty straight translation of the python version at https://github.com/lmcinnes/pynndescent/blob/d99a821b0ed27cf97af16b688568be9838c1e397/pynndescent/distances.py#L498 and seems to give the same numerical results.

But from a closer reading of the paper and your comments it does seem like we are missing a factor of 1/2. So this seems like a bug.

jlmelville commented 9 months ago

This will be fixed in the next release of rnndescent. Thank you for reporting @mhlinder!