Unreachable code reached while inserting vectors

[Kerollmops]

Hey!

When I reached this unreachable panic, I was trying to insert points into an Hgg<DotProduct, Vec<f32>, u32> data structure. The DotProduct data structure is pretty easy but I am not sure about its correctness. Does it validate the triangle inequality? My vectors have 384 dimensions. Should they be normalized (I think they are)?

pub struct DotProduct;

impl Metric<Vec<f32>> for DotProduct {
    type Unit = u32;

    // TODO explain me this function, I don't understand why f32.to_bits is ordered.
    // I tried to do this and it wasn't OK <https://stackoverflow.com/a/43305015/1941280>
    //
    // Following <https://docs.rs/space/0.17.0/space/trait.Metric.html>.
    fn distance(&self, a: &Vec<f32>, b: &Vec<f32>) -> Self::Unit {
        let dist: f32 = a.iter().zip(b).map(|(a, b)| a * b).sum();
        let dist = 1.0 - dist;
        debug_assert!(!dist.is_nan());
        dist.to_bits()
    }
}

Could there be a way to move the hgg crate to the latest version of the space crate? As the latest v0.18 supports raw f32 as distance values.

EDIT: I tried with the latest version on main (6d1eacd) and the bug is always present.

[Kerollmops]

Hey @vadixidav,

I created a minimal reproducible example with fairly simple values. I was going to give you the vectors of 384 dimensions, but the bug can be triggered with smaller ones. I tried with different distance functions, but I may be missing something in this DotProduct one.

/// This is a minimal reproducible example to make
/// the hgg crate trigger an internal crash.
///
/// ```toml
/// [dependencies]
/// hgg = "0.4.1"
/// space = "0.17.0"
/// ```
use hgg::Hgg;
use space::{KnnInsert, Metric};

fn main() {
    let mut hgg: Hgg<DotProduct, Vec<f32>, u32> = Hgg::default();

    hgg.insert(vec![0.1, 1.0, 0.2], 0);
    hgg.insert(vec![0.0, 0.5, 0.2], 1);
    hgg.insert(vec![0.2, 1.0, 1.2], 2);
}

#[derive(Default)]
pub struct DotProduct;

impl Metric<Vec<f32>> for DotProduct {
    type Unit = u32;

    fn distance(&self, a: &Vec<f32>, b: &Vec<f32>) -> Self::Unit {
        let dist: f32 = a.iter().zip(b).map(|(a, b)| a * b).sum();
        let dist = 1.0 - dist;
        debug_assert!(!dist.is_nan());
        dist.to_bits()
    }
}

---

It looks like this Euclidean function works. There is no issue when I try my previous example with this Euclidean metric struct. So it seems like the DotProduct distance function broke the triangle inequality law or something?

#[derive(Default)]
pub struct Euclidean;

impl Metric<Vec<f32>> for Euclidean {
    type Unit = u32;

    fn distance(&self, a: &Vec<f32>, b: &Vec<f32>) -> Self::Unit {
        let squared: f32 = a.iter().zip(b).map(|(a, b)| (a - b).powi(2)).sum();
        let dist = squared.sqrt();
        debug_assert!(!dist.is_nan());
        dist.to_bits()
    }
}

[vadixidav]

It looks like cosine distance is not a true distance metric as per https://towardsdatascience.com/what-is-metric-74b0bf6e862.

However, IIRC (though I am having trouble finding an answer online), if you normalize your vectors first before taking the cosine distance then they will satisfy the triangle inequality. Basically, just normalize them before taking the dot product and see if that improves things. I would recommend pre-normalizing all the vectors to avoid computationally expensive normalizing during search. Please make sure that no vector is zero when inserted, which would produce a NaN or some other non normal float.

That being said, I believe that L2 (euclidean) or L1 (manhattan/hamming) distance is typically preferred.

[vadixidav]

Please refer to this section of the wikipedia page: https://en.wikipedia.org/wiki/Cosine_similarity#Angular_distance_and_similarity. To compute the distance for your vectors in this situation, you will need to get the angular distance. It is a bit more expensive to compute though, so I would recommend considering euclidean.