Vptree.js demo

Back to theProject home
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.

Rotate and hover the globe

There are 51651 dots on this globe, each one is a city.

Nearest cities

#Distance (km)NameCountryLatitudeLongitude
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.