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

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

基于扩展时空距离度量的连续k近邻查询方法

针对基于TPR树索引的连续k近邻查询,引入了一种新的时空距离度量最小最大距离函数作为TPR树索引搜索时节点剪枝上界。提出了一种采用最优优先策略的基于扩展时空距离度量的连续k近邻查询STM-CNN算法,利用最小距离函数进行TPR树索引节点搜索时访问排序,并使用最小最大距离函数对TPR树索引进行剪枝界定。     

基于历史轨迹的城市出租车移动概率模型

对出租车的移动轨迹进行建模分析是重要的研究内容,模型需要反应节点的移动状态信息,支持用户能够对移动出租车节点进行快速查询与搜索。本文针对无法在线实时获取移动出租车实时状态信息的条件下,根据对历史轨迹信息的处理分析,提出将隐马尔科夫理论应用到城市出租车移动轨迹模型中,通过实际数据的分析建立出租车运动模型,通过对模型的计算来预测节点的位置分布概率,并在此模型上针对不同的用户需求进行查询处理,为用户提供搭车路线决策支持。通过利用真实数据集的实验证明,本文提出的方法能够较好的模拟出出租车节点的运动状态,用户也能够从模型中获取较高精度的位置状态信息。     

一个基于引用的高效连接算法

针对对象关系数据模型和查询语言的新特点 ,提出了一个基于引用的高效连接算法Sort Loop。引用既是对象关系数据模型中一种重要的建模设施 ,同时它也有利于连接算法的设计和高效实现 ,如Hash Loops就是基于指针、面向集合属性的连接算法。Sort Loop克服了Hash Loops算法在数据访问方式和内存使用上存在的不足 ,性能分析表明 ,其性能优于Hash Loops。     

基于CPCRLB和动态成簇机制的混合WSN目标跟踪算法

针对传统的基于静态节点的无线传感器网络（wireless sensor network,WSN）电池容量有限、节点移动受限的问题,提出了一种基于条件后验克拉美-罗下界（conditional posterior cramer-rao lower bounds,CPCRLB）的混合WSN的目标跟踪调度算法。该算法引入移动节点来参与目标跟踪,根据目标预测位置对移动节点进行运动控制,同时利用基于CPCRLB的信息效用函数选择静态节点,实现每一时刻目标的动态成簇策略。此外,还提出了一种基于运动学的预测机制,利用分区域管理的方法进一步提高跟踪精度,减少能量消耗,并能够有效避免目标丢失现象。仿真结果表明,该算法可以有效地对目标进行跟踪,在保证跟踪精度的同时相比静态网络节省了大量的能耗。     

基于访问特征负载预测的负载均衡算法

为了提高web集群负载均衡的效果,结合web服务用户访问静动态内容的特征,提出了一种基于访问特征负载预测的负载均衡算法。首先建立网络带宽负载和CPU、内存综合性能负载的小波包一支持向量机回归混合预测模型;然后根据用户请求的类型,结合负载预测的结果对任务进行分配和调度。仿真结果表明：与传统的基于负载预测的负载均衡算法相比,基于访问特征负载预测的负载均衡算法能达到更好的负载均衡效果,从而有效提高web集群的整体性能。     

递归划分的标签约束可达性计算方法

现实世界中的图往往在结点和边上包含描述信息,可达性查询是图数据管理和挖掘中的基本操作之一。针对图数据中标签约束的可达性计算问题,提出一种基于递归划分的可达性计算方法 RP-Hop。该算法基于层次划分思想,利用独立集性质,在保持标签和可达性前提下对大规模图进行递归划分,并结合贪婪扩展思想和递归编码,为标签约束的可达性查询提供压缩索引。经过合成和真实数据集上的实验,结果表明,RP-Hop算法不仅降低了索引大小和构建时间,而且提高了查询效率。     

依据历史轨迹构建城市出租车移动概率模型

