Nearest Neighbor Queries in Shared-Nothing Environments

In this paper, we propose an efficient solution to the problem of nearest neighbor query processing in declustered spatial databases. Recently a branch-and-bound nearest neighbor finding (BB-NNF) algorithm has been designed to process nearest neighbor queries in R-trees. However, this algorithm is strictly serial (branch-and-bound oriented) and its performance degrades, during processing of a nearest neighbor query, if applied to a parallel environment, since it does not exploit any kind of parallelization. We develop an efficient query processing strategy for parallel nearest neighbor finding (P-NNF), assuming a shared nothing multi-processor architecture, where the processors communicate via a network. In our method, the relevant sites are activated simultaneously. In order to achieve this goal, statistical information is used. The efficiency measure is the response time of a given query. Experimental results, based on real-life and synthetic datasets, show that the proposed method outperforms the branch-and-bound method by factors.     

基于八叉树邻域分析的光线跟踪加速算法

八叉树是加速光线跟踪常用的层次划分结构,为加快八叉树跟踪光线的过程,论文 研究了运用八叉树邻域分析提高光线与八叉树节点之间的碰撞检测速度的方法,提出了一种结构 简单、计算效率更高的八叉树节点的邻域分析算法。运用该算法可由现碰撞节点快速计算出下一 碰撞节点,避免了采用大量递归搜索计算,从而提高了图像的渲染速度。实验结果表明,使用论 文提出的邻域分析进行碰撞检测,效率比传统算法提高了3 倍以上,大大提高了光线跟踪的速度。     

Implementing gate operations between uncoupled qubits in linear nearest neighbor arrays using a learning algorithm

We propose a new scheme to implement gate operations in a one dimensional linear nearest neighbor array, by using dynamic learning algorithm. This is accomplished by training quantum system using a back propagation technique, to find the system parameters that implement gate operations directly. The key feature of our scheme is that, we can reduce the computational overhead of a quantum circuit by finding the parameters to implement the desired gate operation directly, without decomposing them into a sequence of elementary gate operations. We show how the training algorithm can be used as a tool for finding the parameters for implementing controlled-NOT (CNOT) and Toffoli gates between next-to-nearest neighbor qubits in an Ising-coupled linear nearest neighbor system. We then show how the scheme can be used to find parameters for realizing swap gates first, between two adjacent qubits and then, between two next-to-nearest-neighbor qubits, in each case without decomposing it into 3 CNOT gates. Finally, we show how the scheme can be extended to systems with non-diagonal interactions. To demonstrate, we train a quantum system with Heisenberg interactions to find the parameters to realize a swap operation.     

使用R树进行k-NN搜索

在地理信息系统中经常要做k-NN搜索，进行这些查询用到的算法与位置和范围查询的算法不同，需要专门进行研究，介绍了一种分支界限遍历R树算法，并将该算法概括为k-NN算法。文中讨论了两种方法。对R树进行结点内MBR的排序以及剪枝过程，以减少搜索空间中需访问结点的数量，有效地进行k-NN搜索。     

基于八叉树邻域分析光线跟踪的云三维模拟

针对目前三维云模拟绘制效率低、计算资源消耗大、绘制效果差等问题,提出基于八叉树邻域分析的光线跟踪算法,并用于WRF模式云数据的三维模拟。使用八叉树结构优化传统光线跟踪算法的数据存储结构,通过存储节点编码和划分层次改进邻域分析算法,通过简化光线的折射公式优化Whitted光照模型,借助OpenGL和Vapor工具实现云数据的三维可视化。实验结果表明,该方法降低了绘制时间,提高了渲染效率,更好体现了云的真实物理特征。     

一种基于邻居信任评估的虫洞防御机制

移动adhoc网是一种新型无线移动网络,具有无中心、自组织、拓扑结构变化频繁以及开放式通讯信道等特性,因此adhoc网络下的路由协议所面临的安全问题比有线网环境中更为严重。虫洞攻击就是其中的一种,能够对adhoc网络产生致命的影响。在这种攻击下,网络的路由机制将会紊乱,特别是那些依赖通过接收对方的广播报文进行邻居探测的路由协议。本文首先从虫洞形成的根源上入手,重新定义了邻居的概念,强调了邻居作为节点信息转发第一站的功能。然后根据邻居定义,引入简化的Marsh信任模型,将邻居的以往表现作为信任评估的经验来源,再通过具体公式对邻居关系做出判定。在具体的路由过程中,节点根据信任评估值选取高可信度的邻居作为下一跳的转发节点,从而避免虫洞攻击的危害。为了验证方法的可行性,本文将模型应用于OLSR路由协议中并在NS2中进行了仿真。     

