5.1.2 复杂度分析
对于顶点层次结构,要素更新的处理方案是直接使用新要素生成一个新的顶点层次结构。其问题在于,若该要素更新所涉及的顶点数量为k,采用整体重建的方式进行更新,其代价将与实际更新的数据量无关,而只与要素的总数据量相关。对于大规模的地理要素而言,要素更新可能只涉及细小的局部,这种情形在VGI应用中很常见,例如在数万个顶点中移动了某个顶点的位置或者插入若干新的顶点。因此,在这种情况下,如果每次都重建整个顶点层次结构,将给数据库带来极大的性能开销,削弱数据库的响应能力。因此,为了提高更新性能,对于局部发生变化的地理要素,应当仅对其局部的顶点层次结构进行更新,未发生变化的区域不进行更新。更新域的大小决定了实际的操作代价,并且其数据无须被读写,因此能够降低更新的资源消耗。
地理要素更新后,空间查询引擎需要将要素的顶点层次结构进行相应更新。顶点层次结构的更新包括两类操作,一是顶点误差的计算,主要操作是数据的读取与运算;二是计算结果及新信息的记录,主要操作是数据的写入。由于I/O操作与计算操作具有不同的特点与分析模型,因此将这两类代价分别考虑,前者称为I/O代价C w,后者称为计算代价C c,总的更新代价函数为两者之和,即C＝C c+C w。若设原序列的顶点数量为n,新序列的顶点数量为k,将更新代价函数的取值约束在下列范围内
可以看出,计算代价C c不超过线性复杂度,数据写入代价C w不超过新加入顶点序列的线性复杂度与原序列的对数复杂度之和。假定要素更新的位置是随机分布的,则单次更新代价的约束则为
假设原顶点序列中的顶点都有相同的概率在该位置被插入顶点、被修改或被删除,可以进行摊平分析。若原序列长度为n,序列插入位置与根节点距离为l,树的高度h＝log n,则l的分布函数为(https://www.daowen.com)
距离根节点为l的顶点,在进行插入操作时,其计算复杂度为O(k log n),因为其插入需要经过log n个节点才能到达叶节点位置,最坏情形下,其I/O复杂度为O(log n)。在删除操作时,其摊平的计算复杂度为
I/O复杂度为O(log n)。在修改操作时,其摊平复杂度与删除操作的摊平复杂度相同。顶点移动的代价包括两方面,即作为边界点的更新代价与作为序列内部点的更新代价,其代价之和为O(h+n/2h)。顶点增加的代价与顶点序列的长度呈对数相关。
在序列递归划分中,某序列的采样点的变化所引发的重建代价比单纯的在序列内重新计算误差值的代价高。若某一个叶节点所对应的顶点的位置变化,则需要重新计算该顶点所处的O(log n)段序列中的误差值,其更新代价与树高度呈线性关系。而对于序列递归划分的划分点,则以该划分点为边界的所有子序列都需要重新计算误差,其更新代价与该点所首次划分的顶点序列大小呈线性关系,即O(n/2h),其中h为顶点作为边界点在层次结构中的高度。