针对无法在线实时获取移动出租车实时状态信息的条件下,根据对历史轨迹信息的处理分析,提出将隐马尔科夫理论应用到城市出租车移动轨迹模型中,通过实际数据的分析建立出租车运动模型,通过对模型的计算来预测节点的位置分布概率,并在此模型上针对不同的用户需求进行查询处理,为用户提供搭车路线决策支持。通过利用真实数据集的实验证明,模型能够较好的模拟出出租车节点的运动状态,用户也能够从模型中获取较高精度的位置状态信息。     

动态环境中无人作战飞机的滚动航路规划

提出了一种应对威胁环境信息动态变化的滚动航路规划方法。借鉴预测控制滚动优化理论,研究了航路的规划过程和滚动窗口内局部子目标与局部子规划,描述了算法步骤,讨论了算法收敛性。该算法不仅适用于二维空间或三维空间的实时滚动规划,而且还可以扩展成为一种针对动态环境和移动目标通用的模型框架。仿真结果表明,算法能够找到一条满足约束、整体较优的可行航路。     

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

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

一种基于范围表示B树的大容量IPv6路由查表算法

IPv6具有巨大的地址空间,未来要面对的将会是海量IPv6路由表,而且128位的IPv6地址比IPv4需要更多的访存数。算法针对IPv6路由查找问题中的这两个难点,提出利用B树高度较低的优良性质,将前缀转化为范围表保存在B树中,并在结点内部利用分段范围比较树算法来减少访存次数和空间耗费。理论分析和实验表明,该算法能够以很好的性能支持IPv6海量路由表的查找。     

On convexity proofs in location theory

It is often assumed in the facility location literature that functions of the type ø_i(x_i, y) = β_i[(x_i-x)²+(y_i-y)²]^K/2 are twice differentiable. Here we point out that this is true only for certain values of K. Convexity proofs that are independent of the value of K are given.     

Nonlinear one-parametric linear programming and t-norm transportation problems

Previous methods for solving the nonlinear one-parametric linear programming problem min {c(t)^Tx |Ax = b, x ≥ 0} for t ? [α,β] were based on the simplex method using a considerably extended tableau. The proposed method avoids such an extension. A finite sequence of feasible bases (B^k | k = 1, 2, …, r) optimal in [t^k, t^k+1] for k = 1, 2, …,^r with α = t¹ < t² < … < t^r+1 = β is determined using the zeroes of a set of nonlinear functions. Computational experience is discussed in the special case of t-norm transportation problems.     

基于态势预测的无人机防相撞控制方法

针对无人机自主飞行过程中,受空中非协作移动目标威胁较大,且空中移动威胁存在高机动性的特点,提出一种预测移动威胁情况下的无人机防撞控制方法,该方法采用交互多模(IMM)算法预测移动威胁的运动状态,同时利用滚动时域控制(RHC)思想建立无人机运动控制模型,构造有约束目标函数,运用微分进化算法(DE)求解目标函数,获取最优控制量,输入控制模型,完成防撞机动控制。仿真结果表明,该方法可以有效解决空中多架航空器同时入侵的防撞问题。     

一种融入运动特性的显著性特征提取方法

针对复杂背景下图像序列中运动目标的跟踪前检测问题,提出一种融入运动特性的显著性特征提取方法,该方法综合目标的灰度、细节和运动等形成稳健的显著性特征,并得到一组显著性特征提取图.在这组图像中,具有这种多特征的区域得到加强,其他区域受到抑制,从而能够轻松地检测出可引起人类视觉注意的运动目标.由于该算法中的显著性特征来源于目标的多种底层特性,因此该算法具有很强的稳健性.实验证明,这种方法具有较强的稳定性和实用性,抗干扰能力强.从视觉效果的角度出发,能够较大地提高运动目标在复杂背景中的信杂比.     

Cell structure of microcellular combustible object foamed by supercritical carbon dioxide

In order to solve the issue that the combustible objects for cased telescoped ammunition (CTA) didn't burn completely during the combustion process, the microcellular combustible objects were foamed with numerous cells in the micron order to improve the combustion performance by the supercritical carbon dioxide (SCCO₂) foaming technology. As the cell structure determined the combustion properties of microcellular combustible objects, the solubility of SCCO₂ dissolved into the combustible objects was obtained from the gravimetric method, and scanning electron microscope (SEM) was applied to characterize the cell structure under various process conditions of solubility, foaming temperature and foaming time. SEM images indicate that the cell diameter of microcellular combustible objects is in the level of 1 μm and the cell density is about 10¹¹ cell⋅cm⁻³. The microcellular combustible objects fabricated by the SCCO₂ foaming technology are smooth and uniform, and the high specific surface area of cell structure can lead to the significant combustion performance of microcellular combustible object for CTA in the future.     

