Hacker News Reader

I did a Google map of US car dealerships for a former employer. When zoomed out dealerships would be clustered together using a modified k-means clustering. I had to do a lot of non-trivial coding to handle the variance in how latitude is distorted in Alaska vs the continental US. To this day, that was the algorithmically most interesting coding that I've done.

View on HN

Spherical kmeans is your friend there. It's overkill in a lot of cases, but perfect for that one.

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.

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