基于图划分抽样算法的图表示学习

在基于神经网络的图表示算法中,当节点属性维度过高、图的规模过大时,从内存到显存的数据传输会成为训练性能的瓶颈。针对这类问题,该方法将图划分算法应用于图表示学习中,降低了内存访问的I/O开销。该方法根据图节点的度数,将图划分成若干个块,使用显存缓存池存储若干个特征矩阵块。每一轮训练,使用缓存池中的特征矩阵块,以此来减少内存到显存的数据拷贝。针对这一思想,该方法使用基于图划分的抽样算法,设计显存的缓存池来降低内存的访问,运用多级负采样算法,降低训练中负样本采样的时间复杂度。在多个数据集上,与现有方法对比发现,该方法的下游机器学习准确率与原算法基本一致,训练效率可以提高2~ 7倍。实验结果表明,基于图划分的图表示学习能高效训练模型,同时保证节点表示向量的测试效果。今后的课题可以使用严谨的理论证明,阐明图划分模型与原模型的理论误差。     

一种基于数字高程模型DEM的淹没区灾害评估方法

采用数字高程DEM来进行洪水淹没分析和灾害评估是GIS水利应用领域的研究前沿,通过对基于种子蔓延算法的淹没区计算及灾害评估方法的分析,将淹没分为有源淹没和无源淹没两种,进而论述了淹没区计算方法的精度及灾害评估和预测的准确性主要取决于数字地面模型DEM空间数据精度和社会经济信息数据的准确性;而种子蔓延算法及空间叠加运算速度则决定了整个模型的效率,该模型已在国家九五地方重大攻关水利项目中得到成功应用。     

采用遥感和GIS技术的洪水痕迹提取与范围估测

针对洪水发生时刻卫星影像数据缺乏的情况,提出了一种延时估测洪水淹没范围的方法。首先采用植被指数法和土壤含水量变化法提取洪水发生前、后植被及土壤遗留下的变化和痕迹,然后利用DEM高程数据进行淹没推算,估测洪水淹没的最大范围。选用Landsat TM、ETM数据以及90m分辨率的DEM数据进行试验。结果表明,在植被覆盖率高、植被种类复杂的平原地区,植被变化痕迹方法可用于估测洪水淹没范围;而在植被覆盖率低、植被种类单一的河谷地区,土壤含水量变化痕迹法更加适用。将估算结果与现场调访数据或洪水发生后一天的影像数据对比显示,不同类型的地貌区选取相适宜的估算方法能够获得较好的洪水淹没范围估算效果。     

基于图形处理器的球面Voronoi图生成算法优化

基于四元三角格网(QTM)之间距离计算与比较的球面Voronoi图生成算法相对于扩张算法具有较高的精度,但由于需要计算并比较每个格网到所有种子点的距离,致使算法效率较低。针对这一问题,利用图形处理器(GPU)并行计算对算法进行实现,然后从GPU共享内存、常量内存、寄存器等三种内存的访问方面进行优化,最后用C++语言和统一计算设备架构(CUDA)开发了实验系统,对优化前后算法的效率进行对比。实验结果表明,不同内存的合理使用能在很大程度上提高算法的效率,且数据规模越大,所获得的加速比越高。     

大型3D场景漫游系统内存管理

在大型3D场景漫游系统中,单个资源(如模型、纹理)所需内存较大且分配和释放频繁,为了防止内存碎片的产生并提高内存分配速度,提出了一种新型内存管理方法.根据程序需求首先划分出一块或多块大的虚拟内存区域,然后基于所划分的内存区域进行内存分配和回收管理.在该管理方法中,对于程序中的小资源,使用内存池;对于大的资源,则使用伙伴系统内存管理方法.实验结果表明,该内存管理方法高效且稳定.     

利用可编程GPU实现大规模地形场景的高性能漫游*

