Understanding Vivaldi

Subtitled: Or so I hope!

As I mentioned before, in our code, we have Vivaldi, but the code was rather complex especially if you look at where (I think) it comes from this paper and this code.  I could not reconcile what was happening!  One thing I must recommend to anyone that is working on a group project or wants their work to continue after you leave, make sure the code you share is clean and document the algorithm (regardless of complexity).  If the code isn't clean, it may be difficult or impossible to understand the code.  If the algorithm isn't documented, you leave it up to the next guy to attempt to understand what you were doing and heaven forbid you did something non-standard try to figure out why.  No one is immune, I compared the Vivaldi paper and code and they are very different but it is nowhere documented why they made those changes!

Anyway onto how I understand Vivaldi.

Each point has position X and error E set to [0, ..., 0] and 1 respectively.

at node i: ProcessSample(Xj, Ej, latency_between_ij)
- distance = EuclideanDistance(Xi, Xj)
- relative_error = (latency - distance) / latency
// We square to give less weight to high error node
- le = Ei^2
- re = Ej^2
- new_error = relative_error * (le / (re + le)) + Ei * (re / (le + re))
- Ei = (19 * Ei + new_error) / 20
- SetInBounds(Ei, 0, 1)

- ForceVector = Xi - Xj
- if(PlaneDirection(ForceVector) < .0001)
- - ForceVector.Bump (just to move it a little from the origin)

- length = Direction(ForceVector)
- unit = 1.0 / length
- weight = .1 * (Ei /(Ei + Ej))
- ForceVector * (unit * weight * (latency - distance))
- Xi += ForceVector
- SetInBounds(Xi.Height, 100, 10000)

So to clarify some terms Euclidean Distance is ||Xi - Xj|| + Xi.Height + Xj.Height
Xi - Xj = Xi.Coords - Xj.Coords, Xi.Height + Xj.Height
SetInBounds ensure that the system stays stable

This differs from the paper by using a exponential weighted moving average instead of static dampers on the error and the introduction of the Bump also generation of the unit vector (in my mind) was a bit hazy.  This differs from the code in that the ForceVector is Xi - Xj instead of Xj - Xi, the latter would cause explosions since it actually moved us closer when we wanted to move away and away when we wanted to move closer.  Also the code had no notion of limiting the height, but in my experiments I have seen it explode.  Another strange feature in the code was the inverting of the ForceVector.Height, which I found when not doing improved results.  Sadly all my effort seems to be in vain as the results are similar to what was presented in the paper.

The next step is to integrate this with the Graph and use it to test potential shortcut optimizations we can make.  Interestingly, the king data set does not work that well with Vivaldi (> 70% of all to all pairs are within 15% of being accurate), but that will not deter my efforts!