基于并行计算的多副本空间数据离散布局策略

根据空间数据的特点及其关系, 提出一个负载均衡的空间矢量数据布局目标, 并结合特定环境, 采用基于图着色理论的空间数据布局算法及多副本的数据安全机制, 提高了空间数据部署在并行环境下, 数据节点上任务的执行效率和数据安全性. 实验结果表明, 该布局方法能实现数据的均衡布局, 兼顾了并行计算的效率和安全性, 适应并行计算下更多的查询应用.     

MapReduce模型下基于R树索引的Skyline查询算法

提出一种MapReduce并行计算模型下基于R树索引的Skyline查询算法, 解决了海量空间数据集下执行Skyline查询效率低的问题. 通过建立R树索引实现空间数据不同粒度的范围剪枝, 有效降低了分布式Skyline查询需扫描的数据规模, 提高了在MapReduce模型下Skyline查询的执行效率. 在不同数据分布下进行对比实验的结果表明, 该方法比已有算法在执行效率上更具优势.     

基于JBPM和角色分组的并行路由算法

JBPM在流程的推进过程中要选择相应的路径进行流转,其中并行路由是一种最为复杂的路径选择方法.但初始化路经参数时,并行路由算法节点定义复杂,需要预先定义子路径流程模板,并且逐一对XML文件节点赋值导致效率较低.针对这一问题,提出了一种基于JBPM与角色分组的并行路由算法.该算法引用角色分组的理论,通过运用角色查询单个分组的方法将并行路由分支参数初始化,生成多个并行子路径节点信息,进而将每个节点信息分组存放数据库中,对数据进行统一处理,提高初始化子路径参数的效率.改进后的算法应用到房地产OA办公系统的请假会签功能中,在实践上取得良好效果,满足业务流程灵活多变的需求.     

一种基于Hadoop的大规模图最短路径查询方法

图的最短路径查询作为图论的经典问题,广泛应用于现实世界的许多应用中.然而随着图的规模日益增大,传统单机环境下的查询算法已无法满足大规模图的处理需求.为解决上述问题,提出基于Hadoop的大规模图最短路径查询方法(D-CH方法):首先利用经典的图分割算法(CNM算法)将存储于Hadoop分布式文件系统(HDFS)中的大规模图进行分割,给出了适于后续算法的标记分割结果;然后将查询区分为分割后子图内查询和子图间查询,基于MapReduce编程模型分别给出相应的并行化查询处理算法.实验结果表明,D-CH方法对大规模图的最短路径查询具有良好的执行效率.     

基于元素区间编码的GML数据索引方法

根据GML数据查询的需要,在分析XML文档编码和空间索引技术的基础上,提出一种基于扩展的元素区间编码的GML索引方法.首先通过扩展的区间编码方法对GML文档中的元素、属性、文本、几何体等要素进行编码;其次依据元素编码算法并将非空间节点、空间节点、元素节点从GML文档树中分离,产生元素编码序列;在此基础上根据节点类型的不同对属性和文本节点建立B+树索引以实现值查询,对几何体节点建立R树索引以实现空间数据的分析操作,并在查询处理时通过查询优化算法避免不必要的节点的遍历,进一步提高查询效率.实验结果表明,基于元素区间编码的GML数据索引方法是可行的、高效的.     

基于多粒度的异质图表示

异质图表示学习旨在将图中的语义信息和异质的结构信息嵌入到低维向量空间中。目前大多数的异质图表示学习方法主要通过基于元路径、元图和网络模式的采样以保留图中同类型节点间的单粒度局部结构,忽略了现实世界中复杂异质图具有的丰富的层次结构。商空间理论中的多粒度思想可以在不同粒度内捕获节点间的潜在联系。因此,为在异质图表示中有效地保留层次结构的信息,文章提出一个基于多粒度的异质图表示方法（Heterogeneous Graph Representations Based on Multi-granularity,HeMug）。该方法首先基于不同元路径构建多个同质子图,并利用多粒度的粗化思想,将每个同质子图分别粗化形成多个多粒度子网络,以保留异质图中同类型节点在给定元路径下的层次结构。其次,利用多粒度的细化思想,将每个多粒度子网络最粗层通过现有表示学习方法获得的节点表示逐层细化,以得到节点在每个多粒度子网络下的表示。最后,设计注意力机制以融合节点在不同元路径对应的多粒度子网络下的表示。在四个真实数据集上的实验结果表明,与对比算法相比,提出的HeMug获得了更有效的节点表示。     