对已有算法进行了综述,并针对数据动态调度、自适应网格模型的生成以及数据的组织与数据裁剪等方面进行了研究并提出改进方法,设计了一种基于GPU编程实现的大规模地形场景的实时绘制与漫游算法。利用GPU端完成地形网格更新、地形块的自动选取、高度图和纹理图采样等大部分计算工作,大大减轻了CPU端的计算负载。实验表明,该算法实现简单,内存开销较少,有效提高了地形绘制的效率,适于大规模地形场景的实时高效漫游。     

Spark环境下并行立方体计算方法

针对传统联机分析处理(OLAP)处理大数据时实时响应能力差的问题,研究基于分布式内存计算框架Spark加速的数据立方体计算方法,设计基于Spark内存集群的自底向上构造(BUC)算法——BUCPark,来提高BUC的并行度和大数据适应能力。在此基础上,为避免内存中迭代的立方体单元膨胀,基于内存重复利用和共享的思想设计改进的BUCPark算法——LBUCPark。实验结果表明:LBUCPark算法性能优于BUC算法和BUCPark算法,能够胜任大数据背景下的快速数据立方体计算任务。     

统一设备计算架构下的栅格河网提取并行算法

针对大规模高分辨率数字地形数据提取栅格河网效率低下的问题,提出了基于统一设备计算架构(CUDA)利用淹没模型提取栅格河网的并行算法。使用图形处理器(GPU)将汇流累积量计算分解为独立的多任务并行处理,通过数据异步传输减少数据交换时间,进而加速河网提取的运算。实验结果表明,该算法运行效率明显优于串行河网提取算法,在NVIDIA Geforce GTX660上对数据量为600 MB(网格大小为9784×8507)数字高程模型(DEM)数据提取河网加速比达到62。     

基于DEM的Priority-flood并行填洼算法优化

针对大尺度数字高程模型无法适应单机内存，导致单机串行填洼算法无法计算的情况，对Barnes提出的并行PF填洼算法加以优化。基于spark实现了由Barnes提出的并行PF填洼算法，同时针对单张DEM未切分的情况，对该算法加以改进，设计了带光环的切分策略等一系列方法，将原算法一二阶段的同步处理变为异步，节约了原算法耗时。在进行2 600亿单元(10 m数据集)的填洼实验中，该方法与原方法填洼结果一致，且比原算法缩短了37%的处理时间，提高了并行填洼的计算效率。     

一种基于洪水消退模型的快速分水岭算法

基于洪水消退思想从反方向建立一个新的分水岭算法模型.用提取截面曲线局部极大值代替传统算法的淹没过程.实验结果表明此算法较传统算法减少了计算量和内存占用量,而且可以与识别结合,让识别来控制分割算法复杂度,有效降低了计算量和过分割.     

高性能快速地形漫游算法

高性能地形漫游是GIS、虚拟现实及军事模拟中的研究热点。大规模地形算法一般都是通过将部分数据常驻内存,并采取各种方法来简化地形、,加速绘制。该文通过对地形分块,使用背面剔除及改进的视点误差来进行LOD细节层次处理;。提出基于屏幕误差包围盒的地平线遮挡剔除技术,提高算法的效率;。采用内存映射文件方式进行DEM数据的加载,实现高性能海量数据的处理。     

基于格网划分的大数据集DEM三维可视化

提出基于格网划分的实时LOD分层方法，该方法基于DEM和影像数据固有的栅格特点，使用简单的几何算法即可实现DEM数据的动态分层，计算量小，可实现对大数据集DEM数据的实时漫游。     

基于分布式图计算的学术论文推荐算法

针对海量论文数据导致的应用效率低下问题,提出一个基于层次混合模型的推荐算法WSVD++。该模型根据学术论文良好的结构特征,构建一个加权的论文二部图模型。首先对论文进行特征提取,按不同特征的权重构建论文的复合关系图;其次对关系图采用一种改进的PPR算法,计算每篇论文的重要程度,依此来对用户—论文关系进行加权;然后在构建好的加权二部图模型上混合SVD++图算法进行推荐。实验结果表明,改善了推荐算法学术论文的推荐效果,并且基于分布式图计算框架GraphX,扩展性好,适合大数据处理。     

Accelerating Louvain community detection algorithm on graphic processing unit

