vp-tree search demo

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.
This database includes loading... random cities. The size of the data is approximately 1.8 Mb. Including more cities would not make the search really longer, but the full database + vp-tree data would take more than 100 Mb.
A naïve algorithm would compare the query coordinates to each one of the loading... cities to find the closest. With a vp-tree, only ≈ 100 comparisons are needed.

Search nearest cities by coordinates

Latitude: Longitude:

You can use decimal (-1.511393) or degree-minute-second-NESW (1° 30′ 41″ W) notations.

Suggestions : North Pole South Pole Mont Saint-Michel Brihadeeswarar Temple Kilimanjaro

0 distance comparisons (0 s)

[more results] [less results]

#	Distance (km)	Name	Country	Latitude	Longitude
1
2
3
4
5

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.