基于OpenMP的并行集合包含查询算法

集合包含查询分为子集、等值和超集3种查询,在多个领域有重要的研究意义和应用价值.随着集合数据集规模的不断增大,迫切需要提高集合包含查询的效率.集合包含查询并行化是解决这一问题的一条途径,基于OpenMP提出并行子集、等值和超集查询算法,这些算法采用反向索引结构,通过for循环并行化实现查询间的并行执行.为提高算法效率,设计2个高效的并行共享数据结构:1PVEC结构:用于存储并行查询结果.2CountArr数组:针对超集查询,用于对反向列表中的元素计数,并行线程可异步地对这两个结构进行访问.在MSWEB和DBLP 2个数据集上进行扩展实验,结果表明,实现的3种并行集合包含查询具有较高的效率,对3种查询在MSWEB数据集上均可达到4X以上的加速比.     

能量有效的传感器网络不规则区域时空查询处理算法

为了减少不规则区域时空查询处理的能量消耗和提高查询结果准确性,该文提出了一种基于树的不规则区域时空数据收集查询算法,该算法将查询区域内的节点组织成一颗树,树中的节点依次将其感知数据发送至其父节点直至汇聚到树的根节点.针对不规则区域时空聚集查询,提出了一种基于路线的算法,该算法沿一条路线收集查询区域内节点的感知数据并对其进行聚集以生成最终的查询结果.这两种算法均通过将复杂的不规则查询区域划分为简单的凸多边形,降低了判断节点是否在查询区域内的计算复杂度,且保证仅查询区域内的节点发送感知数据,减少了能量消耗.仿真实验结果表明,该文提出的算法优于现有的针对规则区域的时空查询处理算法.     

图形处理器上CSB~+-树索引的并行构建算法

为提高缓存敏感CSB+-树索引的操作效率,在图形处理器(GPU)上研究CSB+-树的并行构建和查询性能.通过分析索引树内部节点的每一键与对应叶子节点的映射关系,提出了一种一次性并行构建CSB+-树所有内部节点键值的无锁并行算法,以最大并行度来快速构建索引树.该算法通过设计GPU平台上支持CSB+-树的索引数据任意伸缩的动态数组来解决GPU上不能动态分配显存空间的问题,通过在索引内部节点的边界增加填充位来减少线程块的线程分支数,从而提高CSB+-树的查询效率.实验结果表明,文中所提算法的运行时间比基于单个节点和基于树层的并行算法分别提高了31.0和1.4倍.     

基于并行模式挖掘和路径匹配的用户位置预测

为了提高移动用户位置预测的精度,提出了基于并行模式挖掘和路径匹配的移动用户位置预测方法,对传统的FP-GROWTH算法作了并行化处理,优化了节点负载分配方法,在Spark平台下挖掘用户移动频繁模式.改进了基于索引的路径相似度算法,提出基于路径最短距离的相斥度算法,提高了对轨迹数据缺失的适用性.在真实的用户轨迹数据集上实验表明,提出的基于轨迹相斥度预测方法相比马尔可夫模型和卡尔曼滤波模型拥有更高的预测精度,预测精确度平均提升7%左右.     

分组遗传算法用于图的着色

图的着色算法是一种典型的NP 完全问题 在系统地讨论了图的正常顶点着色、边着色以及全着色的有关理论的基础上 ,提出了基于分组遗传算法和启发式搜索的图的正常 k 点着色 ,正常k 边着色以及正常k 全着色的新型混合算法 ,提出了评价算法性能的标准 实验仿真结果表明 ,新型混合算法可以获得问题高质量的解 ,即对图进行着色所使用的颜色数接近图的色数     

应用思维进化计算求解顶点着色问题