图像中多语种文本提取的高斯混合建模方法

建立了相邻字符区域的高斯混合模型,用于区分字符与非字符.在此基础上,提出了一种从图像中提取多语种文本的方法.首先对输入图像进行二值化,并执行形态学闭运算,使二值图像中每个字符成为一个单独的连通成分.然后根据各连通成分重心的Voronoi区域,形成连通成分之间的邻接关系;最后在贝叶斯框架下,基于相邻字符区域的高斯混合模型计算相应的伪概率,以此为判据将每个连通成分标注为字符或非字符.利用所提出的文本提取方法,进行了复杂中英文文本的提取实验,获得大于97%的准确率和大于80%的召回率,证实了方法的有效性.     

随机约束满足问题的回溯算法分析

提出一种新的随机CSP(constraint sa tisfaction problem)模型,并且通过研究搜索树的平均节点数,分析了回溯算法求解该模型 的平均复杂性.结果表明,这种模型能够生成难解的CSP实例,找到所有的解或证明无解所需的 平均节点数即随变量数的增加而指数增长.因此,该模型可以用来研究难解实例的性质和CSP 算法的性能等问题,从而有助于设计出更为高效的算法.     

基于改进蚁群算法的船舶电力系统故障重构研究

提出一种采用K阶近邻策略求解子集类问题的改进蚁群算法,应用到船舶电力系统故障重构问题中。将重构问题抽象为子集类优化选择问题．建立适合解决此类问题的蚁群算法模型。根据船舶电力系统故障重构特点,采用K阶近邻策略缩小算法的求解空间以提高寻优求解效率。算例分析及仿真实例表明,改进后的蚁群算法可以有效解决船舶电力系统故障重构问题。     

基于AR模型思想的高斯过程多模型建模方法

针对K-近邻算法中难以确定K值的定量问题,提出一种基于AR模型思想的高斯过程多模型建模方法。该方法借鉴AR模型的思想,将前一时刻的输出值作为当前时刻输出值的一个影响因素放入输入集中,通过计算训练样本的平均最小距离从而得到一个搜索半径,根据搜索半径来确定K值和K个近邻样本的权重,采用加权输出的方式以得到组合模型的输出。将其建模方法应用到某双酚A反应釜出口苯酚含量的软测量建模中,仿真结果表明,该方法具有较高的精度和较好的模型推广能力。     

一种具有动态邻域特点的自适应最近邻居算法

传统的最近邻居算法主要分为k-最近邻居和逆最近邻居,然而二者均在邻域参数选择问题中饱受困扰。在这两种思想的基础上,提出 一种具有动态邻域特点的最近邻居算法——自然邻居,并围绕其概念与特性形成了一套有效的方法。该算法从根本上克服了传统最近邻居思想在任意形状(如流型)数据集中参数选择的难题,摆脱了传统方法的参数依赖,并且取得了极佳的效果。自然邻居思想具有完善的理论模型和详细的实现算法,并且经验证其具有很强的鲁棒性和适应性。     

面向非均匀采样点集的3维表面重建算法

针对非均匀采样点集,提出一种改进的3维表面重建方法。该方法将整个点集进行空间划分,缩小近邻点的搜索范围,减少搜索时间;在确定近邻点时,先计算几何近邻点,然后通过求方向性点并构造最小生成树的方法,确定拓扑近邻点;最后通过将拓扑近邻点投影到局部切平面上,利用约束条件对投影点进行三角剖分,并将剖分得到的顶点连接关系映射到3维空间中,实现3维表面重建。实验结果表明,改进后的算法运行效率高、重建效果好、广泛适用于非均匀采样点集的表面重建。     

基于粒子群和二维Otsu方法的快速图像分割

二维Otsu方法同时考虑了图像的灰度信息和像素间的空间邻域信息,是一种有效的图像分割方法.针对二维Otsu方法计算量大的特点,采用粒子群算法来搜索最优二维阈值向量.每个粒子代表一个可行的二维阈值向量,通过粒子群之间的协作来获得最优阈值.结果表明,所提出的方法不仅能得到理想的分割结果,而且计算量大大减少,达到了快速分割的目的,便于二维Otsu方法的实时应用.     

多跳吞吐量分析及邻节点实时估计算法设计

