一种PMR四叉树空间索引效率分析模型的研究
- 格式：pdf
- 大小：234.62 KB
- 文档页数：3
一种ＰＭＲ四叉树空间索引效率分析模型的研究
蒋 华
（桂林电子科技大学计算机系，广西桂林５４１００４）
Ｅ—ｍａｉｌ：ｊｉａ“ｇｈｕａＯ７７３＠１２６．ｃｏｌｎ
摘要：空间索引效率分析模型技术在每一个商业应用中都会有一套特定的分析模型和评判标准，并且评估模式的指标 和权重带有很大的主观性，需要引入科学方法来确定有效指标 探讨了针对ＰＭＲ四又树索引的空间索引效率分析的特
殊案例，将最优化技术引入到空间索引效率分析中，使得空间索引的性能评价有了一定的理论依据。
关键词：空间数据：效率分析模型；多目标优化
文章编号：１００２—８３３１（２００６）３５—０１６６—０２ 文献标识码：Ａ 中图分类号： ｒＰ３１１．１３
Ｅｆｆｉｃｉｅｎｃｙ Ａｎａｌｙｓｉｓ Ｍｏｄｅｌ Ｒｅｓｅａｒｃｈ ｏｆ ＰＭＲ Ｑｕａｄｔｒｅｅ Ｓｐａｔｉａｌ Ｉｎｄｅｘ
Ｊ ＮＧ Ｈｕａ
（Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｇｕｉｌｉｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｅｌｅｃｔｒｏｎｉｃ
Ｔｅｃｈｎｏｌｏｇｙ，Ｇｕｉｌｉｎ，Ｇｕａｎｇｘｉ ５４ １ ００４，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ： ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ａｎａｌｙｓｉｓ ｍｏｄｅｌ ｔｅｃｈｎｏｌｏｇｙ ｏｆ ｓｐａｔｉａｌ ｉｎｄｅｘ ｈｏｌｄｓ ａｎ ｅｓｐｅｃｉａｌ ａｎａｌｙｓｉｓ ｍｏｄｅｌ ａｎｄ ｊｕｄｇｅｍｅｎｔ ｓｔａｎｄａｒｄ ｉｎ ｂｕｓｉｎｅｓｓ，ｉｎ ａｄｄｉｔｉｏｎ，ｔｈｅｓｅ ｉｎｄｅｘｅｓ ｏｆ ｅｖａｌｕａｔｉｏｎ ｍｏｄｅ ａｒｅ ｓｅｖｅｒｅ ｓｕｂｊｅｃｔｉｖｅ，ａｎｄ ｔｈｅｓｅ ｉｎｄｅｘｅｓ ｍｕｓｔ ｂｅ ｃｏｎｆｉｒｍｅｄ ｂｙ ｓｃｉｅｎｔｉｆｉｃ ｍｅｔｈｏｄ． Ｆｈｅ ｐａｐｅｒ ｄｉｓｃｕｓｓｅｓ ａｎ ｅｓｐｅｃｉａｌ ｃａｓｅ ｏｆ ＰＭＲ ｑｕａｄｔｒｅｅ ｉｎｄｅｘ ｏｆ ｓｐａｔｉａｌ ｉｎｄｅｘ ｅｆｆｉｃｉｅｎｃｙ
ａｎａｌｙｓｉｓ，ｂｅｃａｕｓｅ ｏｆ ｏｐｔｉｍｉｚａｔｉｏｎ ｔｅｃｈｎｏｌｏｇｙ，ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｓｐａｔｉａｌ ｉｎｄｅｘ ｈｏｌｄｓ ａｃａｄｅｍｉｃ ｆｏｕｎｄａｔｉｏｎ，
Ｋｅｙ ｗｏｒｄｓ：ｓｐａｔｉａｌ ｄａｔａ；ｅｆｆｉｃｉｅｎｃｙ ａｎａｌｙｓｉｓ ｍｏｄｅｌ；ｍｕｌｔｉ—ｔａｒｇｅｔ ｏｐｔｉｍｉｚａｔｉｏｎ
ｌ 引言
目前，空间索引效率分析模型技术非常不成熟，每一个商 业应用都会有一套特定的分析模型和评判标准．并且评估模式
的指标和极重带有很大的主观性，需要引入科学方法来确定有 效指标，Ｊ｛ 建立准确的定量模 束解决空间索引效率分析的问 题ｆｌＩ。基于这种情况，探讨空间索引效率分析模型的问题也就硅
得相当重要。在众多的评估分析方法里，必须寻找到一种既能 有效地计箅和转换样本数据．又能刘多约束多目标的结果进行 优化处理的方法。由于非线性多目标优化技术的特征比较好地
与空间索引效率分析问题的特征相吻合．本文就采用一种新的 最小加权偏差的方法［２１．通过把多目标转化为 之相关的单Ｈ 标（数值）最优化问题，经多目标最优化的归一化处理，最终综
合成一个统一的总目标，可用其偏离优化方案的桦度来度量其 优化的优劣：借助丰富的非线性规划计算方法，求解权重（时
间、Ｉ／Ｏ成本等）未知情况下的多目标类 的空间索引效率分 析问题，从而达到求解最佳效率的目的
２ ＰＭＲ四叉树索引
ＰＭＲ（Ｐｏｌｙｇｏｎ Ｍａｐ Ｒａｎｄｏｍ）四义树是・种基丁边的索引 结构［３１，其含义是指控制每个结点中信息的数量．能存储仃意类
型的空间对象。这种方法的初始结构足一个空白的块．然后．线 段被…条…条地插入到块中。 插入的线段数目到达一个预先
设定的阈值时，块被分割成４个大小相等的子块，这种操作过 程一直继续到所有的线段都被插入时为止。
ＰＭＲ四叉树采用一对分裂和合并规则来动态维护数
基金项目：国家自然科学基金资助项目（５０１７５０７０）。 作者简介：蒋华（１９６３一），男，副教授，博士，主要研究方向：空间数据库技术。
１６６ ２０ｏ６＿３５计算机１＝程与应用 据［４．５１。当某个对象的插入导致一个ＰＭＲ四叉树块内对象的个 数超过了＿Ｉ＝｛＝ｊ户自定义的一个分裂门限 时．该四叉树块就要被 分裂。如果对象０的插入导致叶块ｂ中对象的个数超过了ｔ，则 ｂ就 再是最大的划分层次，它会被分裂，ｂ巾的对象（包括０） 就会被插入到新创建的于块，并规定那些子块不会再进一步分
裂，即使这时它们所包含的对象多于 。不立即分裂新构造的叶 块的基本原理是避免过度分裂．即防止当一个四叉树块内有几 个相距很近的对象时要分裂这个结点多次。因此，深度为Ｄ的
叶块能包含的对象可达到ｔ＋Ｄ．根的深度为Ｏ（在最大层次的叶 块的对象个数没有限制）。其主要的步骤是将＝维空间信息映
射为一维数据．由线性索引管理空 索引。映射过程也就是责 找镬盖空间目标的最小索引矩形的过程．然后埘每个空间对象 建立索引项，将其写入索引文件（或索引表）里，当区域查询时， 先计箅｝Ｈ涉及哪些索引块．再取出索引块中对应的空间对象，
形成结果集。如何分裂结点和映射数据将使索引效率有很大的 差异［５１，在进行索引效串分析的过程巾，就是要找到相对优化的
一个解集．．
３基于多目标优化技术的效率分析模型
当住空间索引效率分析中的某种目标解的计算已经得到
亢分地验证的同时．由于现实巾的评估模型绝人多数是非线性 的，在多目标优化中将多Ｅｔ标综合成一个能从总体上衡量优劣
的总目标，然后由此优选 最佳方案Ｉ１ｌ。
对于一个多目标最优化问题（ＭＯＰ）：
Ｍｉｎｉｍｉｚｅ （ ） （ ），… （ ））
维普资讯 http://www.cqvip.com Ｓ．ｔ岛（ ）≤０ ｉ＝１，２，…，ｍ （１）
＾，（ ）：０ ｊ＝ｌ，２，…， 其 ｆ （ ， ，…， ， ） 是欧氏空问Ｒ ＩＪ的ｎ维向量，称为决策
最。 所存的宅问称为决策空间。ｆ（ｘ）称为子目标函数，Ｐ维
向量 （ ） （ ），… ．（ ）） 所在的空ｆｉｌｌ称为Ｈ标空间。昏（ ）称
为不等式约束函数，ｈｊ（ｘ）称为等式约束函数 集合Ｘ＝ Ｒ ｌ 韪（ ）≤０，＾，（ ）＝０， １，…，ｍ ＝１，…，ｓ Ｊ是由约束函数确定的决
策变量的取值范同，称为可仃域或约束集
研究多目标最优化问题的是把它转化为与之卡ｕ天的单目
标（数值）最优化『口Ｊ题，通过多Ｈ标最优化的标量化处理，最终 综合成一个统一的总目标。设向量ｃｔ，＝（山 ，山 ，…，（￡Ｊ ） ，作向茸
ｃ￡， ｊ厂（ ）的内积（点乘）可以得到一个数值 数：
ｃｔ， ）＝ （￡Ｊ ｆ（ｘ）
对数值（标量）微小化问题
三 ｍｉｎ￣ｏＩ厂（ｘ）＝ｍｉｎ 山 （ ） （２）
和多日标微小化问题式（１）之间的关系存在。 没有Ｐ个目标为 ，Ｕ＝１，２，…，Ｐ）；待选的方案有ｍ个为
ｐ ，（ １，２，…，ｎ ）。第ｉ个方案按各目标的原尺度计算的目标值 为 ，由公式（２）
Ｌ＿ （３） ｍａｘ（ 一ｍｌｎＦｏ） 将各个目标归一化十０～１之『日ｊ的数值，显然，这样的处理后的 目标值是尢昼纲的。
在Ｈ标矩阵转换成相对隶属度矩阵
＝（ ） （４） 以后，当取ｍｉｑ ＝＆， １，２，…，ｍ，为理想值时。就可定义相对理
想的方案为 ＝（ｇ ｇ２舒… ） （５） 方案（）越接近Ｇ，（Ｊ就越优，因此ｎ『ＪｌＪ茛偏离Ｇ的 Ｊ韭来 度量其优化的程度，这是最小加权偏差方法的实质所在。
、 方案ｉ通过加权将方集ｉ多目标转化成单目标时，冈为 茛权重是未知星，恨据公式（２）、（５），ｎ ｒ Ｊｌ Ｊ下列指标束描述：
（ｃ￡，）＝ （ ） （６） Ｊ 】 此，埘于给定的权前广口ｌ量 ， （ ）最小的对应方案为最 佳方案
为了尽量消除随机操作的影响。一般束说．每 成１０个非 劣解就卜了上一次得到的ｌ０个斛合并，对合许的集合进行支配
父系的比较，删除卡ｕ同的斛和被支 解，再次执仃聚类算法，最 终输ｍ １０个解，这个解将是优化解
时丁多Ｆ｛标优化问题，某些目标件能的改善将引起其他Ｈ
标性能的退化，决策者ｆｌ： 需要存这种改善 ｊ退化中进行妥 协，受各种客观条件的限制．这样的妥协足有限的 相对丁传统
的多目标优化方法．基于最小加枞偏差的方法，通过多日标的
无量纲化处理，求解权重术知情况＿卜的多Ｈ标非线性优化Ｉ＇口Ｊ题 的优点存丁可以为决策者提供住目标卒问巾分布相对均匀的
多个解，使决策者可以根据实际的需要进行选择。
４分析模型的应用
ＰＭＲ四叉树索引分析模型多目标优化函数（ＭＯＰ） Ｍｉｎ Ｊ Ｊ （ １， ２， ３），ｖ（ １， ２， ）ｄ Ｉｄ ２ （７）
ｆ５≤ ≤２０
５．ｔ｛２≤ ２≤１２ （８）
ｌ 【０，１ Ｊ 设计变量说明：公式（７）为最优化的目标函数，其中： （ ，
，Ｘ３）为求解执行时间的函数项，Ⅳ（ ｍ，Ｘ ）为求解１／Ｏ操作 次数的甬数项。公式（８）为约束条件，其 ｆＩ１Ｘ 为最大深度，Ｘ 为
分裂门限，Ｘ 为０＝权重取舍为线性，为１＝权重墩舍为无草纲化 处理。
经过７次．每次Ｊ打时１９３ ｒａｉｎ左右的计算。其ＰＭＲ四叉树
索引分析模型优化结果数据集按其评价级别的排序列表，如表 １所示：
表１ 按评价级别排序的优化结果数据集
５ 结果分析
从优化分析的结果数据看，序号为２的结果数据 最优， 其线段个数为２４６ ７４８，最大深度为ｌ３．分裂门限为５．Ｂ树的
大小为４ ４６５，相交线段数为４６５，执行时问为刚ｓ．１／Ｏ次数为 ７４５次 但在序弓 为６和序号为１４的结果数据中其最大深度 也为１３．分裂门限也为５，其线段个数还少于２号，它们的结果 数据还劣于２号数据 这说明最人深度和分裂门限不完全是空 问索引优化的睢 变量。还有线段的类 和线段之ｆｕＪ的相立个
数有关，并且每次优化分析时其优化解结果还有微弱变化。 这一现象表明：这个优化解巾具有一定的聚炎特性．它ｆｆＪ
的计箅 相ｌ 的条件 ，只有卡ｕ似的结果 ．当 优化解 ｌｔ取最 劣解为系数ｌ ００的话，其他各Ｉ 与评价结果的比率值。如表２ 所示：
表２ 评价结果与其他各项的比率值
从表２的数据町以看到，通过对ＰＭＲ四叉树索引的优化
汁葬，得到的优化解ｔ｛Ｊ．当线段的属性一定的情况 ，分裂¨限 是影响ＰＭＲ旧叉树索引的空 索引效卒的一个 要的因素．
其 要程度大于最人深度的５Ｏ％，分裂门限存５．５时为最优。
但是，并不是分裂门限越低越好，当分裂¨限低丁一定数值时， 索引的精度就达不到要求了。结果也表明：…・个空间对象在不
（下转２０２页）
计算机Ｊ二程 廊用２Ｏｏ６．３５
１６７ 维普资讯 http://www.cqvip.com