应用思维进化计算求解顶点着色问题,给出求解给定图的色数、最小着色的算法。介绍了顶点着色问题的编码与解码方法、特征、信息矩阵的概念,从而应用思维进化计算的趋同和异化求解该问题。实验结果表明该算法是求解顶点着色问题的一种新的有效算法。     

大数据分析中基于 MapReduce 的空间权重创建方法研究

大数据空间分析是 Cyber-GIS 的重要方面。如何利用现有的网络基础设施（比如大规模计算集群）对大数据进行并行分布式空间分析仍然是一大难题。为此,提出一种基于 MapReduce 的空间权重创建方法。该方法依托Hadoop 框架组织计算资源,基于 MapReduce 模式从大规模空间数据集中高效创建出空间权重：大空间数据被分为多个数据块,将映射器分布给计算集群中的不同节点,以便在数据中寻找出空间对象的相邻对象,由约简器从不同节点处收集相关结果并生成权重文件。利用 Amazon 公司弹性 MapReduce 的 Hadoop 框架,从人工空间数据中创建基于邻近概念的权重矩阵进行仿真。实验结果表明,该方法的性能优于传统方法,解决了大数据的空间权重创建问题。     

一种应用于图着色问题的新型混合遗传算法

将遗传算法与模拟退火方法和禁忌搜索方法结合,提出了应用于图着色的混合遗传算法.在混合方法中,模拟退火算法用于局部寻优,提高算法的收敛速度,同时防止早熟收敛;禁忌搜索算法通过记忆能力防止进化过程出现循环来提高全局寻优能力.用遗传算法进行全局搜索,并与贪婪遗传算法和Dsatur算法进行了比较,结果表明,混合遗传算法的寻优质量优于对照算法.这种改进的混合遗传算法可以在稠密图上获得更好的寻优效率,在稀疏图上其效率则略有下降,这表明设计的改进混合遗传算法的合理性和有效性.     

基于邻接矩阵的网络流量检测点选取算法研究

为对网络流量进行有效检测,考虑网络节点的流守恒,把网络流量检测点选取问题抽象为无向图的弱顶点覆盖问题.基于图论中邻接矩阵的概念,在满足对任意顶点度数大于2的假设条件下,提出一个求解弱顶点覆盖问题的近似算法.通过将求解弱顶点覆盖集中点与边的关系转化为点与点的关系,降低了矩阵计算复杂度.仿真实验表明,与现有算法相比,新算法能够选取出更小的弱顶点覆盖集,部署更少的网络流量检测点,减轻了由网络流量数据收集造成的额外负担.     

基于遗传和启发式算法的混合顶点着色算法

图的着色问题是一种典型的NP-完全问题.提出了基于遗传算法和启发式算法的新型混合顶点着色算法,该算法在实现过程中涉及到染色体的编码方法、适应度函数的设计以及遗传算子的选择等.实验仿真结果表明此算法改善了求解的时间复杂度,可以获得问题高质量的解.     

基于弹性分布数据集的海量空间数据密度聚类

为了快速挖掘大规模空间数据的聚集特性,在cluster_dp密度聚类算法基础上,提出了一种基于弹性分布数据集的并行密度聚类方法 PClusterdp.首先,设计一种能平衡工作负载弹性分布数据集分区方法,根据数据在空间的分布情况,自动划分网格并分配数据,使得网格内数据量相对均衡,达到平衡运算节点负载的目的;接着,提出一种适用于并行计算的局部密度定义,并改进聚类中心的计算方式,解决了原始算法需要通过绘制决策图判断聚类中心对象的缺陷;最后,通过网格内及网格间聚簇合并等优化策略,实现了大规模空间数据的快速聚类处理.实验结果表明,借助Spark数据处理平台编程实现算法,本方法可以有效实现大规模空间数据的快速聚类,与传统的密度聚类方法相比具有较高的精确度与更好的系统处理性能.     

路和圈幂图的邻点可区别E-全染色

以一个简单图G为基础,连接G的任意最短路长为k的2个顶点就可得到基础图G的k-幂图,研究了路的k-幂图和圈的2-幂图的邻点可区别E-全染色问题,并结合该类幂图的结构性质,运用构造法、反证法和穷举分类染色技术给出了其邻点可区别E-全色数,为确定图的各类染色问题提供了有效的借鉴.