《表3 不同编码长度、数据量和图形分布状态下的公共边提取时间》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《一种基于单调链和Geohash索引的公共边裂缝处理算法》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

ms

Geohash编码在算法中的作用是减小公共点的搜索范围．Geohash编码长度L决定了搜索空间大小，是影响算法时间效率的重要因素．为测试编码长度L对算法时间效率的影响，本文用1～9的编码长度对3组数据集进行了公共边提取实验，其实验结果如表3所示．可以看出，随着编码长度L的增加，提取公共边的时间总体上呈先下降后上升的趋势．这是因为随着编码长度L的增加，每个编码所对应的矩形区域和落入该区域的顶点数越来越小，也就是说Geohash索引表中的顶点链表越来越短，查找公共点所花费的时间越来越少．在极限状态下，每个编码所对应的矩形区域最多只包含1个数据点，此时公共点的查找时间最短．此后，编码长度的增加对于公共点查找时间没有影响，但构建索引的时间一直随编码长度单调递增．因此，提取公共边的时间总体上呈先下降后上升的趋势．在实际应用中，由于数据采集精度的限制，无论数据的体量大小、稀疏程度，编码长度较为合适的取值范围为4～6．例如，数据集Data1，顶点数在万级规模，编码长度为5时，提取公共边耗时最小，为45.72 ms；数据集Data2，顶点数在十万级规模，编码长度为4时，提取公共边耗时最小，为102.31 ms；数据集Data3，顶点数在百万级规模，编码长度为5时，提取公共边耗时最小，为1 246.22 ms.