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.
All cities are displayed in 3D in real-time. JavaScript only (a
web worker 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.