针对媒体接入控制（MAC）协议吞吐量理论分析中单跳性、静态性不足,提出一种面向移动自组网（MANET）的多跳分析模型,并设计了邻节点实时估计算法。首先,基于二维离散时间马尔可夫链（DTMC）吞吐量模型,定义距离参数欧实比（ERR）,建立泊松网络（PN）分布时多跳吞吐量分析模型;其次,定性分析理论与仿真误差的原因之一在于邻节点的动态性,即模型缺乏移动性考虑;然后,基于卡尔曼滤波算法,定义系统状态更新规则和测量规则,设计一种与泊松节点分布、随机行走模型相适应的邻节点实时估计算法;最后,对比分析多跳吞吐量分析模型的性能。实验结果表明,虽引入0.13 s计算时延,但在吞吐量方面,其精度提高了8%,实现了理论分析模型的多跳扩展和移动性考量。     

基于SURF和快速近似最近邻搜索的图像匹配算法

针对高维特征向量存在的最近邻匹配正确率低的问题, 提出了一种基于SURF和快速近似最近邻搜索的图像匹配算法。首先用Fast-Hessian 检测子进行特征点检测, 并生成SURF特征描述向量; 然后通过快速近似最近邻搜索算法得到初匹配点对, 再对得出的单向匹配结果进行双向匹配; 最后采用鲁棒性较好的PROSAC算法进一步剔除误匹配点对。实验证明了该算法不仅提高了SURF算法匹配的正确率, 还保证了算法的实时性。     

Solving an urban waste collection problem using ants heuristics

This paper describes the methodology that we have applied for the solution of an urban waste collection problem in the municipality of Sant Boi de Llobregat, within the metropolitan area of Barcelona (Spain). The basic nature of the considered problem is that of a capacitated arc routing problem, although it has several specific characteristics, mainly derived from traffic regulations. We present the model that we have built for the problem, which results after an appropriate transformation of the problem into a node routing one. We also present the ant colonies heuristics that we have used to obtain the solutions to the problem. These combine constructive methods, based on nearest neighbor and on nearest insertion, with a local search that explores various neighborhoods. The application of the proposed methods gives results that improve considerably the ones that were previously used in the municipality.     

知识引导的多目标多智能体进化算法

将智能体模型与知识模型相结合,提出一种知识引导的多目标多智能体进化算法.算法定义了智能体的不同邻域环境,并通过对邻域之间的竞争、正交交叉、知识学习等操作实现种群的演化过程.算法采用一种新颖的方法求非劣解集,并使用循环拥挤排序法对外部归档集进行维护.通过对多个测试函数的仿真结果表明,知识的引入不仅增加了种群多样性,而且提高了算法的收敛性.     

采用新邻居模型的多目标分解进化算法

在通常的基于分解的多目标进化算法中,繁殖计算时使用的解从基于子问题定义的邻居集合中选择,当目标函数存在多峰等复杂特征时,它们在决策空间的距离可能较远,这会导致算法性能变差。为了解决这一问题,提出了一种采用新邻居模型的多目标分解进化算法MOEA/D-NN。该算法重新设计了繁殖计算中使用的邻居模型,利用解在决策空间上的距离计算邻居,进而为每个子问题维护相应的邻居集合,在此基础上对邻居集合进行定时更新,实现了基于新邻居模型的繁殖计算。通过在公开测试集上的实验结果表明,提出的算法与几种经典的多目标进化算法相比,在大多数测试集上表现更优。     

融合动态社交关系的距离度量推荐算法

目前,用户的好友关系及其自身呈现的动态变化趋势,使得基于静态社交关系的推荐算法难以满足现今瞬息万变的世界。为解决准确度较低等问题,提出利用用户购买物品的时序行为挖掘隐式社交关系的方法。首先将隐式社交与相似度算法相融合,其次针对近邻评分的稀疏性,提出改进的近邻评分填补方法,然后使用填补后的近邻评分对模型预测评分进行修正,最后生成预测评分。实验部分采用MovieLens数据集评估提出的方法,并与现存算法作对比分析。结果表明,该算法与传统算法及改进算法相比更稳定,也更有效地预测了目标用户的真实评分。     

基于类邻域字典的线性回归文本分类

文本表示的高维性会增加文本分类时的计算复杂度。针对该问题,构建基于类邻域字典的线性回归分类模型。采用K近邻方法构造各类别的类邻域字典,根据对测试样本的不同表示,分别提出基于级联类邻域字典和基于类邻域字典的线性回归分类算法。此外,为缓解噪声数据对分类性能的影响,通过度量测试样本与各个类别之间的相关度裁剪噪声类数据。实验结果表明,该模型对长文本和短文本均能够得到较高的分类精度和计算效率,同时,噪声类裁剪策略使其对包含较多类别数的文本语料也具有较好的分类性能。