lmcinnes / lmcinnes/pynndescent

TSSS missing a factor of 2

Open
#233 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Python
Stars
970
Forks
107
PR merge metrics
No merged PRs in 30d

Description

This was reported to me at https://github.com/jlmelville/rnndescent/issues/8 but would also affect pynndescent, which is unsurprising as I directly converted the equation from here into C++.

Equation 7 of the TS-SS equation in the original paper ([PDF](https://www.researchgate.net/profile/Arash-Heidarian/publication/303513110_A_Hybrid_Geometric_Approach_for_Measuring_Similarity_Level_Among_Documents_and_Document_Clustering/links/5da389b592851c6b4bd33f63/A-Hybrid-Geometric-Approach-for-Measuring-Similarity-Level-Among-Documents-and-Document-Clustering.pdf)), written in terms of degrees, has a denominator of 720, which would convert to 4pi in radians (the pi would cancel). As can be seen at:

https://github.com/lmcinnes/pynndescent/blob/d99a821b0ed27cf97af16b688568be9838c1e397/pynndescent/distances.py#L518-L520

there's only a division of 2 that shows up in the calculation of the return value.

I would volunteer to write a PR and update any affected test, but I would like to to use that paper as a means of confirming my understanding of the equations, as there are some partial numerical results in it. Unfortunately, I quickly got fed up trying to back-convert the vectors in the figures to plausible 2D descriptors (e.g. how can A and B in figure 1a be vectors of length 6, with an angle of 30 degrees between them, but a Euclidean distance of 2). Obviously this doesn't affect the returned neighbors but it could have a (small) effect for anything that used the distances downstream, like UMAP.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with pynndescent/distances.py at lines 518-520 and compare the TSSS calculation with Equation 7 of the linked paper, including its degree-to-radian conversion. Confirm the factor against the paper's partial numerical results, then update the affected test and verify that the corrected distance remains consistent with expected neighbors.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
data, search
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.