dynamic aggregated clustering? points on plane
===

Problem:

I have millions (10+) of markers, each with various fields: 

     1. lat 
     2. lng   
     3. area (double)
     4. size (int)
     5. tolerance (double)
     6. lags (boolean)
     7. channel (boolean)
    ... (more)

Now, i want each cluster to have the following aggregated data:

     1. number of markers
     2. min area
     3. max area
     4. avg area
     5. min size
     6. max size
     7. avg size
     8. tolerance distribution (how many where of tolerance < X, other >=X < Y and >=Y <Z where X,Y,Z constants)
     ... (more)
clusters are created based on lat,lng of the markers (distance wise) and based on zoom level (int).

Non problematic part(**):

> Calculating the clusters for all zoom-level, regardless of the
> condition "all-in". This is done by creating a tree and the fetching of clusters for the user is straight-forward.

Now for problem:

> Users can query based on the marker fields, e.g "show me all markers
> that their area > K and lags = true". For this query alone, a whole
> new clusters tree needs to be created. If he changes the query "show
> me all markers that their area > K.0001 and lags=true" and new tree
> will have to be created.  I don't want to calculate such tree for
> every user's query and not to store it in-memory (not sure if it's
> possible).

Question:

    What approach should be taken ?
    given the complexity of calculation X # of markers 
    (fields inside) X speed factor. 
    I was thinking that there's some sort of way to use  the 
    "all-in" clusters calculation(**), as it gives me ALL the markers and clusters and from 
    there to manipulate in some elegant way.
Will:
 

     - space-filling-curve (hilbert) can help? how?  
     - DB approach (what DBand why?)
     - k-d tree ?

The whole idea is to handle large amount of data and calculation pre-hand so the user can manipulate it with-out calculating it on his side or the server-side (so client side clustering is not a solution, fusion tables as well)

Code samples are more than welcome

Thank you. 




