Clustering Algorithm for Mapping Application

For a virtual earth application I've used the clustering described here. It's lightning fast and easily extensible.

Google Maps Hacks has a hack, "Hack 69. Cluster Markers at High Zoom Levels", on that.

Also, see Wikipedia on clustering algorithms.

You could look at indexing all your points using a QuadTile scheme, and then based upon the scale the further down the quad-splits you go. All similarly located points will then be near each other in your index, allowing the clustering to happen efficiently.

QuadTiles are an example of Morton Codes, and there is a python example linked from that wikipedia article that may help.