基于时空相关性预测的运动估计的优化

运动估计的方法不仅在视频压缩技术中得到广泛的应用,而且也在高质量的视频帧频转换中起到了越来越重要的作用。如何提高运动估计所得到的运动矢量的质量,从而得到更高质量的插入帧图像,是文中研究的目的。在分析比较了现有的几种运动估计算法的基础上,提出了一个优化方法。该方法利用了分水岭算法对视频图像的物体进行正确分割,得到了被识别物体的最优的运动矢量。实验结果表明,该优化方法能够优化所有基于时空相关性预测的运动估计的算法的运动矢量,得到的插入帧图像的质量更高,因而具有较强的实用性。     

基于时空相关性预测的运动估计的优化

运动估计的方法不仅在视频压缩技术中得到广泛的应用,而且也在高质量的视频帧频转换中起到了越来越重要的作用。如何提高运动估计所得到的运动矢量的质量,从而得到更高质量的插入帧图像,是文中研究的目的。在分析比较了现有的几种运动估计算法的基础上,提出了一个优化方法。该方法利用了分水岭算法对视频图像的物体进行正确分割,得到了被识别物体的最优的运动矢量。实验结果表明,该优化方法能够优化所有基于时空相关性预测的运动估计的算法的运动矢量,得到的插入帧图像的质量更高,因而具有较强的实用性。     

大规模时空轨迹数据连接查询效率优化实践

本文提出一种低集群计算资源条件下, 大规模轨迹类数据同时空关系的快速连接查询算法DPCP-CROSS-JOIN. 该算法通过对轨迹数据时间字段进行分段交叉编码和位置网格化等方式对连续的轨迹数据离散化, 并以日期和网格区域编码进行两级分区存储. 通过交叉“等值”连接查询, 实现时空连接查询的三级索引、四级加速, 将$n\cdot n $对象间同时空关系连接查询时间复杂度从O(n²)降为O(nlogn). 在Hadoop集群上使用Hive和TEZ等进行大规模轨迹数据连接查询时能将连接查询效率最高提升到30.66倍. 该算法以时间段编码作为关联条件, 巧妙绕开连接过程中复杂表达式的实时计算, 以“等值”替代复杂表达式计算连接, 提高MapReduce任务并行度, 提升集群存储和计算资源利用率. 在面对仅使用一般优化已几乎无法完成的, 更大规模类似任务, 仍能在数分钟内完成. 实验表明, 该算法具有高效和稳定等特性, 尤其适用低“算力”资源条件下大规模轨迹数据的同时空关系连接查询. 此方法还可作为时空轨迹伴随查找, 对象间关系亲密度判定等的原子算法, 可广泛应用于维护国家安全、社会治安秩序, 预防和打击犯罪, 辅助城乡规划统筹等领域.     

基于预测分析的时空众包在线任务分配

针对时空众包在线任务分配问题,提出任务范围调节算法DMRA与基于预测分析的在线任务分配算法PAMA。DMRA算法以任务位置为中心,根据工人密度动态调整任务的范围。PAMA算法基于历史统计概率,采用贝叶斯分类器预测下一时间戳的对象分布情况,在此基础上,执行带权二分图最优匹配算法以完成任务分配。实验结果表明,将DMRA算法与PAMA算法相结合,能够提升任务分配的总效用,降低工人的差旅成本,任务分配性能优于贪心算法与随机阈值算法。     

基于代价的过程动态变更

通过实例说明工作流运作阶段存在多种动态变更途径;并采用矩阵表示过程的数据流和控制流,利用矩阵变换找到所影响范围内所有可能变更途径;最后对它们作代价分析,求出最佳变更途径.     

基于代价的XML路径索引构建

处理路径表达式是XML查询技术中的难点和热点．在本实验室提出的XML路径表达式索引-结构化映射的基础上．为了降低构建索引所需的空间开销，本文提出了构建路径索引的代价模型，并设计了基于给定查询负载，有选择地构建路径索引的相应算法，为给定查询负载自动选择近最优索引模式（NOIS）．本文还提出了当查询效率发生变化时，系统对索引模式进行自适应调整的策略．实验研究表明：使用本文方法，系统可在不影响路径表达式处理效率的前提下，大大降低路径索引的空间开销，取得查询收益和空间开销的较佳权衡．     

An Adaptive and Cost-Based Intrusion Response System

An Adaptive and Cost-Based Intrusion Response System (ACBIRS) is presented in this paper. The designed system analyzes alerts from the Intrusion Detection System (IDS) and evaluates the attack cost, based on the probable damage of attacks on the protected system. Later on, a response is deployed to thwart the attack and prevent the attacker from reaching his/her goals. The proposed response selection approach is a cost-based method that considers attack features, including type of the attack, severity of the attack, value of targeted host/hosts services, and their data to prioritize alerts. Alerts will be responded with respect to their priorities. The selected responses are based on a measure called Response Merit (RM). The balance between attack damage cost, response cost together with the effectiveness of the response to countermeasure previous attacks determine the RM. In contrast to other Intrusion Response Systems (IRS), ACBIRS not only consists of the attack and response measures but also includes response feedback supervision that is proposed in this paper for the first time. ACBIRS allows responses to be adaptive in changing environments through success and failure assessment of previously deployed responses. Experiments show that ACBIRS can successfully prevent 92% of intrusions with only 3% disruption on benign traffic.     

