图内节点找邻居

Question

向大家请教几个问题，跟实际操作相关滴

1.现在有大量点集，用经纬度表示，分布特征未知，想将这些点进行聚类，找出每个聚类的半径，圈出一个最小外接圆，有没有什么可行的方法呢

2.有这样一些记录(id1,id2)，表示id1和id2有关联，所有这些记录构成了一个图的形式，对所有id都需要进行处理后，量很大的情况，有没有一种效率高的方法找出某个id的所有邻居

Answer 1

1. 聚类的方法很多，kmeans （或kmeans++）什么的，如果你只是单纯用坐标来聚类的话，实现很简单，有现成库可以直接用。（但是经纬度的话 可能要特殊处理下）

2. 取决于这个量到底有多大。假设有N个点，如果点对的量接近N*N，那么没有办法，你只能用邻接矩阵，不过你可以用一个bit来表示每个点，这样就只需要N*N/8个字节。如果量比较少的话，可以用邻接表来实现（查询速度快）。另外，如果这些关系只跟距离有关的话，Quadtree这个数据结构就可以实现，你只要按照这个数据结构组织存储点就行了（其实直接用MongoDB的Geospatial Index就行）。