边界约束的非相交球树实体对象多维统一索引

• 作者: 俞肇元 罗文 胡勇 袁林旺 闾国年
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 多维统一空间索引 非相交球树 空间剖分 空间聚类 实体对象索引
• 年，卷（期）: 2012,（10）
• 所属期刊栏目: 数据库技术
• 页码范围: 2746-2759
• 页数: 14页
• 分类号: TP311
• 字数: 9234字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2012.04214

摘要

针对现有空间索引剖分结构复杂、节点重叠率高及对多维实体对象检索及运算支撑较弱等问题,构建了一种边界约束的非相交球实体对象多维统一空间索引 ;利用球的几何代数外积表达,提出了基于求交算子的直线-平面和直线-球面的相交判定与交点提取方法,建立了多维实体对象体元化剖分方法及包含边界约束的非相交离散球实体填充算法,实现了实体对象空间均匀、非重叠的分割,并在填充球的个数、重叠率以及对象逼近近似度等约束条件上获得了较好的平衡.定义了最小外包球生成与更新的迭代算法与包含球体积修正的批量Neural Gas层次聚类算法,在尽可能保证球树各分支平衡性的前提下,实现了索引层次体系的稳健构建.利用几何代数下球对象间几何关系计算的内蕴性与参数更新的动态性,实现了索引结构的动态生成与更新,进而设计了实体对象表面及其内部任意位置及区域的检索策略及基于实体索引的空间关系计算方法.基于不同实体对象的模拟实验显示,基于几何代数的实体对象索引可以有效实现多维实体对象表面及其内部任意位置及区域的快速检索,并能在有限时间内以较高的精度实现多维实体对象最近邻距离和动态实体对象相交状态的检索.相对于常用球树索引,所提出的索引方法在填充率、节点重叠率、填充误差、体元个数、层次球个数、体积百分比和时间占用等方面均具有明显优势,且不同分辨率剖分条件下的索引结构及空间关系计算精度具有更高的稳健性,可运用于具有较强时间约束下复杂多维动态场景中对象检索与空间关系计算.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡勇	南京师范大学计算机科学与技术学院	25	220	7.0	14.0