面向季节性时空数据的预测式循环网络及其在城市计算中的应用

实际生活中有很多带有季节特征的时空数据,在城市计算领域分布尤广,例如交通流量数据便具有较为明显的以天或周为周期的统计学特征.如何有效利用这种季节特征,如何捕捉历史观测与待预测数据之间的相关性,成为了预测此类时空数据未来变化趋势的关键.传统时序建模方法将时序数据分解为多个信号分量,并使用线性模型来进行预测.此类方法具有较强的理论基础,但对于数据的平稳性要求过于严格,难以预测趋势信息复杂的数据,更不适用于高维的时空数据.然而在真实场景下,季节性时空数据的周期长短可变,且不同周期的对应关系往往并不固定,存在时间、空间上的模式变化与偏移,很难作为理想的周期信号以传统时序方法建模.相比之下,深度神经网络建模能力更强,可拟合更为复杂的数据.近几年有许多工作研究了如何利用卷积神经网络和循环神经网络来处理时空数据,也有一些工作讨论了如何有效利用周期性信息提升预测的准确性.但深度神经网络受困于梯度消失和误差累积,难以捕捉时序数据中的长时间依赖,且少有方法讨论如何在深度神经网络中有效建模上述具有弹性周期对应关系的时空信号.本文针对真实场景下季节性时空数据的上述问题,给出具有弹性周期对应关系的时空数据预测问题的形式化定义,并提出了一种新的季节性时空数据预测模型.该模型包含季节网络、趋势网络、时空注意力模块三个部分,可捕捉短期数据中的临近变化趋势和长期数据中隐含的季节性趋势,并广泛考虑历史周期中的每个时空元素对未来预测值的影响.为了解决深度循环网络难以捕捉时序数据中的长时间依赖的问题,本文提出一种新的循环卷积记忆单元,该单元将上述模块融合于一个可端到端训练的神经网络中,一方面实现了时间和空间信息统一建模,另一方面实现了短期趋势特征与历史周期特征的统一建模.进一步地,为了解决季节性数据中的各周期时空元素对应关系不固定的问题,本文探讨了多种基于注意力模块的时空数据融合方式,创新性地提出一种级联式的时空注意力模块,并将其嵌入于上述循环卷积记忆单元内.该模块建模记忆单元的隐藏状态在不同周期内的弹性时空对应关系,自适应地选取相关度高的季节性特征辅助预测.实验部分,我们选取了两个时空数据预测在城市计算中最为典型的应用:交通流量预测和气象数据预报.本文所提出的时空周期性循环神经网络在北京、纽约的交通流量数据集、美国气象数据集上均取得了目前最高的预测准确性.     

Cost-Based Arc Consistency for Global Cardinality Constraints

A global cardinality constraint (gcc) is specified in terms of a set of variables X={x ₁,...,x _p} which take their values in a subset of V={v ₁,...,v _d}. It constrains the number of times each value v _iV is assigned to a variable in X to be in an interval [l _i,u _i]. A gcc with costs (costgcc) is a generalization of a gcc in which a cost is associated with each value of each variable. Then, each solution of the underlying gcc is associated with a global cost equal to the sum of the costs associated with the assigned values of the solution. A costgcc constrains the global cost to be less than a given value. Cardinality constraints with costs have proved very useful in many real-life problems, such as traveling salesman problems, scheduling, rostering, or resource allocation. For instance, they are useful for expressing preferences or for defining constraints such as a constraint on the sum of all different variables. In this paper, we present an efficient way of implementing arc consistency for a costgcc. We also study the incremental behavior of the proposed algorithm.     

基于代价的闪存数据库缓冲区置换算法

提出一种基于闪存硬盘(solid state disk,简称SSD)的自适应缓冲区管理算法CBLRU,其将数据页的置换代价与其驻留内存的影响相结合,为每个数据页附加一个权值,当发生页缺失问题时,选择具有最小权值的数据页进行置换,从而可以在延长修改页驻留缓冲区的同时,避免某些修改页长期占用缓冲区中有效空间问题的发生.由于...     

Structural Join and Staircase Join Algorithms of Sibling Relationship

