基于R-树索引的Map-Reduce空间连接聚集操作

空间连接聚集是一种常用并且非常耗时的空间数据库操作,特别是在面对大规模空间数据集时,单机运行环境难以满足其对时空开销的需求,如何设计高效的面向云计算环境中的分布式空间连接聚集算法越来越受到人们关注。Map-Reduce作为云计算的核心模式受限于其扁平化的串行扫描操作模型,常被用来加速非索引的空间连接操作,现有工作尚无将Map-Reduce和R-树索引结合来处理空间连接聚集。因此,提出了基于R-树索引的Map-Reduce空间连接聚集算法(RSJA-MR)来更高效地返回连接聚集结果。提出一种分布式R-树索引结构以支持大规模空间数据的索引,RSJA-MR算法利用分布式R-树生成任务集,任务集的执行满足无依赖并行计算模式,很容易在Map-Reduce框架中进行表达。文中提出一种实时缓存策略以支持索引并发访问。实验结果表明:相比非索引的Map-Reduce连接聚集算法,在空间交叠连接聚集查询上,时间性能最少提升8%,在空间包含连接聚集查询上,时间性能最少提升近35%。     

采用单位四元数的旋转约束RRT路径规划

针对船舶虚拟原型设计时装配拆卸路径规划中的旋转约束问题,提出了一种基于快速随机探索树的旋转约束路径规划算法。该算法首先针对三维空间中的旋转提出了一种新的单位四元组随机采样函数,然后将单位四元数内积引入到C空间距离度量函数中,对路径中的旋转变化量进行控制。实验证明:该算法能够对刚体的旋转范围进行有效控制,同时还降低了运动过程中的旋转变化量。     

改进蚁群算法在P2P网络资源搜索中的应用

针对P2P网络搜索算法中冗余查询消息过多,资源搜索效率低的问题,提出了基于改进蚁群算法的P2P资源搜索算法,算法中在选择邻节点查询时,综合考虑到本地资源情况、邻节点资源情况、邻节点资源相似度等因素,尽量避开了资源搜索中的恶意节点,并改进了基本蚁群算法的状态转移规则,从而避免了查询消息的盲目发送。仿真实验表明,与传统资源搜索算法K-radom-walks和Flooding相比,该算法在搜索命中率和带宽利用率方面有明显提高。     

基于蒙特卡洛树搜索方法的空战机动决策

针对空战中双方的机动决策问题,考虑角度、距离、速度变化以及高度优势函数,以赢取最大空战优势期望为目标,建立空战双方机动决策模型,并引入蒙特卡洛树搜索方法进行求解,搜索策略采取极大极小搜索算法。针对双机对抗,通过仿真给出空战态势及空战优势变化曲线,结果表明我机在整个空战过程中绝大部分是处于优势地位的,验证了使用蒙特卡洛树搜索方法进行空战机动决策的可行性,同时对算法的实时性进行了仿真,结果表明算法计算机动动作所用时较短,达到了算法的实时性要求。     

一种基于模糊熵的特征选择算法

特征选择是模式识别中的一个重要组成部分。针对分类边界模糊的样本集,将模糊集的理论应用到特征选择中,通过对特征进行模糊化,定义一种模糊熵来度量特征的分类区分度,再采用相关系数度量特征间的冗余度,建立判定树。则树中的节点即为选择出的特征,树枝为特征的隶属度函数,且通过判定树进行的分类可以实现样本识别的模糊化。     

一种篱笆图构造线性分组码的软判决解码技术

本文讨论的线性分组码的软判决解码技术,是用(n,k)线性分组码的校验矩阵H来构造该码的篱笆图,在图上搜索出一条具有最小路径软距离的路径作为解码输出,因而可达到最大似然解码性能。还讨论了如何减少搜索路径数的方法。     

基于信息增益和相关性的判定树特征选择算法

特征选择是模式识别中需要解决的一个重要问题.针对已知类标号的样本集合,从特征的分类信息和特征间相关性2个方面出发,提出了一种基于信息增益和相关性的判定树特征选择算法.该算法是一种有监督方法,先采用信息增益度量特征的分类区分度,采用相关系数度量特征的冗余度,然后建立判定树,则树中的节点即为选择出的特征.     

求解布尔不可满足子式的消解悖论算法