An extension of the (szwarc) truck assignment problem

In this journal in 1967. Szware presented an algorithm for the optimal routing of a common vehicle fleet between m sources and n sinks with p different types of commodities. The main premise of the formulation is that a truck may carry only one commodity at a time and must deliver the entire load to one demand area. This eliminates the problem of routing vehicles between sources or between sinks and limits the problem to the routing of loaded trucks between sources and sinks and empty trucks making the return trip. Szwarc considered only the transportation aspect of the problem (i. e., no intermediate points) and presented a very efficient algorithm for solution of the case he described. If the total supply is greater than the total demand, Szwarc shows that the problem is equivalent to a (mp + n) by (np + m) Hitchcock transportation problem. Digital computer codes for this algorithm require rapid access storage for a matrix of size (mp + n) by (np + m); therefore, computer storage required grows proportionally to p². This paper offers an extension of his work to a more general form: a transshipment network with capacity constraints on all arcs and facilities. The problem is shown to be solvable directly by Fulkerson's out-of-kilter algorithm. Digital computer codes for this formulation require rapid access storage proportional to p instead of p². Computational results indicate that, in addition to handling the extensions, the out-of-kilter algorithm is more efficient in the solution of the original problem when there is a mad, rate number of commodities and a computer of limited storage capacity.     

二维 DFT 和 DCT 的 Systolic 阵列

超级计算中一个活跃的研究领域是将某些有限和,如离散富里叶变换(DFT)、离散余弦变换(DCT),映射到多处理机阵列上。本文首先通过二维DFT的行列分解算法流程图,给出了计算二维DFT的二种Systolic阵列:一种是由N_1个处理器组成的线性阵列,所花时间步为O(N_1N_2)(设二维DFT为N_1×N_2长的),与行列分解算法在单处理机上顺序执行所花时间相比,加速比为O(N)(设N_1=N_2=N)。这一结果无论是在时间消耗,还是在PE数量上都是目前最优的。另一种是由N_1×N_2个处理器组成的矩形阵列,所需时间为O(N_1+N_2),与行列算法在单处理机上顺序运行所花时间相比,加速比为O(N~2)(这里仍假定N_1=N_2=N)。本文还给出了二维DCT的与二维DFT相似的Systoilc阵列结构。不难将上述阵列推广到多维的情况。     

基于检测的人体跟踪算法

传统的目标跟踪算法需要人为标定跟踪区域,且受到漂移问题的影响。为了解决这些困难,针对人体跟踪问题,提出了一种新的基于检测的跟踪算法。为了减少漏跟踪,使用了多个检测算子,用来定位多个身体部位,将其检测结果映射到一个相同的身体区域。为了适应快速运动的目标,使用KLT跟踪和凝聚聚类将检测窗口连接起来形成人体轨迹。实验结果表明:使用多个检测算子明显地提高了跟踪性能;KLT跟踪对于快速运动目标具有适应能力。该算法基本满足实时性。     

An algorithm for separable piecewise convex programming problems

We present a branch and bound algorithm to solve mathematical programming problems of the form: Find x =|(x₁,…x_n) to minimize Σ?_i0(x₁) subject to x?G, l≦x≦L and Σ?_i0(x₁)≦0, j=1,…,m. With l=(l₁,…,l_n) and L=(L₁,…,L_n), each ?_ij is assumed to be lower aemicontinuous and piecewise convex on the finite interval [l_i.L_i]. G is assumed to be a closed convex set. The algorithm solves a finite sequence of convex programming problems; these correspond to successive partitions of the set C={x|l ≦ x ≦L} on the bahis of the piecewise convexity of the problem functions ?_ij. Computational considerations are discussed, and an illustrative example is presented.