一种分布式数据库多元连接查询优化算法及改进

论文对于分布式数据库中的多元连接查询提出了一种优化算法。该算法产生的操作序列具有全局优化特征。在远程网中,采用最小生成树算法,生成最佳的连接序对能使得总的代价达到最小。而在局域网中,采用改进的最小生成树算法,生成尽可能多的并行连接序对,最大程度地应用并行性,使得响应时间最小。     

基于城市安全知识图谱的多关键词流式并行检索算法

我国智慧城市安全概念的普及和建设的逐渐落地,以及大数据在智慧城市安全建设方面的深度应用,对关键词检索的处理响应速度提出了更高的要求。针对这一问题,提出了基于城市安全知识图谱的流式知识图谱多关键词并行检索算法(MKPRASKG),该算法能够根据用户输入的查询关键字,通过关联类图的构建、剪枝和融合操作实时构建基于知识图谱实体的查询子图集,再结合评分函数,以高评分的查询子图为指引,在知识图谱实例数据中进行并行搜索,最终返回Top-k查询结果。实验结果证明,该算法在实时搜索、响应时间、搜索效果以及可扩展性等方面均具有较大的优势。     

基于数据网格环境的连接操作算法

数据网格是一种分布式数据管理体系结构，能够为分布在网格中的资源提供协同的管理机制．数据库管理系统在数据网格中发挥着重要作用，在各种数据库操作中，连接操作是一种最常用也是最耗时的操作，到目前为止，尚未有文献提出数据网格环境下的连接操作算法．主要对数据网格环境下海量数据的连接操作算法进行了研究，针对网格中各结点之间网络带宽异构的特点，采取关系缩减算法、行分块传输技术和流水线并行机制来减少查询的响应时间．理论分析和实验结果证明，算法在减少网络通信开销、增加I／0和CPU并行、降低响应时间方面具有较好的性能．     

基于直方图的并行结构连接算法

连接操作是最昂贵且常用的数据库操作．在传统数据库系统中，主要的连接操作是等值连接操作，因此，传统的并行连接算法主要集中于并行等值连接操作．另外，随着XML在Web应用中变得越来越重要，XML已经成为Internet上一种新的数据交换标准．对XML数据的连接操作不同于传统数据库中的等值连接操作，它属于结构连接操作．以前适合等值连接操作的并行连接算法并不能有效地解决结构连接问题．因此，第1次提出了并行结构连接问题，并且通过应用直方图的思想于并行连接中，从而提出两种基本的并行XML结构连接算法、等高直方图连接算法和等宽直方图连接算法．实验表明这两种算法具有较好的性能．     

并行数据库基于多连接的查询优化算法的研究

多表连接查询是并行数据库中的一种常用且重要的操作,然而基于传统遗传算法所制定的多表连接查询计划,往往存在查询响应时间长的缺陷。根据无共享并行数据库的特点,将一种新的代价估计模型引入到传统遗传算法中,并对传统遗传算法进行了改进。实验证明改进后的遗传算法能制定出更优的查询计划,从而减少多表连接时的查询响应时间。     

矢量多边形栅格化算法快速并行化方法研究

本文在分析典型多边形栅格化算法的基础上,研究了串行算法并行化思路,提出一种多边形栅格化算法并行框架。该并行框架包括MPI与OpenMP的双层并行模式、顾及负载均衡的矢量多边形数据划分方法、多边形栅格化基本算子调用接口。利用本文形成的并行框架对扫描线算法、边界代数法进行了并行化,并利用大规模土地现状数据验证本文所提出的并行化方法的有效性。试验结果表明,该方法能够解决矢量多边形栅格化串行算法快速并行化的问题,并行化后的算法大大减少了矢量多边形转换时间,具有良好的并行效率。     

面向共享内存结构的并行Delaunay网格生成算法

针对目前大多数并行Delaunay网格生成算法对共享内存结构利用不充分,不能够利用超级计算机多层次体系结构优势的情况,提出了一种充分利用共享内存结构的基于算法并行模式的并行Delaunay网格生成算法。通过对候选点集进行高效划分来实现插点操作的并行,增大了一次选择之后进行并行插点的点集规模。使用OpenMP并行模型对所提出算法进行并行实现,并和串行开源软件Triangle进行了对比。实验结果表明算法能够将候选点集划分成互不冲突的子集进行并行处理,在保证网格质量的同时具有较好的并行效率。     

一种基于移动代理的并行路由算法研究*

