（管理科学与工程专业论文）基于语义的航天信息元数据多维索引的研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 随着我国空间技术的发展和航天体系的逐步完善，特别是在2 0 2 0 年前将建成 完善长期稳定运行的航天设备体系，卫星信息资源必将日益丰富，最终将覆盖全 地域、全时段、全传感类型、全频谱和多分辨率，形成一个覆盖全球的多维卫星 信息空间。 然而，海量的航天信息元数据分布在一个广域的网络环境中。在实际应用时， 对于每个用户来说，要想从中快速自动地获取到满足需求的特定地域、特定时间 段、特定传感器、特定频谱、特定分辨率的空间信息，并综合成一组包括基础地 理数据、环境信息和目标状况于一体的综合信息，是一个复杂的过程。就目前成 熟的技术手段来看，难免会发生“找得慢，找不到，找不全，找不准，不配套” 的问题。 本文以航天信息应用为研究背景，以提高查询航天信息元数据的效率和改善 查询效果为目的，深入研究了针对航天信息元数据的多维索引和基于语义信息构 建和查询的机制，论文做了以下工作： ( 1 ) 针对数据类型的混合性提出了一种适合点和区间混合型维度数据集的多 维索引结构- p i 树。p i 树利用超球划分数据集的多维空间，以提高节点存储利 用率，从而降低数据插入时u o 次数；借鉴r 幸树的建树过程并进行相应算法简化， 有效提高了p i 树建树效率；此外，给出了p i 树插入、删除和查询算法的形式化描 述。理论分析和实验结果表明，本文提出的p i 树建树效率高于r 幸树，存取数据时 f o 次数相对减少，检索效率也相应提高。 ( 2 ) 针对各种元数据标准中各概念、各维度之间的语义相关性，结合本体的 应用，本文提出了在语义本体指导下的多维索引构建方法和检索方法，解决了各 种类型元数据标准中概念之间“异形同义 的问题，并利用维度相关性缩小查询 范围，对改善检索效果和提高检索效率起到了一定的作用。 ( 3 ) 针对元数据文件各维度的层次性，结合相关编码技术，提出了一种具有 层次信息的二进制编码方法，表达出了维度语义层次信息结构，有助于改善查询 效果。 主题词：多维索引语义航天信息球航天信息元数据本体维层次编码 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fs p a c et e c h n o l o g ya n di n f o r m a t i o nt e c h n o l o g yi n c h i n a , t h ei m p o r t a n c eo fs p a t i a li n f o r m a t i o nm e t a d a t am a n a g e m e n ti sb e c o m i n g i n c r e a s i n g l yp r o m i n e n t h o w e v e r , a ni n t e r n a t i o n a ls t a n d a r dh a sn o tc o m eo u ty e t ，a n d c h i n ai sa l s oa t t e m p t i n gt op r o p o s ei t sm e t a d a t as t a n d a r d s p a t i a li n f o r m a t i o nm e t a d a t a s t a n d a r dh a ss u c hc h a r a c t e r i s t i c sa sd i s u n i t y ，d i s t r i b u t e da n dm a s s i v e ，a n di tm a k e st h e m a n a g e m e n t ，m a i n t e n a n c ea n da c q u i s i t i o no fs p a t i a lm e t a d a t ar a t h e rd i f f i c u l ta n d c o m p l i c a t e d s p a t i a lm e t a d a t am a n a g e m e n tb a s e do ns p a t i a li n f o r m a t i o ns p h e r ed o e sn o tm e a n t oe s t a b l i s han e ws t a n d a r da n dh a sn o tm a d ea n ym o d i f i c a t i o no rc h a n g e st ot h ec u r r e n t s t a n d a r d t h ep u r p o s eo fi ti st ob u i l dau n i v e r s a ll o g i cm o d e lf r o mt h ea n g l eo f s e m a n t i cr e l a t i o n so fk i n d so fm e t a d a t as t a n d a r d s i tw i l ln o ta f f e c tt h ea c q u i s i t i o no r s t o r a g eo fs p a t i a lm e t a d a t a a n dt h r o u g ht h eu n i v e r s a l ，e x t e n d a b l el o g i cm o d e l ，i tw i l l b ee a s yt oc o n s t r u c t sas e l f - a d j u s t i n gs p a t i a li n f o r m a t i o nm a n a g e m e n ta n ds e r v i c e m e c h a n i s ma n di m p r o v e st h eu s a g eo fs p a t i a li n f o r m a t i o nt oag r e a te x t e n t t h i sp a p e rh a v ea n a l y z e ds p a t i a lm e t a d a t a ，p o i n t i n go u tt h a tt h e r ea r et h r e ef e a t u r e s i ns p a t i a lm e t a d a t a ，a n db a s e do nt h e s et h r e ef e a t u r e s ，t h i sp a p e rh a v ed e v e l o p e d f o l l o w i n g ： ( 1 ) m a n ym u l t i d i m e n s i o n a l i n d e x e sh a v es i m p l ym a d ec o n t r i b u t i o nt ot h e d i m e n s i o n s 、析t l lt h et y p eo fp o i n to ri n t e r v a l w h i l ec o n s i d e r i n gt h ed a t as e to fh y b r i d d i m e n s i o n s 、v i t ht h et y p eo fb o t hp o i n ta n di n t e r v a l t h e r ei sf e ws t u d yt od e a lw i t ht h e p r o b l e m t h i sk i n do fd a t as e ti so f t e na p p l i e di nt h em e t a d a t aw h i c hd e s c r i b et h e g e o g r a p h i ci n f o r m a t i o nr e s o u r c e s t h i s t h e s i s p r o p o s e s an e wm u l t i d i m e n s i o n a l i i l d e x - p it r e e ，a d a p t i n gt ot h i sk i n do fd a t as e ta b o v e ，u s i n gt h ei d e ao fs u p e r - s p h e r ei n t h es s - t r e e t h e n , w ed i s c u s st h ea l g o r i t h mo fb u i l d i n ga n ds e a r c h i n go fo u rt r e e f i n a l l y ，w em a k ee x p e r i m e n t st os h o w p it r e eo u t p e r f o r m st h er * - t r e e ( 2 ) b a s e do no n t o l o g yt e c h n i q u e s ，t h i st h e s i sh a sp r o p o s e dm u l t i d i m e n s i o n a li n d e x b u i l d i n ga n dr e t r i e v a lm e t h o d s 、i mt h eh e l po fo n t o l o g yi no r d e rt os o l v es e m a n t i c p r o b l e mi ns p a t i a lm e t a d a t a ( 3 ) b a s e do nd i m e n s i o n a lh i e r a r c h i c a le n c o d i n gt e c h n i q u e s ，t h i st h e s i sh a sp r o p o s e d ak i n do fb i n a r yd i m e n s i o n a lh i e r a r c h i c a le n c o d i n gm e t h o di no r d e rt os o l v eh i e r a r c h i c a l s e m a n t i cp r o b l e mi ns p a t i a lm e t a d a t a k e yw o r d s ：m u t i d i m e n s i o n a l - i n d e x ，s e m a n t i c ，s p a c ei n f o r m a t i o n m e t a d a t a ，s p a t i a li n f o r m a t i o ns p h e r e ，o n t o l o g y ，d i m e n s i o n a lh i e r a r c h i c a l c o d e 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表3 1r 宰树与p i 树最大叶节点数量比较2 8 表4 1 检索技术分类及比较描述3 4 表4 2o w l 语言描述元数据示例3 8 表4 3 待插入元数据片段4 6 表5 1 电子侦察元数据片段5 3 表5 2 地面目标情报元数据片段5 4 表5 3 进行编码后的维度值5 6 表5 4 语义相关查询结果5 7 表5 5 维层次查询结果5 7 第1 v 页 国防科学技术大学研究生院硕士学位论文 图目录 图1 1 多维索引历史发展演变图6 图1 2k d 树示意图6 图1 3 网格文件示意图8 图1 4 四叉树示意图9 图1 5 几类空间填充曲线9 图1 6 论文结构图1 2 图2 1 航天信息球的三类映射1 5 图3 1k d b 树的示意图1 9 图3 2r 母树的示意图2 0 图3 3s s 树的示意图2 0 图3 4s r 树的示意图2 1 图3 5 混合型维度在二维时的直观表示2 2 图3 6 利用r 树的r 包络不规则形状2 2 图3 7 利用限定圆包络不规则形状2 2 图3 8 三维情况时利用限定球包络不规则形状2 3 图3 9p i 树在二维中的空间划分2 4 图3 1 0p i 树的结构2 4 图3 1 1 插入新节点时c p u 耗时对比2 9 图3 1 2 插入新节点时i o 次数对比2 9 图3 1 3 检索时c p u 耗时对比3 0 图3 1 4 检索时i o 次数对比3 0 图4 1 基于w e b 的本体描述语言的相互关系3 2 图4 2 航天信息本体架构图3 7 图4 3 元数据结构层次性示意图3 8 图4 4 全局共享本体结构示例4 0 图4 5 三种层次结构示意图4 l 图4 6 时间维层次编码示意图4 4 图4 7 不规则层次结构编码示意图4 4 图4 8 本体指导算法作用位置示意图4 6 图4 9 利用维关联缩小查询范围示意图4 8 图5 1 航天资源注册中心结构5 1 图5 2 多维索引在注册中心的位置5 2 第v 页 国防科学技术大学研究生院硕士学位论文 图5 3 多维索引模块包括的算法5 2 第v i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：基王适必鲍蕴丞焦皇丞数量垒丝塞曼i 鲍盈究 学位论文作者签名： 主拯型日期：办研年2 月7 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：基王适幺鲍魅丞焦! 塾五数量垒丝塞! 煎盟究 学位论文作者签名：涨耕 作者学导教师签名：乌蕻肛 日期：力。7 年2 月了日 吼明年，2 月7 日 国防科学技术大学研究生院硕士学位论文 第一章绪论 1 1 研究背景 随着我国空间技术的发展和航天体系的逐步完善，特别是在2 0 2 0 年前将建成 完善长期稳定运行的航天设备体系，卫星信息资源必将日益丰富，最终将覆盖全 地域、全时段、全传感类型、全频谱和多分辨率，形成一个全球全维的卫星信息 空间。如何有效地利用各种卫星信息，快速、准确、方便地支持国内空间信息需 求或特定应用，是我们必须面对的一个重大问题。 航天信息元数据目的在于实现航天信息的有效管理和合理共享这样的双重目 的。对于数据生产者，一方面通过提供航天信息元数据，及时发布有效的地理空 间数据，最大限度地发挥已有地理空间信息的价值，另一方面根据航天信息元数 据的内容有效地管理和维护已有地理空间数据。根据数据生产者提供的航天信息 元数据，可以实现地理空间信息的快速检索和准确定位，最终达到数据共享的目 的。对用户而言，航天信息元数据大大方便了用户查询检索有效的航天信息，方 便他们了解已有的地理空间信息，帮助他们选择合适的地理空间信息，从而有效 地促进地理空间信息的再利用。 然而，海量的航天信息元数据分布在一个广域的网络环境中。在实际应用时， 对于每个用户来说，要想从中快速自动地获取到满足需求的特定地域、特定时间 段、特定传感器、特定频谱、特定分辨率的空间信息，并综合成一组包括基础地 理数据、环境信息和目标状况于一体的综合信息，是一个复杂的过程。就目前成 熟的技术手段来看，难免会发生“找得慢，找不到，找不全，找不准，不配套 的问题。 因此，有必要从全维航天信息空间的组织入手，建立全局、通用、完备的航 天信息元数据描述模型，继而建立能够动态、自适应的航天信息组织管理和服务 机制，以保证分布在不同地方不同系统中的各地域、各时相、各种传感器类型、 各频谱、各级分辨率的卫星信息，能够根据用户的需要，迅速地被发现和获取， 并针对任务需求被裁减和整合，供用户直接使用。 在这样的需求背景下，本人所在课题组吸收知识工程领域的研究成果，提出 从用户的语义出发组织信息的方法，建立了一种新型的航天信息概念模型航 天信息球。 航天信息球是一个基于地球空间的多维动态的卫星信息元数据的全局逻辑模 型。它通过对各类航天信息元数据、航天信息处理服务元数据和卫星资源元数据 分别建立语义关联索引，能够对所有航天信息和航天信息处理服务进行快速、准 第1 页 国防科学技术大学研究生院硕士学位论文 确、完整的搜索定位，同时还能够实时反映出卫星资源获取航天信息的能力状态 及其变化。它通过多源航天信息球与地球空间的逻辑映射关系，可以定位地球空 间的物理位置并进而通过在信息球上加上时间维，来反映地球空间的时空关系； 通过航天信息球航天信息存储与处理服务的逻辑映射，来反映出特定时空的航天 信息的存储位置，实际上也反映了数据中心、应用中心在信息球上的部署，从而 能够获得航天信息处理服务的分布信息；还对应着卫星信息获取能力的映射，根 据卫星资源的元数据，在信息球上建立在轨卫星与地球空间位置的动态时空关系， 可以获得卫星的轨道信息和传感器信息，进而可以得到卫星在具体时刻所覆盖的 地球空间范围。 航天信息球的一个很重要的功能是有效地组织航天信息元数据集，它可以按 照地域、时间、传感器、频谱和分辨率等用户所感兴趣的要素从不同的视角分解 为各个维度，使用户能够更快、更全面地发现、访问、获取数据。要达到这样的 目标，必然会对数据的索引技术等方面提出很高的性能要求。要使用户在任何时 间、任何地点以任何方式快速有效的通过维度的组合查询关于某个方面的航天信 息，就要在深入分析航天信息元数据的基础上建立一套完整高效的多维索引体系。 上述是从查询效率上对多维索引的要求，随着需求的提高，不仅仅要从查询 效率上满足用户，用户对查询效果的要求也会增加。用户不单纯对其查询的卫星 产品关心，对与之相关的其他卫星产品也需要获得，从而对其应用或任务目的有 一个详尽完备的了解。完成这种需求就要从元数据描述卫星产品的本质出发，各 类元数据本身及各类元数据之间相互的关系作出详细的分析。为了这种目的，我 们要从语义的角度来解决问题，利用“基于语义”的方法来构建多维索引。这也 是本文的目的之所在。 1 2 多维索引概述 近几年，随着大量依赖于多维数据的计算机应用数量的增加，数据库领域的 研究人员在多维数据管理方面投入了大量的精力。虽然这方面的研究动力主要来 源于地球科学和计算机辅助设计( c o m p u t e ra i d e dd e s i g n ，c a d ) ，但目前这方面 的应用领域不断在扩大，如机器人技术、可视化技术、自动导航技术、环境保护 和医学成像等【j j 。 在这种背景之下，多维数据索引结构和适用于多维索引结构的查询算法得到 了人们的极大重视。在传统的数据库研究领域中，针对单维数据的索引技术已经 非常成熟，典型的如b 树、b + 树索引方法，弥久不衰，直到现在仍广泛地被使用。 但是，对于多维数据，由于多维空间中不存在线性顺序，索引算法的设计要复杂 得多。多维索引所面对的是一个无序的多维空间，需要同时对多个数据维进行索 第2 页 国防科学技术大学研究生院硕士学位论文 引，大大增加了索引处理的难度。 目前对多维索引还没有一个完整而准确的定义。在此，给出本文作者自己的 理解。在数据库中，索引是对数据库表中一列或多列的值进行排序的一种结构， 使用索引可快速访问数据库表中的特定信息。维是人们观察事物的特定角度，多 维即是从多个不同的视角考察研究的事物。多维索引就是针对具有多属性的数据 集对其建立多视角的排序结构。 多维索引并不是简单的在每个属性或维度上建立一维索引( 如b 树) 而实现 的，如果这样，由于各个维的索引彼此之间相互独立的，这样将导致关键字必须 存储多次，极大了浪费了存储空间。多维索引往往是通过对空间或数据的划分， 将各个维度综合起来考虑，统一建立整体的数据结构解决问题。 1 - 2 - 1 多维数据的特点 文献 1 ，2 是关于多维索引综述的文章，它们较系统的阐述了多维索引的特点和 发展。一般来说，多维数据具有下列特征【1 】： 结构复杂：数据是多维空间的数据，一般不能像传统的关系型数据库一样 用固定大小的条目来保存； 动态特性：在插入和删除的过程中往往还伴随对数据本身的修改； 海量数据：多维数据库存储空间比较大； 操作多样化：对多维数据而言，没有标准的操作，一般要根据实际需要而 定； 时间代价大：多维数据库的操作所花费时间各不相同，但一般都高于传统 关系型数据库； 不能排序：无法对空间数据进行线形排序以使多维空间中相邻的数据仍然 能够相邻。 1 2 2 多维索引结构的特点 正是由于多维数据具有上述特点，多维索引的设计也要满足以下特征【1 】： 动态构造：因数据可在数据库中以任意顺序插入或删除，其索引结构也应 支持相应的操作； 二级_ - - 级存储管理：尽管主存容量日益增大，但仍不能将整个数据库保存 在主存里，索引结构应充分考虑n - 级及三级的存储管理； 独立于数据的输入和插入的顺序：支持任意顺序； 可增长性：索引结构应能够适应数据库大小的增长； 时间的有效性：查找速度必须是快速的； 第3 页 国防科学技术大学研究生院硕士学位论文 空间的有效性：索引结构相对于原数据应是比较小的，而且还要保证一定 的空间利用率； 支持尽量多的操作，能够保证操作的并行性和可恢复性。 从上述特点分析可见，多维数据相对复杂，对多维索引结构和算法的要求也 较高，且不存在适用所有多维数据的索引结构，多维索引通常都是针对特定多维 数据建立的。 1 。2 3 多维数据库的查询方式 根据应用领域的不同，多维数据库的查询方式也各不相同。对于给定的数据 库d b ，常用的查询方式有u 】： 精确匹配查询( e x a c tm a t c hq u e r y ，e m q ) ：对于给定的查询数据q ，从d b 中找出所有与q 相同的数据； 点查询( p o i n tq u e r y ，p q ) ：给定点数据q ，从数据库中找出所有包含点q 的 数据； 窗口查询( w i n d o wq u e r y ，w q ) ：给定一个d 维的矩形查询区 d = ，】 f 2 ，“：】【乙， ，从数据库中找出至少包含一个i 中的点的所有数据； 相交查询( i n t e r s e c t i o nq u e r y ，i q ) ：给定具有一定形状的空间数据q ，从数 据库中找出至少包含q 中一点的所有数据； 包含查询( e n c l o s u r eq u e r y ，e q ) ：给定查询数据q ，从数据库找出所有包含 q 的数据； 被包含查询( c o n t a i n m e n tq u e r y ，c q ) ：给定查询数据q ，从数据库中找出所 有被q 包含的数据； 邻接查询( a d j a c e n c yq u e r y ，a q ) ：给定查询数据q ，从数据库中找出所有同 q 邻接的数据； 范围查询( r a n g eq u e r y ，r q ) ：给定查询数据q 与查询距离门限t ，从数据 库中找出所有与q 距离小于t 的数据； k 近邻查询 n e a r e s t - n e i g h b o rq u e r y ，k n n q ) ：给定查询数据q 及正整数k ， 从数据库中找出距离q 最近的k 个数据。 1 3 研究现状和发展趋势 1 3 1 国内外研究现状 1 3 1 1 多维索引的发展历程 多维索引的历史可以追溯到上世纪七十年代中期。四叉树【3 1 ( q u a d t r e e ) 和 第4 页 国防科学技术大学研究生院硕士学位论文 k d 树【4 】等多维索引结构的提出代表着多维索引的正式出现。这些数据结构的基本 原理就是对多维空间进行递归划分从而构建出树形索引结构。 由于上述索引结构是针对点数据而构建的，因此，相对于精确匹配查询，点 类型四叉树和k d 树可以实现快速检索，但对于相似性查询，两种索引结构的性 能均下降。 多维索引技术上的突破是1 9 8 4 年g u t t m a n 提出的r 树【5 】索引结构。r 树能够 对点和矩形进行索引，利用最小包围矩形( m i n i m a lb o u n d i n gr e c t a n g l e ，m b r ) 来 递归的划分空间，从而建立高度( h e i g h t ) 平衡树。但r 树节点之间的重叠会使得 搜索性能下降，于是，研究者相继提出了r + 树【6 1 、r + 树 7 1 和x 树【8 1 等结构。这些索 引结构基本上是在r 树的基础上，采取一些优化措施来尽量减少重叠对索引的影 响。 对r 树节点形状的改变是研究人员提出的s s 树【9 1 ，s s 树的节点形状是超球而 不是矩形。s s 树在相似检索中所表现出的性能要优于r + 树，然而s s 树也避免不 了超球的重叠现象，因此，有人提出将超球与超矩形相结合从而构成了新的索引 结构s r 树 1 0 】。s r 树的性能超过了r 树和s s 树。 虽然上述研究成果能够很好对多维数据进行索引，但对于维数很高的数据集， 使用多维索引反而会降低查询效率。因此，研究人员发展了降维的方法，采用压 缩和近似的思想把维数降低，典型的是v a f i l e 1 、金字塔技术1 2 1 等。 多维索引结构和算法经常在v l d b 、a c ms i g m o d 和i e e ei c d e 等关于数 据库的项级会议和期刊上发表。从上个世纪七十年代到现在，多维索引结构从最 初的几种单一样式已经发展到十几种结构，本文借鉴了文献 1 】中的多维索引发展 历程演化图来说明多维索引的发展( 如图1 1 ) 。 1 3 1 1 多维索引分类介绍 关于多维索引的分类目前没有一个统一的方法，文献 2 中将多维索引分为以 下几类： ( 1 ) 基于二叉树的索引技术 基于二叉树索引结构的典型范例有k d 树、a d a p t i v ek d 树【13 1 、k d b 树【1 4 】 等。这种索引结构的典型k d 树是一种二分索引树结构，主要用于索引多维数据点， 但对复杂的空间目标，如折线、多边形、多面体等的索引却必须采用近似方法和空 间映射技术。 k d 树是一种在k 维空间中的二叉查找树。它主要存储的是点数据，在每一 个内部节点中，它用一个k 1 维的超平面将节点所表示的k 维空间分成两个部分， 这些超平面在k 个可能的方向上交替出现。而且在每一个超平面中至少要包括一 个点数据。图1 2 就是一个k d 树在二维空间的例子。在k d 树中的查找和插入 第5 页 国防科学技术大学研究生院硕士学位论文 操作是很简单的，而删除操作则有点复杂，因为一个点的删除可能会导致它的子 树的重建。当数据插入的顺序不同的时候，k d 树的结构也不同，而且数据会分 散出现在树的任何地方而不是仅出现在叶子节点上。 a d a p t i v ek d 树对k d 树的结构做了少许改变，在分裂的时候选择合适的超 ，螂7 17 5伸“1 2牡“拈“s 7“，o9 1站 野 蚶 9 6 图1 1 多维索引历史发展演变图 a d c e g 空间划分 树的构造 图1 2k d 树示意图 平面使分裂后的两部分包含相同数量的数据，而且在这些超平面上不一定非要包 第6 页 ， 国防科学技术大学研究生院硕士学位论文 含数据以及它们的方向也不一定严格地在这k 个可能的方向上交替出现。在这种 结构里，内部节点表示的是分裂的超平面，所有的数据都出现在叶子节点中，每 个叶子只能包含一定量的数据，当超过这个数量的时候要发生分裂。 k d b 树将在第三章中给出介绍。 ( 2 ) 基于b 树的索引技术 b 树及其变体，被广泛应用于常规的数据库管理系统之中，实践证明其对大型数 据库的索引具有出色表现。r 树及其变种都是这类基于b 树的索引结构。r + 树、 s s 树和s r 树将会在第三章给出介绍。 ( 3 ) 基于h a s h i n g 的格网技术 这种方法的基本思路是将索引空间划分为相等或不相等的一些小方格网，与每 个格网相关联的空间目标则存储在同一磁盘页，而格网的访问地址则可以直接通过 求数组下标或某种算法得到，如网格文件 1 5 】，r f i l e 1 6 1 等。这类方法主要适用于索引 多维空间点。 网格文件是一种典型的基于h a s h i n g 的存取方式。它是由包含着很多与数据桶 ( d a t ab u c k e t ) 相联系的单元网格目录来实现的，一般一个数据桶为硬盘上一个磁 盘页。每个单元只对应着一个数据桶，而一个数据桶往往可以包含着几个相邻的 单元。随着数据的增多，网格目录可能会慢慢变大，所以往往将其保存在硬盘上， 但为了保证在进行精确查询的时候能仅用两次i o 操作就可找到相应的记录，一般 将网格本身保存在主存中，网格是用d ( 数据的维数) 个一维的数组来表示的，这些 数组称为刻度。当进行精确查询的时候，首先用这些刻度来定位包含要查找的记 录的单元，假如这个单元不在主存中，那么将进行一次i o 操作。将这个单元从硬 盘调人主存，在这个单元中包含着一个指向可能找到记录的页的指针，取这个指 针所指的页又需要一次i o 操作。而对于范围查询，需要检查所有与要查询的区域 相交的单元。图1 3 就是一个网格文件在二维空间的例子。 当向网格文件插入一个数据的时候，首先要进行一次精确查询以确定该数据 项应当插入的单元以及对应的数据页( 数据桶所存放的磁盘页) 。如果在这个页中还 有足够的空间，将数据插入即可。假如己经没有足够的空间，则要根据与该页相 联系的单元的数目来决定处理的方法，当有几个单元指向该页的时候，则检查现 在的刻度中是否有合适的超平面能够成功地将该页分开，如果有就产生一个新的 页并根据这个超平面将数据分配在两个页中；如现存的超平面没有合适的，或者 只有一个单元指向该页时，将引入一个新的超平面并产生一个新的页，然后根据 这个超平面将数据分配，同时要将这个超平面插入到相应的刻度中，所有与此超 平面相交的单元也要发生分裂。 在网格文件中删除一个数据，也要先进行一次精确查询确定该数据所在的单 第7 页 国防科学技术大学研究生院硕士学位论文 元及对应的数据页，并将其删除。假如在删除之后，这个页中存储的数据低于一 定的数目后，就需要做相应的处理，根据当前刻度对空间的分隔情况，或者选择 同其相邻的页合并，或者选择将刻度中的一个超平面取消。 y 刻 度 图1 3 网格文件不意图 ( 4 ) 空间排序类 其基本思想是将索引空间划分为许多小的格子，然后每个格子指定一个惟一 的数字或编码，空间目标则用与其相交的一个或多个格子的数字来表示，或用与其 相交格子的编码求得另一维一编码来表示。实质是将k 维空间的实体映射到一维 空间。用一维的数值对多维的空间目标进行排序，常见的方法有：四叉树、点四叉 树 1 7 】、空间填充曲线 1 8 1 等。 四叉树同k d 树类似，也是用超平面的方法来划分整个空间的，不过不同的 是，四叉树不再是二叉树，在维数为k 的空间中，每一个内部节点具有2 2 个孩子， 每个孩子对应着一个子空间。例如，对于一个在二维空间的四叉树，每个内部节 点拥有4 个孩子，每个孩子对应着一个矩形，这四个矩形一般用n w ，n e ，s w 以 及s e 来表示。用这种方法将整个空间逐渐划分到每一个矩形中所包含的数据的个 数低于一定的数目为止。显然这样得到的四叉树不能保证是平衡树，在数据比较 密集的地方树的深度将高于其他的地方，如图1 4 所示为四叉树在二维空间的一个 例子。 第8 页 国防科学技术大学研究生院硕士学位论文 空间划分 树的构造 图1 4 四叉树示意图 空间填充曲线的特点就是希望找到某种方法对多维空间中的数据进行近似的 排序，使得原来在空间中较为接近的数据能在排序后以比较高的概率靠在一起。 那么就可以用一维数据对它们进行索引。用这种方法在点查询操作中能够取得良 好的效果，但进行范围查询时就会比较繁琐。根据这种思路，人们就提出了几种 将多维空间中的点数据影射到一维空间并进行排序的方法，图1 5 中列出了四种空 间填充曲线。 ：! n ： 矬一 t h i k nd 叠q 图1 5 几类空间填充曲线 国内研究人员对多维索引的研究基本是在国外的研究基础之上展开的。有一 些提出针对应用改进的索引结构，还有一些针对经典的索引结构进行改进算法。 如为了减少r 树约束矩形间重叠区域及空白空间，国内研究人员提出了一种适用 于r 树节点分裂的混合聚类算法【1 9 】。它建立在普通聚类算法的基础上，并对其进 第9 页 门一几 国防科学技术大学研究生院硕士学位论文 行扩充，使得建立的r 树能适用于点状、线状、面状等多种复杂空间数据集。 又如提出的3 d + r 树【2 0 】是对国外的3 d r 树的一种改进，它减少了索引中的长 条立方体，提高了索引性能。在建立索引时将历史数据和活跃数据分开组织，使 得其可以对“在线 数据进行索引。 1 3 2 发展趋势 多维索引是一门比较新的学科，许多研究都很不完善。目前，各种索引方法 纷纷被提出而且都声明自己具有良好的性能。实际上，适合所有场合、所有分布 的索引结构是不存在的1 2 1 j 。 多维索引的发展趋势本文作如下总结： ( 1 ) 降维算法将会更加受到重视。随着应用需求的变化和数据空间复杂度的 提高，多维空间的维数将会越来越高，而几乎所有的多维索引结构的查找时间随 着维度的增加成指数级增长，最终1 1 4 土1 - 白丹匕k 将低于顺序查找的性能【2 2 j 。即便是被认为 较能适应高维数据的r 树家族索引结构也都不可避免地面临这个问题。所以，将 高维转换为低维将会使“维数灾难”问题得到很好的解决。 ( 2 ) 在度量方法上将会发生相应的变化。大多数多维索引一般只支持欧氏距 离和绝对值距离，而实际应用中很多描述相似性搜索都是其他的度量方法，如何 在索引结构中有效地描述各种相似度，这是目前的研究热点和发展趋势。 ( 3 ) 对实际数据分布情况的预测方法将会逐步发展。目前业界的实验中采用 的数据集和实际数据集的分布特征可能相差很大，按照模拟数据的研究方式去讨 论实际数据，得到的结果和实际结果大相径庭。这一方面f a l o u t s o sc 教授己经提 出了自己的新看法【2 3 】。他认为很多实际数据的分布都是符合分形规则即自相似的。 那么，按照分形的特点去预测索引结构的性能和各种参数，就会得到比较正确的 结果。 ( 4 ) 多维索引性能评价的模型将会发展。目前多维索引的性能评价几乎都是 通过测试模拟数据集而实现的。文献 2 4 ，2 5 通过建立了一种花费模型来从理论上评 价多维索引的性能，这将给多维索引的研究人员带来新的研究方法和方向。 1 4 相关工作中存在的主要问题 根据相关工作的分析，目前多维索引存在的主要问题是：空间数据类型问题， 语义问题，层次信息问题。本节对目前工作中存在的不足进行归纳，以便针对这 些问题展开本文所做工作的阐述。 ( 1 ) 维数问题 多维索引技术研究到现在，没有一种多维索引结构和算法能够逃避“维数灾 第1 0 页 国防科学技术大学研究生院硕士学位论文 难”，随着维数的增加，顺序扫描要逐渐优于多维索引。虽然降维算法不断提出， 但这一问题仍然存在。 ( 2 ) 空间数据类型问题 目前的多维索引所考虑的数据空间中的数据类型大多数集中在点类型数据和 区间类型数据上，而对既有点类型又有区间类型的数据空间专门研究得很少。虽 然r 树系列结构支持这种空间类型，但其需保存每一维度的区间范围，增大了信 息存储量，不利于数据的检索。 ( 3 ) 语义问题 现在的多维索引几乎都是在数据层面上构建的，没有体现出数据与数据之间 的语义信息。然而语义信息在实际中的数据中是必然存在的，并且维与维之间也 是有语义关联的。在检索时如果能够首先考虑语义信息，那么将会提前进行信息 的过滤，这对检索的效果和效率是有帮助的。 1 5 本文的工作和论文结构 1 5 1 本文的主要工作 本文以航天信息为研究背景，致力于关于航天信息元数据的基于语义带有层 次信息的多维索引结构和算法。主要内容包括： ( 1 ) 总结了多维索引的研究现状和发展趋势，综述了多维索引的相关技术和 应用。分析了相关工作中存在的不足和主要问题。该项工作对应于本文的第一章。 ( 2 ) 深入分析了航天信息元数据，总结了航天信息元数据的三个特点：数据 类型的混合性，各种元数据标准中各概念、各维度之间的语义相关性和元数据文 件各维度的层次性，讨论了这三个特点的相关问题，并提出了相应的基本解决思 路。该项工作对应于本文的第二章。 ( 3 ) 针对数据类型的混合性提出了一种适合点和区间混合型维度数据集的多 维索引结构p i 树。p i 树利用超球划分数据集的多维空间，以提高节点存储利 用率，从而降低数据插入时i 0 次数；借鉴r 木树的建树过程并进行相应算法简化， 有效提高了p i 树建树效率；此外，给出了p i 树插入、删除和查询算法的形式化描 述。理论分析和实验结果表明，本文提出的p i 树建树效率高于r ，- c 树，存取数据时 i 0 次数相对减少，检索效率也相应提高。该项工作对应于本文的第三章。 ( 4 ) 针对各种元数据标准中各概念、各维度之间的语义相关性，结合本体的 应用，本文提出了在语义本体指导下的多维索引构建方法和检索方法，解决了各 种类型元数据标准中概念之间“异形同义的问题，并利用维度相关性缩小查询 范围，对改善检索效果和提高检索效率奠定了基础。 第11 页 国防科学技术大学研究生院硕士学位论文 ( 5 ) 针对元数据文件各维度的层次性，结合相关编码技术，提出了一种具有 层次信息的二进制编码方法，表达出了维度的层次信息结构，对查询效果有明显 的改善，并为带有数据挖掘性质的查询提供了可能。第四项工作和第五项工作对 应于本文的第四章。 1 5 2 论文结构 论文共分六章，章节的基本关系如图1 2 所示。 第一章为绪论，总体介绍本文的研究背景，回顾并分析多维索引的各种研究 技术，概述了其发展与应用，在对其研究现状和发展趋势进行综合分析的基础上， 说明了现有工作面临的挑战和本文的研究工作。 第二章从航天信息的需求出发，分析讨论了航天信息元数据的特点以及多维 索引的相关问题，提出了航天信息元数据的三个特点，确定了研究中的问题，并 给出了解决问题的基本思路。 l 第五章 l 航天信息元数据多维索 i 引的应用实例 1r 第六章结论 图1 6 论文结构图 第三章在第二章的分析基础上，以特点一为出发点，参考经典的多维索引结 构，提出了一种适用于点和区间混合型维度数据集的多维索引结构p i 树，并给出 了p i 树插入、删除和查询算法的形式化描述。最后给出了实验证明。 第四章在第二章的分析基础上，以特点二和特点三为出发点，结合本体论和 编码理论提出了一种在语义本体指导下多维索引的构建和查询方法和一种具有维 第1 2 页 国防科学技术大学研究生院硕士学位论文 层次结构的二进制编码方法，这两个方法有助于解决各种类型航天信息元数据概 念、维度语义相关问题以及元数据维度的层次结构问题。 第五章使用一个应用实例将三个问题的解决方法贯穿起来验证所提理论的正 确性和可操作性。 第六章结论，总结了本文工作，展望下一步的研究方向。 第1 3 页 国防科学技术大学研究生院硕士学位论文 第二章航天信息元数据中多维索引相关问题描述与分析 第二章作为全文探讨问题的一个入口，通过分析多维索引在航天信息元数据 中的需求出发，深入讨论了航天信息元数据文件的特点，从特点出发，引出论文 所要解决的三个问题。 本