一种P2P环境下高效Topk资源搜索技术

随着网格的广泛应用,在网格下查询最符合用户需求的k个资源成为资源搜索研究的重点之一.特别是资源在地域上广泛分布,使得这种Topk搜索的效率成为影响系统性能的关键因素之一.提出了一种P2P环境下的Topk搜索算法,它根据资源属性,将网格资源看做是m维空间中的点,而Topk搜索就转换为在m维空间中搜索距离查询点最近的k个点.该算法根据Agrawal发现的资源密集现象,在m维空间中确定搜索区间大小,并利用P2P领域的多区间搜索算法,迭代地在多个区间中搜索资源,使得算法同时保持高效和低负载的特点.证明了该算法的正确性并分析了它的性能,分析和实验表明,该算法在高维资源属性空间中具有较好的查询效率和较低的网络负载.     

Skyline代表点的选择*

Skyline查询在多维决策和数据挖掘等方面发挥重要作用,然而随着数据属性维度的增大, Skyline集变得非常庞大.为克服该不足,提出Skyline代表点查询.文中提出新的评价函数改进Skyline点的得分计算方法以选择k个具有代表性的Skyline点.在二维空间提出动态规划算法(DPBA),利用覆盖圆的性质确定非代表点与代表点间的覆盖距离,迭代计算评价函数值,从而得到k个代表点;在高维空间针对NP-hard问题提出一个基于aR-tree结构的近似解决方法,遍历索引结构中的节点,通过与候选Skyline集比较判断是否被支配进行剪枝,降低计算开销.大量基于合成数据与真实数据的实验证明该算法的有效性.     

大型钢铁企业原料场存储分配问题的研究

为钢铁企业原料存储分配问题建立了以降低成本并保持原料成分稳定为目标函数的非线性数学模型,并提出了改进禁忌搜索算法进行求解.该算法利用基于随机kick移动的迭代局域搜索策略作为跳出局部最优的策略,其中迭代局域搜索策略的邻域以环交换移动产生.通过150组随机数据的实验证明,引入迭代局域搜索策略的禁忌搜索算法具有较强的全局搜索能力,是解决该类实际工业问题的快速有效的近优算法.     

一种基于迭代局部搜索的和声搜索算法

为了改进原始和声搜索算法的全局搜索性能,提出了基于迭代局部搜索的和声搜索算法.该算法在充分利用和声记忆库中信息和提高搜索效率的同时,对于不满足停止准则的新和声采用基于改进kick策略移动的迭代局部搜索算法进行寻优,从而使新算法具有较强的"爬山"能力.针对4个benchmark函数对新算法做了测试,并与粒子群优化算法以及已有的几个算法进行了比较,结果表明该算法跳出局部极值点的能力较强、收敛速度更快、寻优精度较高;最后将新算法应用到焊接梁的优化设计问题中,仿真结果验证了该算法在求解焊接梁最小造价问题时优于原始的和声搜索算法、遗传算法等方法.     

基于向量夹角的SIFT特征点匹配算法

提出一种基于向量夹角的近似最近邻搜索算法.该算法首先计算高维空间向量与随机选择的参考向量的夹角,并进行排序.计算出待查询向量与参考向量的夹角后,采用二分搜索算法在已排序夹角中查找对应的夹角,并以此夹角为中心,在一定范围内搜索给定向量的近似最近邻.实验结果表明,文中算法可显著提高尺度不变特征变换特征的匹配速度,并能获得满意的匹配效果.     

一种基于角相似性的k-最近邻搜索算法*

k-最近邻搜索(KNNS) 在高维空间中应用非常广泛,但目前很多KNNS算法是基于欧氏距离对数据进行索引和搜索,不适合采用角相似性的应用。提出一种基于角相似性的k-最近邻搜索算法(BA-KNNS)。该算法先提出基于角相似性的数据索引结构(BA-Index),参照一条中心线和一条参照线,将数据以系列壳—超圆锥体方式进行组织并分别线性存储;然后确定查询对象的空间位置,有效确定一个以从原点到查询对象的直线为中心线的超圆锥体并在其中进行搜索。实验结果表明,BA-KNNS算法较其他k-最近邻搜索算法有更好的性能。     

