一种PMR四叉树空间索引效率分析模型的研究

一种PMR四叉树空间索引效率分析模型的研究

一种PMR四叉树空间索引效率分析模型的研究

蒋

华

（桂林电子科技大学计算机系，广西桂林５４１００４）

Ｅ－ｍａｉｌ：ｊｉａｎｇｈｕａ０７７３＠１２６．ｃｏｍ

摘

要：空间索引效率分析模型技术在每一个商业应用中都会有一套特定的分析模型和评判标准，并且评估模式的指标

和权重带有很大的主观性，需要引入科学方法来确定有效指标。探讨了针对ＰＭＲ四叉树索引的空间索引效率分析的特殊案例，将最优化技术引入到空间索引效率分析中，使得空间索引的性能评价有了一定的理论依据。关键词：空间数据；效率分析模型；多目标优化文章编号：１００２－８３３１（２００６）３５－０１６６－０２

文献标识码：Ａ

中图分类号：ＴＰ３１１．１３

ＥｆｆｉｃｉｅｎｃｙＡｎａｌｙｓｉｓＭｏｄｅｌＲｅｓｅａｒｃｈｏｆＰＭＲＱｕａｄｔｒｅｅＳｐａｔｉａｌＩｎｄｅｘ

ＪＩＡＮＧＨｕａ

（ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＧｕｉｌｉｎＵｎｉｖｅｒｓｉｔｙｏｆＥｌｅｃｔｒｏｎｉｃ

Ｔｅｃｈｎｏｌｏｇｙ，Ｇｕｉｌｉｎ，Ｇｕａｎｇｘｉ５４１００４，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：Ｔｈｅｅｆｆｉｃｉｅｎｃｙａｎａｌｙｓｉｓｍｏｄｅｌｔｅｃｈｎｏｌｏｇｙｏｆｓｐａｔｉａｌｉｎｄｅｘｈｏｌｄｓａｎｅｓｐｅｃｉａｌａｎａｌｙｓｉｓｍｏｄｅｌａｎｄｊｕｄｇｅｍｅｎｔｓｔａｎｄａｒｄｉｎｂｕｓｉｎｅｓｓ，ｉｎａｄｄｉｔｉｏｎ，ｔｈｅｓｅｉｎｄｅｘｅｓｏｆｅｖａｌｕａｔｉｏｎｍｏｄｅａｒｅｓｅｖｅｒｅｓｕｂｊｅｃｔｉｖｅ，ａｎｄｔｈｅｓｅｉｎｄｅｘｅｓｍｕｓｔｂｅｃｏｎｆｉｒｍｅｄｂｙｓｃｉｅｎｔｉｆｉｃｍｅｔｈｏｄ．ＴｈｅｐａｐｅｒｄｉｓｃｕｓｓｅｓａｎｅｓｐｅｃｉａｌｃａｓｅｏｆＰＭＲｑｕａｄｔｒｅｅｉｎｄｅｘｏｆｓｐａｔｉａｌｉｎｄｅｘｅｆｆｉｃｉｅｎｃｙａｎａｌｙｓｉｓ，ｂｅｃａｕｓｅｏｆｏｐｔｉｍｉｚａｔｉｏｎｔｅｃｈｎｏｌｏｇｙ，ｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｓｐａｔｉａｌｉｎｄｅｘｈｏｌｄｓａｃａｄｅｍｉｃｆｏｕｎｄａｔｉｏｎ．Ｋｅｙｗｏｒｄｓ：ｓｐａｔｉａｌｄａｔａ；ｅｆｆｉｃｉｅｎｃｙａｎａｌｙｓｉｓｍｏｄｅｌ；ｍｕｌｔｉ－ｔａｒｇｅｔｏｐｔｉｍｉｚａｔｉｏｎ

１引言

目前，空间索引效率分析模型技术非常不成熟，每一个商

据［４，５］。当某个对象的插入导致一个ＰＭＲ四叉树块内对象的个数超过了用户自定义的一个分裂门限ｔ时，该四叉树块就要被分裂。如果对象ｏ的插入导致叶块ｂ中对象的个数超过了ｔ，则

业应用都会有一套特定的分析模型和评判标准，并且评估模式的指标和权重带有很大的主观性，需要引入科学方法来确定有效指标，并建立准确的定量模型来解决空间索引效率分析的问基于这种情况，探讨空间索引效率分析模型的问题也就显题［１］。

得相当重要。在众多的评估分析方法里，必须寻找到一种既能有效地计算和转换样本数据，又能对多约束多目标的结果进行优化处理的方法。由于非线性多目标优化技术的特征比较好地与空间索引效率分析问题的特征相吻合，本文就采用一种新的最小加权偏差的方法［２］，通过把多目标转化为与之相关的单目标（数值）最优化问题，经多目标最优化的归一化处理，最终综合成一个统一的总目标，可用其偏离优化方案的程度来度量其优化的优劣；借助丰富的非线性规划计算方法，求解权重（时间、Ｉ／Ｏ成本等）未知情况下的多目标类型的空间索引效率分析问题，从而达到求解最佳效率的目的。

