This demo shows how the vp-tree algorithm
allows to search nearest neighbors
in a huge database without actually comparing all items to the query.
I know the blue lines representing the distances should be great circle arcs and not just straight lines. Maybe I will fix this, some day. The important thing
to note is that the distances are correctly computed with Vincenty's formula
This database includes 51651 random cities. The size of the data is approximately 1.8 Mb. A naïve algorithm would compare the query coordinates to
each one of the 51651 cities to find the closest. With a vp-tree, only ≈ 100 comparisons are needed.
is used). No plug-in,
not event WebGL
City data created by MaxMind
and available from their site.
Distances are computed with Movable Type Scripts' implementation of the Vincenty formula
The vp-tree was pre-computed with a bucket-size of 10 cities.