The processing of XML queries can result in evaluation of various structural relationships. Efficient algorithms for evaluating ancestor-descendant and parent-child relationships have been proposed. Whereas the problems of evaluating preceding-sibling-following-sibling and preceding-following relationships are still open. In this paper, we studied the structural join and staircase join for sibling relationship. First, the idea of how to filter out and minimize unnecessary reads of elements using parent＇s structural information is introduced, which can be used to accelerate structural joins of parent-child and preceding-sibling-following-sibling relationships. Second, two efficient structural join algorithms of sibling relationship are proposed. These algorithms lead to optimal join performance： nodes that do not participate in the join can be judged beforehand and then skipped using B^＋-tree index. Besides, each element list joined is scanned sequentially once at most. Furthermore, output of join results is sorted in document order. We also discussed the staircase join algorithm for sibling axes. Studies show that, staircase join for sibling axes is close to the structural join for sibling axes and shares the same characteristic of high efficiency. Our experimental results not only demonstrate the effectiveness of our optimizing techniques for sibling axes, but also validate the efficiency of our algorithms. As far as we know, this is the first work addressing this problem specially.     

对象关系数据库中一个基于连接谓词索引的连接算法

针对对象关系数据库中的连接运算,讨论了一种适合于对象关系数据库的新型索引结构－连接谓词索引,继而给出了基于该索引结构的连接算法,并分析了连接算法的性能,提出了根据性能计算来确定关系Ｒ和Ｓ中谁做为外关系,从而降低算法代价的方法。另外,给出的索引结构,算法思想及性能分析方法,也同样适用于多表连接。     

基于代价模型的不一致XML 数据修复启发式计算

在实际应用中,为不一致的XML 文档计算最优修复意义重大.但求解最优修复是一个NP 完全问题,特别是在XML 文档同时违反函数依赖约束和主键约束时.提出一个基于代价模型的、可以在多项式时间内完成的启发式修复求解算法.该算法首先借助索引表,在一遍扫描原始XML 文档的情况下寻找不一致数据集,然后为每一类约束的不一致数据集构造候选修复,同时计算其修复代价,最后启发式地求解一个代价最小的修复方案.实验结果表明,该算法的时间复杂度不超过冲突类的3 次方,即便是在不一致数据量很大、噪声比例很大以及涉及多类语义约束时,也能较快地完成修复.     

基于代价的XML文档关系模式的生成

1.引言作为目前信息表示和交换的标准,XML得到越来越广泛的应用。对XML进行管理,传统的方法是利用文件系统。目前,传统的关系数据库在市场上仍占有主流地位,如何利用关系数据库来管理XML数据成为现实的问题。由于XML文档本质上是基于图模式的半结构化数据,而目前商用数据库管理系统管理的是基于关系模式的结构化数据,利用关系数据库来管理XML数据可能带来非常高的存贮代价和查询代价,因此利用关系数据库来管理XML数据必须解决两种异构模式之间的转换问题,生成合理的关系模式。对于上述问题,工业界和学术界从不同的角度进行了研究,文Oracle 8i利用关系数据库引擎来完成XML文档的简单查询,但是,Oracle 8i的当前版本要求手工生成XML文档所对应的关系模式,增加了使用人员的负担。     

基于成本的服务链组成与部署联合优化策略

网络功能虚拟化（NFV）通过将虚拟网络功能（VNF）部署在虚拟设备中,提高了网络管理的灵活性,但随着服务需求的扩大,网络供应商消耗的运营支出（OPEX）也不断增加。由于VNF改变流大小的特性、VNF间的依赖性以及组成和部署方式的复杂性,面向OPEX的VNF组成和部署问题充满挑战。提出一种面向成本的虚拟网络链组成和部署联合优化策略,将节点映射成本、链路映射成本、激活成本和能耗成本公式化为OPEX,构建混合整数非线性规划模型。为分析影响成本的不同因素,同时提高特殊依赖情况下的处理效率,根据不同依赖关系将VNF请求集分为完全无序、部分有序和完全有序VNF集合进行分析,并设计3种相应优化算法。实验结果表明,在完全无序、部分有序情况下,算法性能优于首次适应算法、随机拟合算法等同类算法,对于完全有序算法,当节点资源配比在50%以上时,可获得小规模网络下近似线性规划模型精确解的方案。     

基于代价估计的Hive多维索引分割策略选择算法

在能源互联网、智慧城市等新兴领域,智能终端采集的庞大数据往往需要多维分析,传统企业寻求借助互联网技术(如Hadoop和Hive)应对大数据问题.但是Hive当前的多维索引能力较弱,无法满足传统企业的需求.针对这一问题,提出了一种基于分布式网格文件的多维索引技术——DGFIndex,来提升Hive的多维查询处理能力.但是在创建DGFIndex时,需要用户指定各个索引维度的分割粒度,而分割粒度的大小与查询性能息息相关.在用户对数据与查询特征不熟悉时,很难选择较优的分割策略.为了解决这一问题,通过建立新的MapReduce代价模型,并使用两阶段模拟退火算法为DGFIndex搜索较优的分割策略,从而提升查询性能,减少查询集合的总耗时.实验结果表明:DGFIndex可以提升Hive多维查询性能50%~114%,对于固定的查询集合,与人工选定分割策略比较,基于代价估计的分割策略选择算法可以为DGFIndex快速选定较优的分割策略,并可以使整个查询集合的处理时间比人工方法最多减少30%.