学过计算机的同学能不能猜出上面的图可视化了啥?哈哈,是不是感觉很熟悉?这幅图由Eric Fischer所作,可视化了在世界地图上所构造的一棵k-d tree。这棵k-d tree针对的数据是google Picasa用户在地理上的分布数目。k-d tree听上去学术,但是它的构造并不复杂:先在地图上,按照用户数量,平均切分为二份;然后对于每一份,按照用户数量,再往下切分;这样递归切分,直到每一份所对应的用户数目小于一个阈值,或者矩形小于某个尺寸。对于每个矩形,算法总是沿平行于短的边切分这个矩形。

这样构造的k-d tree的目的是啥?不难发现,每个矩形对应于的用户数目基本上是一致的,也就是所对应的照片数据量也基本一致。如果按照每个矩形来组织管理数据,就可以大大提供数据搜索的效率。下面两张放大的图对应于美国和欧洲的划分,我们不难发现矩形的大小跟美国或者欧洲可能的Picasa用户分布基本一致。比如,美国的东西两岸划分就要密集的多。

下面这部分对应于东亚地区。这更加容易让我们验证这棵k-d tree的正确性:日本,韩国和中国台湾,划分很密集,因为在这些地区,很多人使用Picasa,需要把区域划分的很小,才能让每个小块的用户数小于阈值。而中国大陆,虽然人口众多,但是Picasa用户稀少,所以稍微划分一下,就能使每小块的用户数小于阈值。
如果没有写过k-d tree的同学,或者想复习一下的同学,可以参观一下Eric同学的源代码,看他如何用86行代码实现这个递归划分算法。

© 2011, 视物 | 致知. All rights reserved.

Related Posts: