并行I/O技术研究

从分析提高I／O性能的途径开始，对在分布主存的高性能计算机中利用存储系统并行性来完成数据访问的并行文件系统所涉及到的问题进行了分析和探讨，最后介绍了几个著名的并行文件系统。     

基于数据分割的复制算法RSREPL的研究与实现

针对分布存储系统的本质特点，提出了基于数据分割的复制算法RSREPL。性能测试结果表明，与传统的复制算法相比，RSREPL能够提供更高的可用性、持久性和安全性，并且具有较低的系统开销。     

基于高斯模型的不确定数据流Skyline查询方法

由于数据的动态性及不确定性等特征,使得不确定数据流上Skyline查询研究面临挑战.不确定对象一般采用多元概率密度函数(PDF)表示,现有的不确定数据流Skyline查询方法均采用离散型随机变量建模.然而不确定数据流中的对象可能是连续变化的,离散模型对连续性随机变量难以适用.针对连续PDF建模的不确定数据流Skyline查询进行了研究,提出了基于高斯模型的不确定数据流Skyline查询方法(SGMU),该方法包含2个过程:1)动态高斯建模算法(DGM):对滑动窗口采样并建立高斯模型,将原始的数据流转化为不确定对象PDF的参数流;2)提出了基于高斯树的查询算法(GTS)以建立空间索引结构和执行Skyline查询.实验结果表明,SGMU算法不仅能够对连续型不确定对象进行有效建模以辅助Skyline查询,而且能够有效地减少查询对象个数,提高Skyline查询效率.     

n-of-N 数据流模型上高效概率Skyline 计算

研究概率数据流上的q-skyline计算问题.与只支持滑动窗口数据流模型的已有方法相比,所提出的方法能够支持更为通用的n-of-N数据流模型.采用将q-skyline查询转换为区间树上刺入查询的方法支持n-of-N数据流模型.提出PnNM算法维护支持n-of-N数据流模型所需的相关数据结构,高效处理了不确定对象候选集合更新和区间更新等维护工作;提出PnNCont算法实现连续查询处理.理论分析和实验结果表明,算法能够有效地支持概率数据流n-of-N模型上的q-skyline查询处理.     

一种基于语义吸引的节点规模估计方法

节点规模是各种分布式应用的基础信息,节点波动的大规模网络环境要求节点规模估计方法具有较高的估计精度和较强的鲁棒性,已有的节点规模估计方法多侧重于某个方面的优化而未能充分权衡计算精度和鲁棒性.提出一种基于语义吸引的节点规模估计方法——SEBSA(a network size estimation method based semantic attraction).SEBSA将每个节点标识所对应的实数区间上的哈希值作为语义信息,节点通过与哈希值临近的节点周期性地交换哈希空间上的邻居信息,以快速吸引与自己哈希值最近的一组节点,测量该组节点哈希值的平均间距以估计节点规模.理论分析和实验结果表明,相对于已有方法,SEBSA在节点频繁波动的网络环境中仍然能够快速地提供准确的节点规模信息.     

DKNNS:面向延迟敏感型应用的可扩展精确分布式K近邻搜索算法研究

为了降低用户访问延迟,延迟敏感型网络应用需要选择合适的邻近服务节点响应用户访问请求.分布式K近邻搜索通过可扩展的选择距任意用户节点邻近的K个服务节点,可以有效满足网络应用延迟优化的目的.已有工作在精确度以及可扩展性等方面存在不足.针对可扩展精确的K近邻搜索问题,文中提出了分布式K近邻搜索方法DKNNS(distributed K nearest neighbor search).DKNNS将大量的服务节点组织为邻近性感知的多级环,通过最远节点搜索机制选择优化的K近邻搜索初始化节点,然后基于回退方式快速的在目标节点邻近区域发现K个近邻.基于理论分析,模拟测试以及真实环境下的部署实验发现,在不同规模的节点集合下,DKNNS算法能够确定近似最优的K个服务节点.且DKNNS的查询延迟,查询开销均显著低于Meridian算法.最后,DKNNS的返回结果相对于Meridian具有较高的稳定性.     

基于超节点网络的多源并行数据分发研究

在P2P系统中,同一个数据往往拥有多个副本,这些副本分布在网络的不同节点上,为并行分发提供了可能.然而在传统的数据分发中,只有单一的源节点参与分发,这种模式不但浪费了系统中存在的多个副本资源,而且容易使单一的源节点成为系统的瓶颈.为了更有效地利用系统中存在的多个副本资源,提高分发的效率和系统的性能,提出了一个基于超节点网络的多源并行数据分发算法PPMSD,通过一个基于超节点网络的结构化拓扑来组织系统中的数据和索引,使得数据的查询和定位效率控制在O(log N)以内;根据分发速率动态地为每个数据源分配相应比例的分发数据量,并行地向目标节点传输数据以最小化分发时间;最后,实现了原型系统PPThor以验证算法的有效性.测试结果表明分发的效率得到了极大的提高.     

一种基于动态组播树的可靠数据分发方法

已有的数据分发方法多侧重于某方面的优化,不能充分权衡数据分发的可靠性与高效性,难以满足应急场景下可靠快速分发数据的要求.为此,提出一种基于动态组播树的可靠数据分发方法.根据节点间延迟信息对节点进行层次化分簇和编号,以此构建层次化覆盖网,根据节点编号采用基于动态组播树的前缀匹配路由.理论分析和实验结果表明,与MEDYM方法相比,即使短时间内系统中产生大量消息,该方法仍能够可靠快速地分发数据,系统开销较小.     

基于半连接的并行查询处理算法的研究

多元连接查询的并行执行是并行数据库的研究重点,传统的并行查询处理算法没有利用面向对象数据库及其查询的特点,算法效率较低.借鉴分布式数据库查询处理中基于半连接的优化思想,提出了基于半连接的并行查询处理算法.性能评价表明了其实用性和有效性.     

一种基于关键属性的优化数据一致性维护方法

针对关键属性更新的易描述、更新项较小和弱相关性三个特点。提出一种基于关键属性的优化数据一致性维护方法.在该方法中,首先分离出用户提交的更新请求中关于关键属性的更新;然后采用基于延迟.覆盖的更新传播模型进行更新传播,即基于副本间的网络延迟选择具有最大和最小网络延迟的结点转发更新,并在传播过程中记录和综合考虑更新的确定传播和不确定传播两条路径;在对关键更新冲突分类的基础上,采用更新缓冲区和更新日志两层更新协商机制并结合最新写胜出和分而治之规则,优化关键更新冲突的发现和解决:更新日志信息是方法中各种策略开展的基础,讨论了更新日志中信息管理方法以及结点失效和网络划分发生时信息的维护方法.关键属性更新的优化处理使得不会产生因为关键属性更新的延迟而降低系统基于关键属性的资源定位效率,满足面向Internet的P2P系统的要求.模拟测试结果表明,该方法在一致性维护开销、资源定位开销与资源访问开销以及鲁棒性方面均具有较好的性能.