基于测地线距离的广义高斯型Laplacian 特征映射

传统的Laplacian 特征映射是基于欧氏距离的近邻数据点的保持,近邻的高维数据点映射到内在低维空间后仍为近邻点,高维数据点的近邻选取最终将影响全局低维坐标.将测地线距离和广义高斯函数融合到传统的Laplacian 特征映射算法中,首先提出了一种基于测地线距离的广义高斯型Laplacian 特征映射算法(geodesicdistance-based generalized Gaussian LE,简称GGLE),该算法在用不同的广义高斯函数度量高维数据点间的相似度时,获得的全局低维坐标呈现出不同的聚类特性;然后,利用这种特性进一步提出了它的集成判别算法,该集成判别算法的主要优点是:近邻参数K 固定,邻接图和测地线距离矩阵都只构造一次.在木纹数据集上的识别实验结果表明,这是一种有效的基于流形的集成判别算法.     

基于混合负载平衡的并行启发式搜索算法

在分析了迭代加深启发式搜索(Iterative Deepening A*)算法及其可并行性后,提出了一种新的基于混合负载平衡的并行迭代加深启发式搜索算法。该算法综合了静态负载平衡和动态负载平衡的优点,可以在多结点的并行搜索计算中获得很高的加速比和效率。给出了该算法的Java RMI实现。通过在72个结点的并行机上的试验表明,该算法可以极大地提高并行搜索算法的加速度和效率。     

基于自适应搜索模板的快速运动估计算法

为了降低快速运动估计的计算复杂度,避免小菱形搜索算法带来的局部最优点问题,提出了自适应搜索模板的估计算法.该算法在搜索时根据SAD值的变化快慢和相邻帧之间时间相关性自适应选择搜索模板.实验表明,使用该算法编码,码流大小与使用菱形搜索算法和六边形搜索算法差距为±0.6%,搜索点数为菱形算法的72%～77%,六边形算法的83%～86%.在减少搜索点数的情况下有效地避免了局部最优点问题.     

关系数据库中支持语义的Top-K关键字搜索

为了增强关系数据库中的关键字搜索查询结果,考虑了多表之间以及元组之间的语义关系,提出了一种语义评分函数.该语义评分函数不仅涵盖了当前的评分思想,并且加入新指标来衡量查询结果与查询关键字之间的相关性.基于该评分函数,提出两种以数据块为处理单位的Top-K搜索算法,分别为BA(blocking algorithm)算法和EBA(early-stopping blocking algorithm)算法.EBA在BA基础上引入了过滤域值,以便尽早终止算法的迭代次数.最后实验结果显示语义评分函数保证了搜索结果的高查准率和查全率,所提出的BA算法和EBA算法改善了现有方法的查询性能.     

孤岛危机要点

研发工作室Crytek展开了一个有效的中间设备方案并紧密的关注细节，创造出了PC游戏中从未出现过的最真实的环境之一。     

Non-partitionable point sets

Let S be a finite set of n points in d-dimensional space. S is α(n)-partitionable if there exists a set of d mutually intersecting hyperplanes that divide d-space into 2^d open regions, no 2^d ? 1 of which together contain more than α(n) points of S. Willard (1982) has shown that every set in 2-space is $\text{3}\text{4}$n-partitionable. Yao (1983) has shown that every set in 3-space is $\text{23}\text{24}$n-partitionable. It is shown here that there exist sets S of arbitrary cardinality in d-space, d ? 5, for which d² + 1 open regions together contain at least n ? d² points of S, in any partition by d intersecting hyperplanes. Further, at least 2^d ? d² ? 1 open regions contain no points of S. This implies that the powerful balanced quad and oct-trees introduced by the above authors may not be generalized to balanced 2^d-trees in dimension at least 5.     

基于点对特征的三维点云匹配算法