求解布尔不可满足子式在超大规模集成电路设计与验证领域都具有非常重要的理论与应用价值,帮助EDA工具迅速定位错误与不一致。针对求解不可满足子式的非完全方法,提出了消解悖论与悖论解析树的概念,在此基础上提出一种启发式局部搜索算法。该算法根据公式的消解规则,采用局部搜索过程直接构造证明不可满足性的悖论解析树,而后递归搜索得到不可满足子式;算法中融合了布尔推理技术、动态剪枝方法及蕴含消除方法以提高搜索效率。基于随机测试集进行了实验对比,结果表明提出的算法优于同类算法。     

一种适用于点和区间混合型维度数据集的多维索引

点和区间混合型维度数据集是空间数据库系统和GIS中重要的数据对象.在分析SS树的基础上,提出了一种适用于索引点和区间混合型维度数据集的索引结构--PI树.PI树利用超球划分数据集的多维空间,以提高结点存储利用率,从而降低数据插入时的I/O次数.文章给出了PI树插入、删除和查询算法的形式化描述.理论分析和实验结果表明,所提的PI树性能上总体优于R·树.     

适用于战术通信的路由度量策略改进分析

提出了将基于ETT度量的路由策略应用于多种带宽并存的战术通信网络中,克服了传统的采用基于跳数、距离等度量方式的路由选择策略的局限性。并使用OPNET对采用基于ETT度量的路由协议与传统的基于最小跳数度量的路由协议进行仿真,并对仿真结果进行分析比较,得出两种策略在特定网络仿真场景下性能的优劣差异。     

辅助任务增强的中文跨域NL2SQL算法

自然语言到结构化查询语言(natural language to structured query language,NL2SQL)任务旨在将自然语言询问转化为数据库可执行的结构化查询语言(structured query language,SQL) 语句。本文提出了一种辅助任务增强的中文跨域 NL2SQL 算法,其核心思想是通过在解码阶段添加辅助任务以结合原始模型来进行多任务训练,提升模型的准确率。辅助任务的设计是通过将数据库模式建模成图,预测自然语言询问与数据库模式图中的节点的依赖关系,显式地建模自然语言询问和数据库模式之间的依赖关系。针对特定的自然语言询问,通过辅助任务的提升,模型能够更好地识别数据库模式中哪些表/列对预测目标 SQL 更有效。在中文 NL2SQL 数据集 DuSQL 上的实验结果表明,添加辅助任务后的算法相对于原始模型取得了更好的效果,能够更好地处理跨域 NL2SQL 任务。     

延迟驱动的FPGA高扇出信号线快速布线算法

采用基本的延迟驱动Pathfinder布线器对FPGA高扇出信号进行布线,大部分时间会用于初始化寻路的优先级队列,而初始化工作主要是将已得到的布线树中的布线资源结点插入优先级队列.但是分析发现,并非所有被插入的资源结点对布线都是有帮助的.因此提出了一种基于树剪枝的优先级队列初始化算法,这种算法对已有的布线树中的资源点进...     

A non-myopic scheduling method of radar sensors for maneuvering target tracking and radiation control

In decades, the battlefield environment is becoming more and more complex with plenty of electronic equipments. Thus, in order to improve the survivability of radar sensors and satisfy the requirement of maneuvering target tracking with a low probability of intercept, a non-myopic scheduling is proposed to minimize the radiation cost with tracking accuracy constraint. At first, the scheduling problem is formulated as a partially observable Markov decision process (POMDP). Then the tracking accuracy and radiation cost over the future finite time horizon are predicted by the posterior carmér-rao lower bound (PCRLB) and the hidden Markov model filter, respectively. Finally, the proposed scheduling is implemented efficiently by utilizing the branch and bound (B&B) pruning algorithm. Simulation results show that the performance of maneuvering target tracking was improved by the improved interacting multiple model (IMM), and the scheduler time and maximum memory consumption were significant reduced by the present B&B pruning algorithm without losing the optimal solution.     

Interception in a network

This paper presents an algorithm for determining where to place intercepting units in order to maximize the probability of preventing an opposing force from proceeding from one particular node in an undirected network to another. The usual gaming assumptions are invoked; namely, the strategy for placing the units is known to the opponent and he will choose a path through the network which, based on this knowledge, maximizes his probability of successful traverse. As given quantities, the model requires a list of the arcs and nodes of the network, the number of intercepting units available to stop the opposing force, and the probabilities for stopping the opposition at the arcs and nodes as functions of the number of intercepting units placed there. From these quantities, the algorithm calculates the probabilities for placing the unit at the arcs and nodes when one intercepting unit is available, and the expected numbers of units to place at the arcs and nodes when multiple intercepting units are available.     

