总第２８０期 ２０１３年第２期 计算机与数字工程 Ｃｏｍｐｕｔｅｒ＆Ｄｉｇｉｔａｌ Ｅｎｇｉｎｅｅｒｉｎｇ Ｖｏｌ＿４ｌ Ｎｏ．２ １９６ ＩＲＴ树索引结构的研究 朱德龙李松董义明籍祥李海岫 １５００８０） （哈尔滨理工大学计算机科学与技术学院摘要哈尔滨论文针对Ｒ树在处理一些特定空间数据对象集时的不足，研究了基于最小外接直角等腰三角形（ＭＩＲＴ）的新的索引结构一 ＩＲＴ树 探讨了ＩＲＴ树的空间平面划分和空间数据结构特征，给出了ＩＲＴ树的节点算法和搜索算法。进一步对ＩＲＴ树和Ｒ树进行了 比较分析。由分析可知，对于一些特定数据集，ＩＲＴ树在查询准确率、数据存储和空白空间冗余方面均有一定的优势。 关键词Ｒ树；空问索引；ＩＲＴ树；节点 ＴＰ３１１ 中图分类号Ｒｅｓｅａｒｃｈ ｏｆ ＩＲＴ Ｔｒｅｅ Ｉｎｄｅｘ Ｓｔｒｕｃｔｕｒｅ ＺＨＵ Ｄｅｌｏｎｇ ＬＩ Ｓｏｎｇ ＤＯＮＧ Ｙｉｍｉｎｇ Ｊ Ｉ Ｘｉａｎｇ ＬＩ Ｈａｉｓｈｅｎ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ １５００８０） Ａｂｓｔｒａｃｔ Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｄｅｆｉｃｉｅｎｃｙ ｏｆ ｔｈｅ Ｒ ｔｒｅｅ，ｔｈｅ ＩＲＴ ｔｒｅｅ ｗａｓ ｓｔｕｄｉｅｄ ｂａｓｅｄ ｏｎ ｔｈｅ ｍｉｎｉｍｕｍ ｉｓｏｓｃｅｌｅｓ ｒｉｇｈｔ ｔｒｉａｎｇｌｅ（ＭＩＲＴ）． Ｔｈｅ ｓｐａｔｉａｌ ｐｌａｎｅ ｐａｒｔｉｔｉｏｎ ａｎｄ ｔｈｅ ｓｐａｔｉａｌ ｄａｔａ ｓｔｒｕｃｔｕｒｅ ｗｅｒｅ ｄｉｓｃｕｓｓｅｄ．Ｔｈｅ ｓｐｌｉｔｔｉｎｇ ａｌｇｏｒｉｔｈｍ ａｎｄ ｔｈｅ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ｗｅｒｅ ｇｉｖｅｎ．Ｔｈｅａｔ ｒｉｃａ１ ａｎａｌｙｓｉｓ ａｎｄ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ＩＲＴ ｔｒｅｅ ｈａｓ ａｄｖａｎｔａｇｅｓ ｏｎ ｓｅａｒｃｈ ａｃｃｕｒａｃｙ，ｄａｔａ ｓｔｏｒａｇｅ ａｎｄ ｂｌａｎｋ ｒｅｄｕｎｄａｎｃｙ ｆｏｒ ｓｏｍｅ ｄａｔａｓｅｔｓ ｃｏｍｐａｒｅｄ ｗｉｔｈ Ｒ ｔｒｅｅ． Ｋａｙ Ｗｏｒｄｓ Ｒ ｔｒｅｅ，ｓｐａｔｉａｌ ｉｎｄｅｘ，ＩＲＴ ｔｒｅｅ，ｎｏｄｅ ｓｐｌｉｔ Ｃｌａｓｓ Ｎｕｍｂｅｒ ＴＰ３１ １ １ 引言 Ｒ树ｌｌ 及Ｒ树家族ｌ２］（ｉｎ Ｒ＊树、ＴＰＲ树、ＳＲ树等）是 空问数据对象组织和查询的重要空间索引结构，近年来在 空间查询ｌ３ 和空间聚类分析＿８］等领域起着日益重要的作 用。有关Ｒ树及其变种树的研究受到了大家广泛的重视。 Ｒ树的建树基础是最小外包矩形（ＭＢＲ）。在Ｒ树中 存放的数据并不是原始数据，而是这些数据的最小外包矩 形（ＭＢＲ），空间对象的ＭＢＲ被包含于Ｒ树的叶节点中。Ｒ 树中的各层节点以递归的方式对数据集空间进行划分。其 环境和特定的查询需求，本文研究了一种空间索引树 ＩＲＴ树，探讨了ＩＲＴ树的空间组织和节点结构，给出了节 点算法和搜索算法。 ２ ＩＲＴ树索引结构与基本操作算法 ２．１ ＩＲＴ树索引结构 与Ｒ树类似，ＩＲＴ树足一种多级高度平衡树。在ＩＲＴ 树中存放的数据是最小外接等腰三角形（ｍｉｎ ｉｓｏｓｃｅｌｅｓ ｒｉｇｈｔ ｔｒｉａｎｇｌｅ，ＭＩＲＴ），叶子节点存放空间数据对象的 每一个非叶节点本身代表数据集空间中的一个矩形，该矩 形为其子节点所代表矩形的ＭＢＲ。Ｒ树在数据组织和查 ＭＩＲＴ，中间节点存放包含ＭＩＲＴ的ＭＩＲＴ。ＩＲＴ树中的各 层节点以递归的形式对数据对象空间进行划分。非叶节点 由多个形如（ＩＲＴ，，ＮＤ ）结构的数据项组成，其中，ＩＲＴ 为与子节点相关的ＭＩＲＴ，ＩＮＤ 为指向子节点的指针； 而叶子节点由多个形如｛ＩＲＴ，Ｐ｝结构的数据项组成，其中， 询方面对于空间许多数据集是高效的。尤其是对于大量形 状近似空间矩形的空间数据对象且大部分数据对象子集分 布区域近似为空间矩形的情况，Ｒ树的优势是明显的。但 在许多空间环境中，空间数据对象的形状往往近似为三角 形，大量空间数据对象的聚类子集的区域往往也经常近似 为三角形。此时，再用ＭＢＲ进行数据对象的近似和聚类将 会产生大量的空白空间，Ｒ树节点中存储的空间信息与实 Ｐ为指向空间对象的具体数据指针，ＩＲＴ为对象Ｐ的 ＭＩＲＴ。ＩＲＴ树中的每个节点对应一个磁盘页面，ＩＲＴ树的 平面划分与数据结构如图１所示。 与Ｒ树类似，ＩＲＴ树自身主要具有以下特征： 际数据对象的空间信息偏差太大，从而导致利用Ｒ树及变 种树进行查询时会产生较大的误差，建树代价和查询代价 １）ＩＲＴ树的每个等腰直角三角形（ＩＲＴ）的两条直角边 均和一个全局坐标系的纵、横坐标轴平行，直角顶点处于左 下方。 均会急剧增大。为了弥补以上问题，针对一些具体的空间 ＊收稿日期：２０１２年８月３０日，修回日期：２０１２年１Ｏ月５日 基金项目：计算机专业卓越工程师的研究和创新能力培养（编号：ＧＢＣ１２１１０６２）；哈尔滨理工大学大学生创新创业训练计划项目（编 号：２０１２）；哈尔滨理工大学青年科学研究基金项目（编号：２０１１ＹＦ０１５）；黑龙江省自然科学基金资助项目（编号：Ｆ２０１１３４）资助。 作者简介：朱德龙，男，硕士研究生，研究方向：算法设计与数据库。李松，男，博士，副教授，硕士生导师，研究方向：数据库原理及应 用。董义明，男，研究方向：数据结构。籍祥，男，研究方向：算法理论与设计。李海岫，男，研究方向：软件分析与程序设计。 ２０１３年第２期 计算机与数字工程 １９７ （ｂ）ＩＲＴ树的数据结构 图１ ＩＲＴ树的平面划分与数据结构示例 由该特征可知，ＭＩＲＴ的三个顶点的空间信息可表示 为（ｚｏ， ），（－ｚ１， ），（ｚｏ，（ ｏ＋ｚ ）／２）。节点所存的每个 ＭＩＲＴ空间信息仅为三个数据，所需空间存储较少。 ２）ＩＲＴ树的每个叶节点的每条索引记录形式为｛ＩＲＴ， Ｐ），ＩＲＴ表示数据对象的最小外接等腰直角三角形，Ｐ为指 向空间对象的具体数据指针。 ３）若ＩＲＴ树的节点不是叶节点，则该节点至少有两个 子节点。 ４）若ＩＲＴ树的节点不是叶节点，则该节点的每个项的 记录形式为（ＩＲＴ，ＩＮＤａ ）。ＩＲＴ表示包含其子节点最小 外接等腰直角三角形的最小外接等腰直角三角形。 ５）除根节点外，每个节点包含的索引记录或包含的子 节点的个数均有上限和下限的。 ２．２ ＩＲＴ树索引结构的基本操作 在树索引结构的操作中，树节点的操作和树的查 询操作最为重要，本节重点给出了ＩＲＴ树的操作算法 和ＩＲＴ树的查询操作算法。 与Ｒ树类似，操作是当树的节点所包含的项的个 数超过上限后，按照一定的规则将该节点分为若干个部分。 子节点将会产生一些新的单元，使父节点包含的项的 数目增大，从而有可能引起父节点的溢出，利用规则继续对 父节点进行。显然，ＩＲＴ树的操作是递归进行的。 算法１给出具体的算法如下： 算法１ ＩＲＴ＿Ｓｐｌｉｔ（ｅ）（ＩＲＴ－树结点算法） 输入：需要的结点ｅ； 输出：后的ＩＲＴ－树； ｂｅｇｉｎ 判断节点ｅ是否溢出； ｉｆ ｅ溢出ｔｈｅｎ ｔｌ＋一ＳＰＩ ＩＴ１（Ｐ）； ｔｚ￣－ＳＰＬＩＴ２（Ｐ）； ｉｆ Ｐ是根结点ｔｈｅｎ 新建一个根节点Ｅ； ＩＮＤ￣ｉｌａ（Ｅ）一 １； ＩＮＤ （Ｅ）— ２； ｒｅｔｕｒｎ（Ｅ）： ｅｌｓｅ 将ｅ从ｅ的父节点的项中删除； ＦａｔｈｅｒＩｔｅｍ（ｅ）￣－－ｔｌ； ＦａｔｈｅｒＩｔｅｍ（ｅ）＋一 ２； ｉｆ ＦａｔｈｅｒＩｔｅｍ（ｅ）＞ＭＫ ｔｈｅｎ ＩＲＴ—Ｓｐｌｉｔ（Ｆａｔｈｅｒ（ｅ））； ｅｎｄ． ＩＲＴ树的查询操作即是给出待查区域，利用树索引结 构查出符合条件的数据项。算法２给出了ＩＲＴ树的搜索算 法如下： 算法２ ＩＲＴ＿Ｓｅａｒｃｈ（ＩＲＴ，Ｔ）（ＩＲＴ－树搜索算法） 输入：ＩＲＴ树，搜索三角形丁； 输出：符合查询条件的项； ｂｅｇｉｎ ｉｆＥ是叶子节点ｔｈｅｎ 遍历Ｅ中的每一项Ｅ ； ｉｆ Ｅ 与搜索三角形Ｔ相交ｔｈｅｎ ｒｅｔｕｒｎ（Ｅ）； ｅｌｓｅ 遍历Ｅ中的每一项Ｅ．； ｉｆＥ 与Ｔ相交ｔｈｅｎ ＩＲｒｒ一以Ｅ为根节点的树； ＩＲＴＳｅａｒｃｈ（ＩＲＴ，Ｔ）； ｅｎｄ． ２．３性能分析 针对空间数据对象和空间数据集的空间分布在众多情 况下呈近似三角形和三角分布的特点，传统的以最小外接 矩形（ＭＢＲ）为聚类近似手段的空间索引树（如Ｒ树）将具 有一些不足。为了弥补该缺点，２．２节研究了ＩＲＴ树和相 应的操作算法。本节对ＩＲＴ树进行性能分析。 利用算法复杂度分析技术对本文的ＩＲＴ树的节点 算法和搜索算法进行算法分析。由算法１可知，算法在 最好的情况下的时间复杂度为Ｏ（ ），最坏情况下的时间复 杂度为Ｏ（ｎｌｏｇ￣ｋ），其中，，ｚ表示叶子节点中包含数据对象的 个数；ｌｏｇ￣ｋ为树的最大深度，ｋ为空间对象个数。算法２的 时间复杂度为（１ｏｇｎ），最坏情况下的时间复杂度为０（ ）。 进一步，表１给出了ＩＲＴ树和Ｒ树的指标参数比较信 息。所用的空间数据对象数为９５０，其中７８％的空间数据 对象呈近似三角形；７３ 的空间数据对象分布的子集合可 近似由一定数量的三角形进行聚类。由表１可知，处理该 空间数据集，ＩＲＴ树在存储空间、查询误差，建树代价方面 都比Ｒ树少。其中，空间对象近似和数据聚类时所产生的 冗余空白空间信息仅为Ｒ树的８６ 。 表１基本性能指标比较 ３ 结语 由于在实际空间场景中，很多空间数据对象的形状是 近似三角形的，空间数据对象的聚集分类区域往往也近似 三角区域，用传统的Ｒ树索引结构进行数据组织和索引，所 产生的空白较多，影响建树和查询效果。本文研究了一种 新的空间索引树即ＩＲＴ树，提出利用最小外接等腰直角三 角形代替最／Ｊ，￣ｂ接矩形对空间对象及对象集区域进行近 （下转第２２１页） ２０１３年第２期 计算机与数字工程 Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｅｌｅｃｔｒｏｎｉｃｓ，２００５，２７（５）：８４１—８４３． ２２１ ｂｅｔｗｅｅｎ ａｌｔｅｒｎａｔｉｖｅｓ ｗｉｔｈ ｓｐｅｃｉａｌ ｔｙｐｅ ｏｆ ｉｎｃｏｍｐｌｅｔｅ ｉｎ ｆｏｒｍａ— ｔｉｏｎ［－Ｊ］．Ｅｕｒｏｐｅａｎ ｏｆ Ｊｏｕｒｎａｌ Ｏｐｅｒａｔｉｏｎａｌ Ｒｅｓｅａｒｃｈ，１９９７，９６ （２）：３９８ ４０６． ［１２］吴江，黄登仕．区间数排序方法研究综述［Ｊ］．系统工程，２００４， （８）：１－４． ［６］华光旭．试论投资风险评估［ｎ有色金属，２０１０，２：１３２—１３３． ＨＵＡ Ｇｕａｎｇｘｕ．Ｄｉｓｃｕｓｓｉｏｎ ｏｎ Ｉｎｖｅｓｔｍｅｎｔ Ｒｉｓｋ Ｅｖａｌｕａｔｅ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ＸｉｎＪｉａｎｇ Ｎｏｎｆｅｒｒｏｕｓ Ｍｅｔａｌｓ，２０１０，２：１３２－１３３． ＷＵ Ｊｉａｎｇ，ＨＵＡＮＧ Ｄｅｎｇｓｈｉ．Ａｎ Ｒｅｎｅｗ ｏｎ Ｒａｎｋｉｎｇ Ｍｅｔｈｏｄｓ ｏｆ Ｉｎｔｅｒｖａｌ Ｎｕｍｂｅｒｓ［Ｊ］．Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ，２００４，（８）：１—４． ［１３］姜宁，李登峰．不完全信息多属性决策的集成模型与方法［Ｊ］． 系统工程与电子技术，２００１，２３（２）：７１—７３． ＪＩＡＮＧ Ｎｉｎｇ，ＬＩＤ￣ｎｇｆｅｎｇ．ＡｎＩｎｔｅｇｒａｔｅ ｄＭｏｄｅｌ ａｎｄＭｅｔｈｏｄｆｏｒ ［７１樊治平，张权．一种不确定多属性决策模型的改进［Ｊ］．系统工 程理论与实践，１９９９，１９（１２）：４２—４７． ＦＡＮ Ｚｈｉｐｉｎｇ，ＺＨＡＮＧ ＱｕａｒＬ Ｔｈｅ Ｒｅｖｉｓｉｏｎ ｆｏｒ ｔｈｅ Ｕｎｃｅｒｔａｉｎ Ｍｕｌｔｉａｔｔｒｉｂｕｔｅ Ｄｅｃｉｓｉｏｎ Ｍａｉｋｎｇ Ｗｉｔｈ Ｉｎｃｏｍｐｌｅｔｅ Ｉｎｆｏｒｍａｔｉｏｎ［Ｊ］． Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｎｎｇ ａｎｄ日ｅｃｔｒｏｎｉｃｓ，２００１，２３（２）：７１—７３． Ｍｕｌｔｉｐｌｅ Ａｔｔｒｉｂｕｔｅ Ｄｅｃｉｓｉｏｎ Ｍａｋｉｎｇ Ｍｏｄｅｌｓ［Ｊ］．Ｓｙｓｔｅｍｓ Ｅｎｇｉ— ｎｅｅｒｉｎｇ－ｔｈｅｏｒｙ＆Ｐｒａｃｔｉｃｅ，１９９９，１９（１２）：４２—４７． Ｌ１４］徐泽水，达庆利．区间数排序的可能度法及其应用［Ｊ］．系统工 程学报，２００３，１８（１）：６７—７Ｏ． ＸＵ Ｚｅｓｈｕｉ，ＤＡ Ｑｉｎｇｌｉ．Ｐｏｓｓｉｂｉｌｉｔｙ ｄｅｇｒｅｅ ｍｅｔｈｏｄ ｆｏｒ ｒａｎｋｉｎｇ ［８］达庆利，徐泽水．不确定多属性决策的单目标最优化模型ｉ－ｊ］． 系统工程学报，２００２，１７（１）：５０—５５． ＤＡ Ｑｉｎｇｌｉ，ＸＵ Ｚｅｓｈｕｉ．Ｓｉｎｇｕｌ ｏ ｂｊｅｃｔｉｖｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｍｏｄｅｌ ｉｎ ｉｎｔｅｒｖａｌ ｎｕｍｂｅｒｓ ａｎｄｉｔｓ ａｐｐｌｉｃａｔｉｏｎ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ，２００３，１８（１）：６７—７０． ｕｎｃｅｒｔａｉｎ ｍｕｌｔｉ—ａｔｔｒｉｂｕｔｅ ｄｅｃｉｓｉｏｎ ｍａｋｉｎｇ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｓｙｓ— ｔｅｒｎｓ Ｅｎｇｉｎｅｅｒｉｎｇ，２００２，１７（１）：５Ｏ一５５． ［１５］梁智学，郭俊颖．基于多源数据融合的网络风险评估＿Ｊ］．舰船 电子工程，２０１１，３１（４）． ＬＩＡＮＧ Ｚｈｉｘｕｅ，ＧＵＯ Ｊｕｎｙｉｎｇ．Ｎｅｔｗｏｒｋ Ｒｉｓｋ Ａｓｓｅｓｓｍｅｎｔ ［９］徐泽水．对方案有偏好的三角模糊数型多属性决策方法研究 ＿＿Ｊ］．系统工程与电子技术，２００２，２４（８）：９－１２． ＸＵ Ｚｅｓｈｕｉ．Ｓｔｕｄｙ ｏｎ Ｍｅｔｈｏｄ ｆｏｒ Ｔｒｉａｎｇｕｌａｒ Ｆｕｚｚｙ Ｎｕｍｂｅｒ－ Ｂａｓｅｄ Ｍｕｌｔｉ Ａｔｔｒｉｂｕｔｅ Ｄｅｃｉｓｉｏｎ Ｍａｋｉｎｇ Ｗｉｔｈ Ｐｒｅｆｅｒｅｎｃｅ Ｉｎｆｏｒ— Ｂａｓｅｄ ｏｎ Ｍｕｌｔｉ—Ｓｏｕｒｃｅ Ｄａｔａ Ｆｕｓｉｏｎ［Ｊ］．Ｓｈｉｐ Ｅｌｅｃｔｒｏｎｉｃ Ｅｎｇｉ— ｎｅｅｒｉｎｇ，２０１１，３１（４）． ｍａｉｒｏｎ ｏｎ Ａｌｔｅｍａｔｉｖｅｓ口］．Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｅｌｅｃｔｒｏｎ— ｉｃｓ，２００２，２４（８）：９－１２． ［１６］陈华伟，陈生春，黄祥兵．风险矩阵方法在集体逃生舱释放过 程中的应用研究＿Ｊ］．舰船电子工程，２０１１，３１（７）． ＣＨＥＮ Ｈｕａｗｅｉ，ＣＨＥＮ Ｓｈｅｎｇｃｈｕｎ，ＨＵＡＮＧ Ｘｉａｎｇｂｉｎｇ． Ａｐｐｌｉｎｇ Ｒｉｓｋ Ｍａｔｒｉｘ Ｍｅｔｈｏｄ ｔｏ Ｅｖａｌｕａｔｅ ｔｈｅ Ｒｅｌｅａｓｉｎｇ ［１０］李汶华，郭军鹏．判断矩阵的区间权向量及其方案排序［Ｊ］．哈 尔滨工业大学学报，２００５，７（５）：６９８—７００． ＬＩ Ｗｅｎｈｕａ，ＧＵ０ Ｊｕｎｐｅｎｇ．Ｉｎｔｅｒｖａｌ ｗｅｉｇｈｔ ｖｅｃｔｏｒ ｏｆ ｊｕｄｇ— Ｐｒｏｃｅｓｓ ｏｆ Ｃｏｌｌｅｃｔｉｖｅ Ｅｓｃａｐｅ Ｃａｐｓｕｌｅ￣Ｊ］．Ｓｈｉｐ Ｅｌｅｃｔｒｏｎｉｃ Ｅｎ— ｇｉｎｅｅｒｉｎｇ，２０１１，３１（７）． ｍｅｎｔ ｍａｔｒｉｘ ａｎｄ ｒａｎｋｉｎｇ ｏｆ ｔｈｅ ａｌｔｅｒｎａｔｉｖｅｓ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｈａｒｂｉｎ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，２００５，７（５）：６９８—７００． ［１７］徐泽水，达庆利．区间型多属性决策的一种新方法［Ｊ］．东南大 学学报，２００３，３３（４）：４９８—５０１． ＸＵ Ｚｅｓｈｕｉ，ＤＡ Ｑｉｎｇｌｉ．Ｎｅｗ ｍｅｔｈｏｄ ｆｏｒ ｉｎｔｅｒｖａｌ ｍｕｌｔｉ—ａｔｔｒｉｂ ［１１］熊文涛，刘三阳，史加荣．不确定性多属性决策的一种新方法 ［Ｊ］．系统工程与电子技术，２００５，２７（５）：８４１—８４３． ＸＩＯＮＧ Ｗｅｎｔａｏ，ＬＩＵ Ｓａｎｙａｎｇ，ＳＨＩ Ｊｉａｒｏｎｇ．Ｎｏｖｅｌ ｍｅｔｈｏｄ ｕｔｅ ｄｅｃｉｓｉｏｎ—ｍａｋｉｎｇ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｓｏｕｔｈｅａｓｔ Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔ ｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ），２００３，３３（４）：４９８—５０１． 不 乖 尔 希 乖 尜 筇 ｆｏｒ ｔｈｅ ｕｎｃｅｒｔａｉｎ ｍｕｌｔｉ—ａｔｔｒｉｂｕｔｅ ｄｅｃｉｓｉｏｎ ｍａｋｉｎｇ［Ｊ］．Ｓｙｓｔｅｍｓ ！； ！矫 ． 坏 铞 不 ： ．希 （上接第１９７页） 似，给出了节点算法和搜索算法，最后对ＩＲＴ树进行 了性能分析。分析表明，ＩＲＴ树对一些特定数据对象集具 Ｐｒｅｓｓ。２０ｌ１． ［６］李松，郝忠孝．球面上最近邻空问关系处理方法［Ｊ］．计算机工 程，２０１０，３６（６）：９１—９３． ＬＩ Ｓｏｎｇ，ＨＡＯ Ｚｈｏｎｇｘｉａｏ．Ｍｅｔｈｏｄｓ ｆｏｒ ｈａｎｄｌｉｎｇ ｎｅａｒｅｓｔ 有一定的优势。下一步的研究重点主要在于ＩＲＴ树的索 引优化及将ＩＲＴ树用于空间查询的研究（如单纯型连续近 邻链查询 。 和球面上的Ｋ最近邻查询 等）。 参考文献 ｒ１］ＧＵＴＹＭＡＮ Ａ Ｒｔｒｅｅｓ：Ａ ｄｙｎａｍｉｃ ｉｎｄｅｘ ｓｔｒｕｃｔｕｒｅ ｆｏｒ ｓｐａｔｉａｌ ｎｅｉｇｈｂｏｒ ｓｐａｔｉａｌ ｒｅｌａｔｉｏｎｓ ｏｎ ｓｐｈｅｒｉｃａｌ ｓｕｒｆａｃｅ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ，２０１０，３６（６）：９卜９３． ［７］ＺＨＡＮＧ Ｌｉｐｉｎｇ，ＬＩ Ｓｏｎｇ．Ｓｉｍｐｌｅ ｃｏｎｔｉｎｕｅｓ ｎｅａｒ ｎｅｉｇｈｂｏｒ ｃｈａｉｎ ｑｕｅｒｙ ｏｆ ｔｈｅ ｄａｔａｓｅｔｓ ｂａｓｅｄ ｏｎ ｔｈｅ Ｒ Ｔｒｅｅ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍｓ，２０１２，２２：１－８． ｓｅａｒｃｈｉｎｇ［Ｃ］／／Ｐｒｏｃ．ｏｆ ＡＣＭ ＳＩＧＭＯＤ，Ｂｏｓｔｏｎ，ＭＡ，１９８４：４７－５７． ［２］张明波，陆锋，申排伟，等．Ｒ＿树家族的演变和发展［Ｊ］．计算机 学报，２００５，２８（３）：２８９—３００． ＺＨＡＮＧ Ｍｉｎｇｂｏ，ＬＵ Ｆｅｎｇ，ＳＨＥＮ Ｐａｉｗｅｉ．Ｔｈｅ ｅｖｏｌｖｅｍｅｎｔ ［８］孙殿柱，孙永伟．Ｒ＊一树结点自适应聚类分簇算法ＩＪ］．北京航 空航天大学学报，２０１２，６：１－５． ＳＵＮ Ｄｉａｎｚｈｎ，ＳＵＮ Ｙｏｎｇｗｅｉ．Ｎｏｄｅ ｓｐｌｉｔｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｏｆ Ｒ ａｎｄ ｐｒｏｇｒｅｓｓ ｏｆ Ｒ－Ｔｒｅｅ ｆａｍｉｌｙ［Ｊ］．Ｃｈｉｎｅｓｅ Ｊｏｕｒｎａｌ Ｏｆ Ｃｏｍｐｕｔ ｅｒｓ，２００５，２８（３）：２８９—３００． ＊一ｔｒｅｅ ｂａｓｅｄ ｏｎ ｓｅｌｆ－ａｄａｐｔａｔｉｏｎ ｃｌｕｓｔｅｒｉｎｇ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｂｅｉ— ｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ａｅｒｏｎａｕｔｉｃｓ ａｎｄ Ａｓｔｒｏｎａｕｔｉｃｓ，２０１２，６：１－５． ［３］郝忠孝．时空数据库查询与推理［Ｍ］．北京：科学出版社，２０１０． ＨＡＯ Ｚｈｏｎｇｘｉａｏ．Ｓｐａｔｉｏ ｔｅｍｐｏｒａｌ ｄａｔａｂａｓｅ ｑｕｅｒｙ ａｎｄ ｒｅａｓｏｎ— ［９］李松，张丽平，蔡志涛，等．数据集中单纯型连续近邻链查询方 法［Ｊ］．计算机工程，２０１２，３８（４）：８２ ８３． ＬＩ Ｓｏｎｇ，ＺＨＡＮＧ Ｌｉｐｉｎｇ，ＣＡＩ Ｚｈｉｔａｏ．Ｑｕｅｒｙ ｍｅｔｈｏｄ ｏｆ ｓｉｍ— ｉｎｇ［Ｍ］．Ｂｅｉｊｉｎｇ：Ｓｃｉｅｎｃｅ Ｐｒｅｓｓ，２０１０． ［４］郝忠孝．移动对象数据库理论基础［ⅣＩ］．北京：科学出版社，２０１２． ＨＡ０ Ｚｈｏｎｇｘｉａｏ．Ｔｈｅｏｒｅｔｉｃａｌ ｂａｓｉｓ ｆｏｒ ｍｏｖｉｎｇ ｏｂｊｅｃｔｓ ｄａｔａｂａｓｅ ｐｉｅ ｃｏｎｔｉｎｕｓ ｎｅａｒ ｎｅｉｇｈｂｏｒ ｃｈａｉｎ ｉｎ ｄａｔａｓｅｔ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉ ｎｅｅｒｉｎｇ，２０１２，３８（４）：８２—８３． ［Ｍ］．Ｂｅｉｊｉｎｇ：Ｓｃｉｅｎｃｅ Ｐｒｅｓｓ，２０１２． ［５］李松，张丽平，孙冬璞．空间关系查询与分析［Ｍ］．哈尔滨：哈尔 滨工业大学出版社，２０１１． ＬＩ Ｓｏｎｇ，ＺＨＡＮＧ Ｌｉｐｉｎｇ，ＳＵＮ Ｄｏｎｇｐｕ．Ｓｐａｔｉａｌ ｒｅｌａｔｉｏｎ ｑｕｅ— ［１Ｏ］张丽平，李松，郝晓红．球面上的Ｋ最近邻查询算法［Ｊ］．计算 机工程，２０１１，３７（２）：５２—５６ ＺＨＡＮＧ Ｌｉｐｉｎｇ，ＬＩ Ｓｏｎｇ，ＨＡ０ Ｘｉａｏｈｏｎｇ．Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ Ｋ－Ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｑｕｅｒｙ ｏｎ ｓｐｈｅｒｅ［Ｊ］．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒ— ｉｎｇ，２０１１，３７（２）：５２—５６． ｒｙ ａｎｄ ａｎａｌｙｓｉｓ［Ｍ￣．Ｈａｒｂｉｎ：Ｈａｒｂｉｎ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ
