python - Server side clusterer for Google Maps

After doing a lot of research on different types of clustering coordinates (server side) I am still having problems with choosing the best approach for my project.

My requirements:

1. Ability to work with more than 1.000,000 coordinates.



2. Be able to filter coordinates by point of interest.


3. Support map zooming and dragging.


4. Fast


5. I can't use any third party services.

Here is what I found:

1. Region quadtree seems to the most suitable algorithm.


2. Geo hashing coordinates + Solr for quick retrieval/filtering of points (might only work with small set of data since the clustering will have to happen on the fly)

I would like to know how to deal with map zooming & dragging while maintaining fast response from the server. How can clusters be cached if the maps is dragged, zoomed? Some clusters can be pre-clustered for large areas (continents) but what if there are 10,000 points within once city?

My software stack is postgresql, python, django.