The Louvain community detection algorithm is a hierarchal clustering method categorized in the NP-hard problem. Its execution time to find communities in large graphs is, therefore, a challenge. Parallelization is an effective solution for amortizing Louvain's execution time. In this paper, we propose an adaptive CUDA Louvain method (ACLM) algorithm that benefits from the graphic processing unit (GPU). ACLM uses the shared memory in GPU, as well as the optimal number of threads in the GPU blocks. These features minimize parallelization overhead and accelerate the calculation of modularity parameters. The proposed algorithm allocates threads to each block based on the number of required streaming multiprocessors (SMs) and warps on GPU. The implementation results show that ACLM can effectively accelerate the execution time by 77% compared to the competitive method in the large graph benchmarks.

     

Spark平台下类别数据互信息计算的并行化

针对大规模类别数据的互信息计算量非常大的问题,利用Spark内存计算平台,提出了类别数据的并行互信息计算方法,该算法首先采用列变换将数据集转换成多个数据子集;然后采用两个变长数组缓存中间结果,解决了类别数据特征对间互信息计算量大、重复性强的问题;最后在配备了24个计算节点的Spark集群中,使用人工合成和真实数据集验证了算法。实验结果表明,该算法在效率、可伸缩性和可扩展性等方面都达到了较高的性能。     

基于并行图计算的社区划分方法

以图计算形式研究社交网络由来已久,但对于如何提升图计算应用于大规模社交网络的计算速度和扩展性,一直是研究的难点。谱图论的应用为社交网络在图计算方面的研究带来新的研究热点,谱图分割为社交网络社区划分带来基于结构的支撑。为了解决谱图论在处理大规模社交网络时存在计算缓慢、内存溢出等问题,本文提出了谱聚类改进算法结合矩阵方式在并行环境下的处理方法。首先,利用Spark对网络数据进行并行化预处理,将社交网络以图结构表示,再将图转化为Spark分布式稀疏矩阵。然后,将谱聚类改进算法在Spark环境下,实现并行化社交网络社区快速划分,并以分布式方式持久化存储源数据、中间计算数据和计算结果,提高图计算在社交网络中的可靠性。最后,通过实验证明并行化图计算方法能有效提高计算速度和扩展性,支持大规模社交网络的挖掘分析,实现并行算法下高并发、高吞吐的特点。     

Accelerating ARTS

A major fraction of ray-tracing computation time is spent on ray-object intersection calculation. To reduce this calculation cost, one method, ARTS, subdivides the 3-D object space into voxels and uses a 3-D line-drawing routine to simulate ray propagation in the subdivided space to select objects for intersection testing. Finer space subdivision gives better object selection resolution and fewer ray-object tests. However, as the subdivision increases, the improvement is offset by a linear degradation of the line-drawing-routine efficiency and a cubic growth of the memory requirement. We solve these time and memory scalability problems in ARTS using an adaptive 3-D line-drawing algorithm, which traverses space with multiple stepsizes, and a hybrid database that employs both the octree and the 3-D array data structures. The space traversal cost in our solution grows logarithmically with the subdivision increase, and the memory requirement grows only linearly.     

隐蔽流树方法的分析与改进

利用隐蔽流树方法搜索隐蔽通道时,获得的操作序列中只有极少部分真正构成隐蔽通道,增加了后续手工分析的工作量。为此,提出一种改进的隐蔽流树方法。根据信息流图进行建树,设计信息流规则,并给出隐蔽流树的自动分析算法。以一个文件系统为例进行分析,结果验证了改进方法的正确性。     

VAOS克里金插值在三维地震属性平面图的应用

三维地震属性数据巨大,在实际应用中一般采用局域克里金插值算法进行插值。目前常用的指定距离半径、指定点数、kd-tree等搜索算法均涉及距离计算、遍历已知点,相对较为费时。对此,提出一种无须距离计算、无须遍历已知点而直接利用待插值点位置的增减实现邻域点的选取方法(VAOS),以高效实现克里金插值。经过实验验证,在同精度下,该算法比距离半径搜索法快数十倍。