1.3.3　地理要素的层次化模型

空间数据与非空间数据在近似查询处理中主要差异在于空间数据的基本元素间存在显式的内部关系,例如顶点的序列构成线对象,线对象的序列构成面对象及其他复杂组合对象。因此采样过程中所有的空间对象单元间的内部结构必须得以保持。这些内部结构包括线对象中顶点的先后次序、组合对象中线对象的先后次序、线对象间的拓扑关系等。(https://www.daowen.com)

选择一个正整数k,将D内元素进行划分以形成k个子集,每个子集为D i,1,且满足,对每个数据子集进行数据操作Opr,得到的结果记为R i,1＝Opr(D i,1),并对每个数据子集D i,1进行简化至最简单形式形成,同时对简化的进行数据操作,获得的结果记为使用距离函数度量R i,1与的差别记录及εi,1,对于每个集合D i,1继续迭代上述步骤,直至每个集合的元素个数降为最小值,最终形成具有嵌套关系的一系列集合及其伴随的误差值ε0,0,εi,1,…,εi,h,其中h＝O(log kn),n＝|D|为原始数据集合元素个数。根据这一迭代过程,可以将D在迭代划分的过程中形成的嵌套集合映射为一个层次结构,此层次结构即可用于处理针对数据操作Opr的近似查询,并报告近似结果的误差上界。