ｂ就不再是最大的划分层次，它会被分裂，ｂ中的对象（包括ｏ）

就会被插入到新创建的子块，并规定那些子块不会再进一步分裂，即使这时它们所包含的对象多于ｔ。不立即分裂新构造的叶块的基本原理是避免过度分裂，即防止当一个四叉树块内有几个相距很近的对象时要分裂这个结点多次。因此，深度为Ｄ的叶块能包含的对象可达到ｔ＋Ｄ，根的深度为０（在最大层次的叶块的对象个数没有限制）。其主要的步骤是将二维空间信息映射为一维数据，由线性索引管理空间索引。映射过程也就是查找覆盖空间目标的最小索引矩形的过程，然后对每个空间对象建立索引项，将其写入索引文件（或索引表）里，当区域查询时，先计算出涉及哪些索引块，再取出索引块中对应的空间对象，形成结果集。如何分裂结点和映射数据将使索引效率有很大的差异［５］，在进行索引效率分析的过程中，就是要找到相对优化的一个解集。

２ＰＭＲ四叉树索引

ＰＭＲ（ＰｏｌｙｇｏｎＭａｐＲａｎｄｏｍ）四叉树是一种基于边的索引

３基于多目标优化技术的效率分析模型

当在空间索引效率分析中的某种目标解的计算已经得到

结构［３］，其含义是指控制每个结点中信息的数量，能存储任意类型的空间对象。这种方法的初始结构是一个空白的块，然后，线段被一条一条地插入到块中。当插入的线段数目到达一个预先设定的阈值时，块被分割成４个大小相等的子块，这种操作过程一直继续到所有的线段都被插入时为止。

充分地验证的同时，由于现实中的评估模型绝大多数是非线性的，在多目标优化中将多目标综合成一个能从总体上衡量优劣的总目标，然后由此优选出最佳方案［１］。

对于一个多目标最优化问题（ＭＯＰ）：

ＰＭＲ四叉树采用一对分裂和合并规则来动态维护数

基金项目：国家自然科学基金资助项目（５０１７５０７０）。

：（）男，，，：Ｍｉｎｉｍｉｚｅ（ｆ１（ｘ），ｆ２（ｘ），…，ｆｐ（ｘ））Ｔ

１６６２００６．３５计算机工程与应用

一种PMR四叉树空间索引效率分析模型的研究

Ｓ．ｔｇｉ（ｘ）≤０ｈｊ（ｘ）＝０

ｉ＝１，２，…，ｍｊ＝１，２，…，ｓ

（１）

ＭｉｎＳ．ｔ

$$Ｔ（ｘ，ｘ，ｘ）Ｎ（ｘ，ｘ，ｘ）ｄｘｄｘ

１

２

３

１

２

３

１

%’’’&’’’(

２

（７）

其中Ｘ＝（ｘ１，ｘ２，…，ｘｎ）Ｔ是欧氏空间Ｒｎ中的ｎ维向量，称为决策向量。ｘ所在的空间称为决策空间。ｆｉ（ｘ）称为子目标函数，ｐ维向量（ｆ１（ｘ），ｆ２（ｘ），…，ｆｐ（ｘ））Ｔ所在的空间称为目标空间。ｇｉ（ｘ）称集合Ｘ＝｛ｘ∈Ｒｎ｜为不等式约束函数，ｈｊ（ｘ）称为等式约束函数。

５≤ｘ１≤２０

２≤ｘ２≤１２ｘ３［０，１］

（８）

设计变量说明：公式（７）为最优化的目标函数，其中：Ｔ（ｘ１，

ｇｉ（ｘ）≤０，ｈｊ（ｘ）＝０，ｉ＝１，…，ｍ，ｊ＝１，…，ｓ｝是由约束函数确定的决

策变量的取值范围，称为可行域或约束集。

研究多目标最优化问题的是把它转化为与之相关的单目标（数值）最优化问题，通过多目标最优化的标量化处理，最终

Ｔ

综合成一个统一的总目标。设向量ω＝（ω１，ω２，…，ωｐ），作向量

ｘ２，ｘ３）为求解执行时间的函数项，Ｎ（ｘ１，ｘ２，ｘ３）为求解Ｉ／Ｏ操作

次数的函数项。公式（８）为约束条件，其中：ｘ１为最大深度，ｘ２为分裂门限，ｘ３为０＝权重取舍为线性，为１＝权重取舍为无量纲化

处理。

经过７次，每次历时１９３ｍｉｎ左右的计算， …… 此处隐藏：5981字，全部文档内容请下载后查看。喜欢就下载吧 ……