稀疏平衡变分自动编码器的文本特征提取

针对文本特征提取方面的高维数据特征区分度较低、基于规则的特征学习的自学习性能差、变分自动编码器存在过度剪枝等问题,提出稀疏平衡变分自动编码器(Sparse Balanced Variational AutoEncoder,SBVAE)的文本特征提取模型.为消除噪声干扰,提高文本特征提取模型的鲁棒性,在文本特征提取的输入...     

卫星中断容忍网络路由算法研究

针对卫星网络易中断、长时延等问题,提出一种适合卫星DTN网络的路由算法——SDTNR算法。该算法在节点缓存中设置了3个存放不同服务等级报文的队列,队列根据报文响应比排序,响应比小的报文优先发送。SDTNR算法根据卫星运行规律,建立节点选择表并实时更新该表,根据表中信息选择满足条件的节点作为下一跳节点,以此保证通信的可靠性。仿真结果表明,SDTNR与EPR、PR、FC 3种算法相比,SDTNR更好地提高了报文的投递率、降低了网络开销和平均时延。     

声纳浮标网络节点GPS信息的无冲突共享协议

节点位置信息对声纳浮标网络的建立具有十分重要的意义,利用它可以完成节点身份划分、路由建立等工作.鉴于传统GPS广播方式的低效性,提出了一种GPS共享协议,并利用网络仿真软件OPNET仿真证明:该协议能够以无冲突方式快速实现网络节点GPS信息的共享和拓扑结构的自辨识.同时,针对GPS所固有的定位偏差问题,提出了一种网络节点GPS求精算法,OPNET仿真证明:该算法可提高对网络整体拓扑结构的把握精度.     

基于DJI分步实现的联机空间距离查询处理

综合考虑了查询处理时的计算费用和存储费用,提出了距离连接索引(Distance associatedJoinIn dices,DJI)的分步实现方法,以高效地支持联机空间距离查询。该方法采用分阶段计算DJI的策略,根据用户的查询条件动态地计算DJI的一部分以支持查询。实验研究证明,与传统方法相比,DJI的分步实现方法在性能上具有较大优势。     

受互联网思路启发的电力系统重要节点评估算法

对电力系统中重要节点进行有效区分,有助于在资源有限的条件下对重要节点施加额外保护或改变拓扑结构,从而提高系统鲁棒性、降低事故发生的概率。受网页排序算法启发,提出电气链接结构分析的随机方法(electrical stochastic approach for link structure analysis, E-SALSA)用于电力系统重要节点评估。该算法综合考虑了电力系统拓扑结构、潮流等因素对节点的影响,能够有效反映电力系统的真实情况,并且其特点更符合电力系统背景。在IEEE300节点电力系统中,使用失负荷规模和最大子群规模两个指标对E-SALSA算法与电气介数算法、基于共同引用的超链接引导的主题搜索(model based on co-citation hypertext induced topic search, MBCC-HITS)算法进行了对比分析。结果证明E-SALSA算法相比电气介数算法在两个指标上都具有优势,相比MBCC-HITS算法能够更综合考虑各方面因素对节点的影响,进而证明了E-SALSA算法的合理性、有效性。     

Generalized orienteering problem with resource dependent rewards

We introduce a generalized orienteering problem (OP) where, as usual, a vehicle is routed from a prescribed start node, through a directed network, to a prescribed destination node, collecting rewards at each node visited, to maximize the total reward along the path. In our generalization, transit on arcs in the network and reward collection at nodes both consume a variable amount of the same limited resource. We exploit this resource trade‐off through a specialized branch‐and‐bound algorithm that relies on partial path relaxation problems that often yield tight bounds and lead to substantial pruning in the enumeration tree. We present the smuggler search problem (SSP) as an important real‐world application of our generalized OP. Numerical results show that our algorithm applied to the SSP outperforms standard mixed‐integer nonlinear programming solvers for moderate to large problem instances. We demonstrate model enhancements that allow practitioners to represent realistic search planning scenarios by accounting for multiple heterogeneous searchers and complex smuggler motion. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013