提出了一种基于移动代理的并行路由算法,通过对网络节点间的多条并行链路的充分利用,提高网络带宽的利用率,减少移动代理从源节点到目的节点的迁移响应时间。仿真实验结果表明,与著名的蚁群算法和遗传算法的性能相比,该并行路由算法具有更高的网络利用率,同时具有更短的平均延迟时间,提高了应用系统的运行效率。     

基于三维胞元空间的MA双向并行路由算法

针对传统移动代理(MA)在监测无线传感器网络(WSNs)的感兴趣信息时产生的延迟较大和能耗较多问题,提出了基于三维胞元空间的MA双向并行(3D-BPMA)路由算法.3D-BPMA将MA与传统的客户/服务器(c/S)模式相结合,在胞元内利用C/S模式搜集信息,在单层胞元系统和路由器与路由器之间采用MA双向并行的策略进行传输.仿真结果表明:3D-BPMA与LCF,DSG-MIP算法相比减少了平均响应时间和网络平均能耗,提高了MA发送率.     

基于半连接的分布式数据库查询优化算法探讨

采用连接操作实现分布式数据查询时,不仅代价较高而且费时。若利用半连接查询操作取代连接操作,可以通过缩减操作数获得查询优化。而两次半连接对接算法可以更大限度地缩减操作数,实现起来更为简单、高效。针对多节点的数据查询,提出了通过最小生成树算法生成并行的连接序对,并由两次半连接对接算法进行查询优化处理的算法。应用该算法可以有效利用多节点的并行性缩短系统的查询响应时间,降低系统的总开销。算法在海量信息查询中具有实用价值。     

A semi-transparent selective undo algorithm for multi-user collaborative editors

Multi-user collaborative editors are useful computer-aided tools to support human-to-human collaboration. For multi-user collaborative editors, selective undo is an essential utility enabling users to undo any editing operations at any time. Collaborative editors usually adopt operational transformation (OT) to address concurrency and consistency issues. However, it is still a great challenge to design an efficient and correct OT algorithm capable of handling both normal do operations and user-initiated undo operations because these two kinds of operations can interfere with each other in various forms. In this paper, we propose a semi-transparent selective undo algorithm that handles both do and undo in a unified framework, which separates the processing part of do operations from the processing part of undo operations. Formal proofs are provided to prove the proposed algorithm under the well-established criteria. Theoretical analysis and experimental evaluation are conducted to show that the proposed algorithm outperforms the prior OT-based selective undo algorithms.     

An adaptive large neighborhood search heuristic for solving a robust gate assignment problem

With the rapid growth of air traffic demand, airport capacity becomes a major bottleneck within the air traffic control systems. Minor disturbances may have a large impact on the airport surface operations due to the overly tight schedules, which results in frequent gate conflict occurrences during airport’s daily operations. A robust gate schedule that is resilient to disturbances is essential for an airport to maintain a good performance. Unfortunately, there is no efficient expert system available for the airport managers to simultaneously consider the traditional cost (the aircraft tow cost, transfer passenger cost) and the robustness. To fill this gap, in this paper, we extend the traditional gate assignment problem and consider a wider scope, in which the traditional costs and the robustness are simultaneously considered. A mathematical model is first built, which leads to a complex non-linear model. To efficiently solve this model, an adaptive large neighborhood search (ALNS) algorithm is then designed. We novelly propose multiple local search operators by exploring the characteristics of the gate assignment problem. The comparison with the benchmark algorithm shows the competitiveness of proposed algorithm in solving the considered problem. Moreover, the proposed methodology also has great potential from the practical perspective since it can be easily integrated into current expert systems to help airport managers make satisfactory decisions.     

一种用于中值滤波的改进均值划分算法

图像滤波是很多图像处理算法在图像预处理阶段采用的处理措施,而中值滤波不仅能够有效地去除图像中的噪声,而且可以保持图像的边缘细节,从而成为首选的图像滤波方法.由于中值滤波需要使用排序操作,其计算时间复杂度较高,而且在滤波窗口较大时,导致图像滤波耗费较长的时间,不能满足海量、高分辨率图像实时滤波处理的需求.在研究中值滤波基础上,提出一种改进的基于均值划分的快速中值滤波算法,实验表明,该算法可以有效地降低图像中值滤波的时间消耗,特别是在大尺度图像中,当滤波窗口较大时,能够显著降低图像滤波时间,同时,能够与传统中值滤波保持一致的效果,进一步增强了大尺度图像实时处理能力.     

DNA计算机算术运算的自装配模型(Ⅲ)—减法

