网络拓扑距离的高效KNN查询

项目背景：

有些应用场景下，需要快速找到某个用户在网络中拓扑距离更近（跳数少，连接延迟低，传输速率快）的K个邻居节点，即KNN(K-Nearest Neighbor Query)。但是，这些方法对于数目多到全国级别，而且表示维数也稍高一些的网络节点，索引及KNN查询就成了一个挑战。现在需要完成一个索引全国用户IP-Geo-ISP数据，并可实现高效KNN查询的程序。

最终目标：

以腾讯提供的更详细IP库的部分数据，千万级别用户，在上面进行KNN查找的效率不低于单机100QPS；

思路及实现方案：

拓扑距离暂时使用地理位置的距离和节点之间是否属于同一个isp来近似度量。

首先使用geohash将数据分块，再针对分块后的数据用空间索引树进行索引，最后进行knn查询即可。

此外还有局部网络瘫痪的情况，只需对查询范围进行下更改即可。

已经完成的工作：

对数据用geohash进行分块。

对分块后的数据使用快速选择算法进行knn查询，对于随机生成的数据每秒可以完成100+次查询。

后面的计划：

将快速选择算法部分改成用kd树所有，进行knn查询，这样效率还会提高一个量级，达到最终的查询效率应该没问题。最终再使用腾讯的数据库进行下测试即可。