Hacker News Reader

You just need "distance" in the k means to be more general than just using the euclidean distance between coordinates, you need a norm appropriate for the space you are working in. Haversine distance should be fine for this application.

View on HN

Yes, but that's harder to implement.

Spherical kmeans is much simpler. A simple cos distance between vectors.

I don't remember exactly what I did or how it maps to spherical k-means. One modification was to use a version of the k-means algorithm but doing clustering not by fixed size but by fixed distance. The other was measuring distance by what the map coordinates would be rather than the lat/long coordinates. The last thing was rather than using a euclidean distance which gives circular neighborhoods, we used max(∆x, ∆y) which gives square neighborhoods. Clusters were pre-calculated or else we would have made rectangular neighborhoods with the proportions of the viewport window on the map. In retrospect, it might have made sense to do client-side clustering for more detailed zoom levels where n would have been relatively small and we could have gotten that as well.

Reply on news.ycombinator.com