针对现有的基于全局特征的三维物体识别方法和基于局部特征的三维物体识别方法在有遮挡和混叠场景中识别效果均不理想的问题,提出了一种基于点对特征的三维点云匹配算法。利用模型上的所有点对特征来完成全局模型描述构建,并在减少的二维空间上,利用快速投票方案,在局部对模型点云和场景点云进行匹配,从而恢复模型在场景中的全局姿态。实验结果表明:该算法在有遮挡和混叠的场景中识别效果比较理想。     

多供应点、多需求点应急物资调运模型及算法

研究了多供应点、多需求点应急物资调运问题的优化目标、决策模型及求解算法。首先,从需求点的角度考虑应急物资的需求紧迫程度、运达时间和需求满足情况,提出了应急保障综合评价函数。在此基础上,兼顾不同供需情况以及应急物资和运输工具种类的多样性,构建了以应急保障综合评价函数值最小为目标的决策模型。最后,针对模型特点提出了嵌入解构造算法的改进粒子群优化算法(IPSOA-ESCA)。仿真实验验证了应急保障综合评价函数的合理性、模型的普适性和算法的有效性。     

基于多判据的散乱点云特征点提取算法

为了有效获取散乱点云中的尖锐特征点和边界特征点,提出一种利用多判据融合的特征点提取算法。首先利用一种改进的k-d tree构建点云拓扑,搜索样点的K局部邻域;然后利用法向夹角判定准则、核密度判定准则、场力和判定准则分别求取各个样点局部邻域的三个特征参数,最后通过加权计算特征参数得到每个样点的特征值与全局判定阈值,特征值比阈值大的点即为特征点。实验证明,该算法能有效的获取散乱点云中边沿特征点与尖锐特征点。     

结合间接邻域的散乱点云三角网格曲面重构

对于非均匀散乱点云,多数基于区域生长方法的曲面重构往往容易出现孔洞等缺陷。针对该问题,在K邻域点集的基础上提出间接邻域点集的概念,对以点为生长对象进行区域生长的三角网格曲面重构方法进行了研究,实现三角网格曲面重构。以生长点的邻域点集为样点估算微切平面,将邻域点投影至该平面上,并按照右手定则、逆时针方向进行排序,通过拓扑正确性原则从点列中去除错误的连接点,优化局部网格,选择较好的连接点,实现网格曲面的区域生长。     

一种改进的散乱点云边界特征点提取算法

提出一种新的散乱点云边界特征点提取算法。根据点云数据小邻域内点用最小二乘法拟合建立微切平面,并将这些数据点向其微切平面投影,利用点集中每个点的场力大小之和可以体现点集平均作用的理论来分析投影面上点集的几何分布特性,据此检测边界特征点。利用双向最近点搜索算法对提取出来的特征点进行排序并自动生成边界曲线。实验结果证明该算法能够快速、准确、有效地提取点云的边界。     

基于特殊角点和基点定位在线掌纹的方法

本文简述了目前在线掌纹定位的主要方法,提出一种通过寻找特殊角点和基点实现在线掌纹的定位。该方法基于掌纹的形状特点,先定位特殊角点,再通过统计块点方向和求梯度确定感兴趣的纹线上的一点,最后用灰度值跟踪方法确定特殊基点。该定位方法减少了手掌张开强度因素造成的影响,并取得了理想的实验结果。     

Harmonic point cloud orientation

In this work we propose a new method for estimating the normal orientation of unorganized point clouds. Consistent assignment of normal orientation is a challenging task in the presence of sharp features, nearby surface sheets, noise, undersampling, and missing data. Existing approaches, which consider local geometric properties often fail when operating on such point clouds as local neighborhood measures inherently face issues of robustness. Our approach circumvents these issues by orienting normals based on globally smooth functions defined on point clouds with measures that depend only on single points. More specifically, we consider harmonic functions, or functions which lie in the kernel of the point cloud Laplace-Beltrami operator. Each harmonic function in the set is used to define a gradient field over the point cloud. The problem of normal orientation is then cast as an assignment of cross-product ordering between gradient fields. Global smoothness ensures a highly consistent orientation, rendering our method extremely robust in the presence of imperfect point clouds.