面向非易失性内存的持久索引数据结构研究综述

随着非易失性内存从理论走向实用,现代存储系统的设计与实现将迎来颠覆性变革。针对传统存储设备设计的存储系统并不能充分利用非易失性内存带来的性能红利。为了构建高吞吐、低时延、大规模的存储系统,迫切需要设计与非易失性内存硬件特性相匹配的持久索引数据结构,从而进一步提升性能。从持久索引数据结构出发,分别对B+-Tree和哈希表在非易失性内存上的设计和优化进行分析,比较其优缺点,并展望了该方向的机遇与面临的挑战。

基于网格索引的连续Skyline计算方法

考虑按任意顺序随机增删的数据流场景下连续Skyline计算问题,首先基于已有工作提出了一个基本算法BCSC;然后基于"影响区域"的观察,提出了一个基于网格索引数据结构的算法GICSC,其基本思想为:(1)将数据空间划分为若干大小相等的网格,采用网格索引方法对数据点进行组织和管理;(2)用网格将数据空间表示为自由区域和影响区域两部分,发生在自由区域中的数据变化可以从理论上保证不影响计算结果,因此仅需对落于影响区域的数据增删进行运算,从而降低数据规模;(3)算法的计算模块通过逐步扩展的方法,无需遍历全部数据便可获得初始的Skyline集合及影响区域,维护模块通过类似方法计算数据变化对Skyline集合的影响,同时动态更新影响区域的大小.由于没有对数据流特性进行假设限制,因此BCSC和GICSC算法具有更广泛的适应性.理论分析和实验结果均验证了上述方法的有效性.

编码八叉树在多波束测深数据中的应用与分析

多波束测深数据在水下地形地貌研究与应用中具有十分重要的价值。针对多波束测深数据量大,相关处理方法效率低等问题,提出一种基于莫顿编码的八叉树海量点云数据结构。首先,根据点云的包围盒大小及最大深度进行空间划分;然后,对各个节点赋予索引值,并对索引值进行二进制编码,建立基于莫顿编码的八叉树数据结构;最后,以SOR(statistical outlier removal)滤波实验为例,测试提出的数据结构在邻域内快速搜索的效率,结果表明,基于莫顿编码的八叉树数据结构具有更高的搜索效率,对于提高海量测深数据处理效率具有一定参考意义。

更新数据流上的连续Skyline计算

本文考虑"更新数据流"场景下的连续Skyline计算问题。在该环境下,数据不再满足"先进先出"特性,使得传统基于滑动窗口数据流上的连续Skyline计算方法不再适用。在对问题进行了形式化描述后,本文提出了基本算法BUSM,在分析其不足的基础上提出了一种网格索引数据结构,基于该结构提出了GUSM算法。该算法利用了更新数据流中删除和添加操作成对同时出现的特性,以网格为单位表示影响区域并进行快速排除预处理。理论分析和实验结果证明了上述方法在更新数据流上连续计算Skyline的有效性。

Flash存储技术

Flash存储器具有非易失性、固态性、体积小、重量轻、抗震动、高性能、低能耗等特点.近年来,随着容量的提高和价格的降低,Flash存储器在通用计算环境中的应用技术迅速成为研究热点.研究的目的是对Flash存储技术研究现状进行分析、总结,以期为进一步的研究工作提供启发.首先介绍了Flash的存储特性,探讨了其在存储体系结构中地位,并讨论了管理Flash存储器的两种软件体系结构.然后重点分析、总结了Flash存储的各项关键技术的研究现状,包括地址映射机制、垃圾回收机制、磨损均衡策略、基于Flash的buffercache管理策略、基于Flash的索引数据结构以及基于Flash的事务处理技术.最后对Flash存储技术的研究现状进行总结,提出可能的未来研究方向.

网络环境下三维模型的多尺度数据组织方法

本文针对网络环境下海量三维模型数据的传输与可视化要求,探讨了三维模型数据多尺度组织方法。设计了基于点索引的三维模型几何数据结构,结合多尺度纹理表达,构建三维模型多尺度数据结构。在此基础上,基于四叉树结构构建分层分块的三维模型数据多尺度存储结构,从而适应三维模型数据的多尺度分块调度与传输,并通过实验验证该方法能根据三维场景中视点的变化,动态、分块地传输多尺度三维模型数据,快速响应传输请求,保证三维场景绘制效率。