algorithm - 动态聚合集群？平面上的点

Question

问题:

我有数百万 (10+) 个标记，每个标记都有不同的字段:

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

现在，我希望每个集群都具有以下聚合数据:

 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)

集群是根据标记的纬度、经度(距离方面)和缩放级别(整数)创建的。

无问题部分(**):

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

问题来了:

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

问题:

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.

将:

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

整个想法是预先处理大量数据和计算，这样用户就可以操作它而无需在他这边或服务器端进行计算(因此客户端集群不是解决方案，融合表作为嗯)

非常欢迎代码示例。

Answer 1

Hadoop 适用于预处理，不适用于在线(“实时”)操作。

希尔伯特曲线和 k-d-trees 比常规的网格文件/四叉树更复杂，实际上对您的用处更少。优化树以完全匹配您的可视化缩放级别!然后你可能根本不做任何“聚类”就走了，而只是可视化适当的四叉树单元格。

毕竟，您的空间数据只有 2d，因此所有 2d 方法都可以正常工作。而且您非常了解值范围，因为地球不会改变大小。这就是 Google map 速度如此之快的原因:它们使用可以缓存、高效服务和预生成的固定图 block 。

鉴于您可能不需要 ACID 和事务以及这些高级功能，使用其中一种被大肆宣传的 NoSQL 数据库似乎是合理的。