Fast evaluation of Euclidean distance with sparse data

Question

I am working on a KNN implementation for sparse datasets (that I apply to text analysis). My points are represented by a Dictionary<string, double>, each key represents a word of the text and the value, its count or TFIDF.

I am using index inversion to reduce the number of distances to evaluate. However, evaluating the distance remains the bottleneck. It is represented in the following method:

    public static double Euclide(Dictionary<string, double> sp1, Dictionary<string, double> sp2)
    {
        double distance = 0;
        foreach (KeyValuePair<string, double> kvp1 in sp1)
        {
            if (sp2.ContainsKey(kvp1.Key))
                distance += Math.Pow((kvp1.Value - sp2[kvp1.Key]), 2);
            else
                distance += Math.Pow((kvp1.Value), 2);
        }

        foreach (KeyValuePair<string, double> kvp2 in sp2)
            if (!sp1.ContainsKey(kvp2.Key))
                distance += Math.Pow((kvp2.Value), 2);

        return distance;
    }

How can I make it faster? Any help would be greatly appreciated.

I think I could reduce the time of evaluation using a Dictionary<int, double>, but I prefer to stick to strings, as it allows me to see at a glance what is going on (hashing words would compromise that).

The following yieled a 1.3~2.1x improvement (depending on the length of the input, but it is still not enough) :

    public static double FastEuclide(Dictionary<string, double> sp1, Dictionary<string, double> sp2)
    {
        double distance = 0;
        foreach (KeyValuePair<string, double> kvp1 in sp1)
        {
            double sp1Value = kvp1.Value;

            if (sp2.ContainsKey(kvp1.Key))
            {
                double sp2Value = sp2[kvp1.Key],
                    diff = kvp1.Value - sp2[kvp1.Key];
                distance += diff * diff;
            }
            else
                distance += sp1Value * sp1Value;
        }

Answer 1

Calling ContainsKey() on a dictionary if you need to get the value later on should be replaced with TryGetValue() to reduce the processing time.

See: what-is-more-efficient-dictionary-trygetvalue-or-containskeyitem

TryGetValue will be faster.

ContainsKey uses the same check as TryGetValue, which internally refers to the actual entry location. The Item property actually has nearly identical code functionality as TryGetValue, except that it will throw an exception instead of returning false.

Using ContainsKey followed by the item basically duplicates the lookup functionality, which is the bulk of the computation in this case

---

The next part to increase performance is to replace the call to Math.Pow() with multiplying the value by itself.

So instead of Math.Pow((kvp2.Value), 2) you should use kvp2.Value * kvp2.Value.

You just edited your question to do this but I will keep it in my review.

---

Using the said above will lead to

public static double Euclide(Dictionary<string, double> sp1, Dictionary<string, double> sp2)
{
    double distance = 0;
    
    foreach (KeyValuePair<string, double> kvp1 in sp1)
    {
        double possibleValue = 0.0d;
        sp2.TryGetValue(kvp1.Key, out possibleValue);

        double currentValue = kvp1.Value - possibleValue;

        distance += currentValue * currentValue;
    }

    foreach (KeyValuePair<string, double> kvp2 in sp2)
    {
        if (!sp1.ContainsKey(kvp2.Key))
        {
            distance += kvp2.Value * kvp2.Value;
        }
    }
    return distance;
}

This

double possibleValue = 0.0d;
sp2.TryGetValue(kvp1.Key, out possibleValue);

double currentValue = kvp1.Value - possibleValue;

will store the value of the searched key inside possibleValue if the key is in the dictionary. If TryGetValue() does not succeed it will return default(T) which for a double is 0.0.

---

I have added braces {} for the for and the if which makes the code less error prone. I would like to encourage you to always use braces.

Answer 2

I'm sorry I'm not addressing your direct question, but I feel I need to mention this.

Any time you're writing mathematical type code, it's useful to leave a comment explaining yourself:

// This is So & So's formula....

Maybe even drop a link to a wiki article or something. The logic may be obvious to you now, but may not be in 6 months time or to someone else.

Answer 3

Not really a code review: Have you tried using a sparse linear algebra library, like Math.NET? This would let you work with sparse vectors as:

var v1 = new SparseVector(1000000);
var v2 = new SparseVector(1000000);

var rnd = new Random();
for (int i = 0; i < 1000; i++)
{
    v1[rnd.Next(v1.Count)] = rnd.NextDouble();
    v2[rnd.Next(v2.Count)] = rnd.NextDouble();
}

And then you can just call (v1 - v2).L2Norm() to calculate the euclidean distance.

I would assume that Math.NET is optimized for operations like this.

Answer 4

Borrowing heavily from Heslacher's answer, can you perhaps parallelize the method? I took a stab at it using a range partitioner.

I added these usings:

using System.Threading;
using System.Collections.Concurrent;

And this method:

public static double ParallelEuclide(Dictionary<string, double> sp1, Dictionary<string, double> sp2)
{
    double distance = 0;
    object lockableObject = new object();

    // CAUTION: may create a large list!
    var keys = sp1.Keys.ToList();

    var partitions = Partitioner.Create(0, keys.Count);

    Parallel.ForEach(partitions, range =>
        {
            double subtotal = 0;

            for (var i = range.Item1; i < range.Item2; i++)
            {
                double possibleValue = 0.0d;
                sp2.TryGetValue(keys[i], out possibleValue);

                double currentValue = sp1[keys[i]] - possibleValue;

                subtotal += currentValue * currentValue;
            }

            if (subtotal != 0.0)
            {
                lock (lockableObject)
                {
                    distance += subtotal;
                }
            }
        });

    // CAUTION: may create a large list!
    keys = sp2.Keys.ToList();

    partitions = Partitioner.Create(0, keys.Count);

    Parallel.ForEach(partitions, range =>
    {
        double subtotal = 0;

        for (var i = range.Item1; i < range.Item2; i++)
        {
            if (!sp1.ContainsKey(keys[i]))
            {
                subtotal += sp2[keys[i]] * sp2[keys[i]];
            }
        }

        if (subtotal != 0.0)
        {
            lock (lockableObject)
            {
                distance += subtotal;
            }
        }
    });

    return distance;
}

I have to run off to a meeting very soon, so apologize that I did not chop the one method up into 3 pieces. As is, it looks kind of ugly as one big code dump.

Admittedly, the biggest downside to this is memory. Dumping a dictionary's KeyCollection.ToList() can build an extremely large list of keys. But it should improve performance.