DNA计算是基于DNA分子生化反应,能够在DNA计算机上实现的算法。它具有高度并行性、容量大、速度快等特点。同传统电子计算机一样,它也是以加、减、乘、除等简单算术运算和异或等逻辑运算为基本运算单元。在DNA自装配加法的基础上,设计了一般的DNA自装配并行减法模型,算法的时间复杂度为O(1),空间复杂度为O(n),并通过实例验证了算法的有效性。算法的主要优点在于编码简单、效率高,且具有通用性。     

基于链码的分水岭变换算法

为了快速准确地进行图像分割，通过对现有分水岭变换算法的分析，并借鉴图像处理中常用的链码思想，提出了基于链码的分水岭变换算法，并首先扩展了传统链码的定义，将其分为指出链码和指入链码；然后提出并阐述了利用链码实现分水岭变换的两个性质；最后给出了基于链码的分水岭变换算法的具体描述，并详细分析了新算法的时间和空间复杂度。实验结果表明，新算法具有较低的时间和空间复杂度，且变换结果更有利于后续的图像理解。     

基于位运算的固件代码变量区间分析法

变量区间分析是程序代码数据流分析的重要部分。固件反汇编代码存在字节运算和位运算两类运算,当变量取值范围较大时,依次迭代法不能高效地分析经位运算后的结果的取值区间。提出一种快速位运算方法,即根据变量取值区间范围,先将变量转化为不确定位形式再进行位运算;提出一种区间生成算法,即把不确定位形式转化为区间来实现字节运算。实验结果表明,该基于位运算的固件代码变量区间分析方法在程序变量取值范围较大时效率远远高于依次迭代法,而且在各种变量取值区间范围内所需时间稳定,并随着区间范围的增大,其有略微下降趋势。     

Spatial join processing using corner transformation

Spatial join finds pairs of spatial objects having a specific spatial relationship in spatial database systems. Since spatial join is a fairly expensive operation, we need an efficient algorithm taking advantage of the characteristics of available spatial access methods. In this paper, we propose a spatial join algorithm using corner transformation and show its excellence through experiments. To the extent of authors' knowledge, the spatial join processing using corner transformation is new. In corner transformation, two regions in one file joined with two adjacent regions in the other file share a large common area. The proposed algorithm utilizes this property in order to reduce the number of disk accesses for spatial join. Experimental results show that the performance of the algorithm is generally better than that of the R*-tree based algorithm proposed by Brinkhoff et al. (1993. 1994). This is a strong indication that corner transformation is a promising category of spatial access methods and that spatial operations can be performed better in the transform space than in the original space. This reverses the common belief that transformation will adversely effect the clustering. We also briefly mention that the join algorithm based on corner transformation has a nice property of being amenable to parallel processing. We believe that our result will provide a new insight towards transformation-based processing of spatial operations     

基于单亲遗传算法混合动态规划的电动汽车充电调度优化策略

充电调度是电动汽车运营的一个重要内容,合理有效的充电策略在帮助运营商降低成本的同时还能减轻电网高峰时段的供电负担。从充电站运营商的角度出发,在实时电价和每个充电任务时间必须连续的假设下,建立了一个电动汽车充电成本最小模型,给出一个单亲遗传算法混合动态规划的两阶段常规充电调度算法。与电桩一旦闲置即刻分配车辆进行充电的策略以及传统单亲遗传算法相比较,该充电调度策略在电桩负载均衡的情况下有效降低了电费成本,说明了算法的有效性。此外,实验结果表现出了充电任务在多数相同时段聚集从而避开高电价时段的特征,说明充电策略对减轻高峰时段的电网压力也有一定帮助。     

量子混沌和分数阶Fourier变换的图像加密算法

针对传统的自然混沌系统安全性低的问题,提出了量子混沌和分数阶Fourier变换的图像加密算法。通过引入量子Logistic混沌映射,解决了Logistic映射存在的周期窗口、伪随机和非周期性不好等缺陷,还改善了计算机进行浮点数运算丢失精度的问题。同时将混沌系统和分数阶Fourier变换相结合,实现了介于空间域和频域的分数域置乱,克服了传统一些方法只在单一域变换和单纯使用某一种方案而导致参数变量少,系统结构简单,直方图不均匀等缺点。实验和仿真结果表明,该算法具有密钥空间大,计算复杂度低,敏感性强等优点,能够有效地抵御统计分析攻击。     

高效RSA算法的研究与并行实现

RSA算法依赖于大数的运算,实现起来较为困难,并且对计算机速度、容量等要求较高。针对上述问题,提出一种有效的解决方案,即将大整数分解成小整数进行相乘以提高幂乘运算速度,并给出改进的负载均衡并行算法,进一步提高计算速度。实验结果表明,与传统的RSA算法相比,该算法在计算速度上有明显的提高,具有较好的可扩展性。