基于k-d树的k-means聚类方法

在直接k-means算法的基础上提出了一种新的基于k-d树的聚类方法。通过把所有的对象组织在一棵k-d树中，可以高效地发现给定原型的所有最近邻对象。利用的主要思想是：在根结点，所有的聚类中心(或称为候选原型)都是所有对象的最近邻候选集合，对于根结点的子结点，通过简单几何约束来剪枝该候选集，这种方法可以被递归使用。使用基于k-d树的方法可以使直接k-means算法的总体性能提高一到两个数量级。     

基于句法的统计机器翻译模型与方法

该文总结了我们近几年来在基于句法的统计机器翻译方面所做的研究工作,特别是基于源语言句法的一系列统计机器翻译模型与方法,具体包括 基于最大熵括号转录语法的翻译模型,基于源语言短语结构树的树到串翻译模型及其相应的基于树的翻译方法,基于森林的翻译方法和句法分析与解码一体化翻译方法,基于源语言依存树的翻译模型。     

一个适用于内存数据库系统的多维索引结构

树形结构一直都是数据库系统中建立多维索引最有效的方法之一,其中比较流行的有k-d树,R树等。但是对于内存空间极为宝贵的内存数据库来说,它们都有浪费内存的缺点。而T树作为内存数据库最常使用的一维索引结构,具有存取速度快,节约空间的优点,但是对于多维索引的情况它的效率却不高。该文首先介绍了k-d树,R树的特点及缺点,然后介绍T树的特点,操作和在多维条件下的缺陷,并提出了一种网格+T树的结构对其进行改进,从而使它适用于多维索引的情况。     

基于结构比对的软件同源综合检测工具的设计与实现

文章对基于文本、Token和抽象语法树的同源性检测技术进行探讨,详细介绍了关于抽象语法树的同源性检测技术。同时,在对实际应用大量研究的基础上,文章着重介绍了源代码同源性检测系统的架构设计,以及引擎比对、比对结果分析和比对结果输出等主要功能模块,并对开发的系统进行了系统测试和分析,验证了算法的可行性。     

基三分层网络中的受限多播路由算法

多播路由算法对互连网络的通信性能和多处理机系统性能的发挥起着重要作用。针对基三分层互连网络，在权衡性能、成本和实现的基础上，提出一种基于树的受限多播路由算法TRMA。该算法充分利用基三分层互连网络的层次特性和节点编码中所含的网络拓扑信息实现消息路由，算法设计简单，易于硬件实现。和其他基于树的多播路由算法相比，TRMA算法不需要源节点在发送消息前构建多播树,并将多播树的信息存放在消息中，大大降低了源节点的工作负载，提高整个系统的性能。通过仿真比较了TRMA和基于单播的多播路由算法，结果表明TRMA具有较低的网络延迟和较小的网络流量。     

快速聚类算法在个性化服务中的应用

许多实际应用已经证明,k-means算法能够有效地得到好的聚类结果。但是,k-means直接算法的时间复杂度和模式复杂度对数据量的大小非常敏感,无法满足一些高性能的应用场合,如个性化服务中对用户数据进行的群组分析。对此,笔者提出了一种新颖的基于k-d树的聚类算法。这种算法采用空间数据结构—k-d树组织所有的样本数据,可以高效地搜索到离某个给定的聚类中心最近的全部模式。实验结果表明,该方案可以显著提高k-means直接算法的运算速度,在距离运算量和总的运算时间上,可把性能提高1～2个数量级。     

基于树的分析技术在软件测试中的应用

本文以如何使用基于树的建模技术标识软件中有问题的区域和进行危险管理为例，着重阐述了基于树的分析技术在软件测试中的应用。     

基于依存树距离识别论元的语义角色标注系统

在基于依存的语义角色标注研究中,大多数系统采用机器学习方法进行论元识别和分类。该文分析了依存树的特点,发现论元集中分布于依存树上的特定局部范围内,因此提出一种基于依存树距离的论元识别方法。该方法将候选论元限制在与目标动词的依存树距离不超过3 的范围内,通过制订规则,提取目标动词的最佳候选论元集合。在CoNLL2009中文语料上采用正确的依存树,识别出了98.5%的论元。在此基础上,结合基于机器学习的角色分类,系统F值达到89.46%,比前人的方法 (81.68%)有了较为显著的提升。     

基于粗集的CBR故障诊断案例的检索方法研究

针对基于案例推理的飞机机载设备故障诊断中知识的表示及检索做了研究,对于目前存在的故障案例在知识的表示和案例的检索中遇到的案例表示多样化,案例检索效率低下等问题,提出了类似于故障树的案例检索树,参考k-d的建树方法,利用粗集理论计算案例各个属性重要性,按属性重要性进行检索,这种方法运用在飞机机载设备故障诊断中,可以显著提高案例检索的效率,几乎是传统方法的一半,同时提高了检索结果的精度,减少了匹配的案例个数.     

基于形状特征k-d树的多维时间序列相似搜索

多维时间序列是信息系统中一类重要的数据对象,相似搜索是其应用的一个核心.两个序列(子序列)相似度加以比较的常用方法是:将序列(子序列)转换成空间中的曲线,然后计算曲线间的欧几里德距离.这种方法的主要缺陷是它仅考虑了序列(子序列)间的整体距离关系,而不能体现它们自身的局部变化.针对此问题,提出了一种新的可应用于多维时间序列的快速相似搜索方法.该方法将序列(子序列)的局部变化特性与检索结构(k-d树)结合起来,使得在搜索k-d树的同时实现了序列(子序列)的局部变化匹配,从而极大地提高了查询效率和正确率.实验结果表明了算法的有效性.     

Parallel construction of multidimensional binary search trees

Multidimensional binary search tree (abbreviated k-d tree) is a popular data structure for the organization and manipulation of spatial data. The data structure is useful in several applications including graph partitioning, hierarchical applications such as molecular dynamics and n-body simulations, and databases. In this paper, we study efficient parallel construction of k-d trees on coarse-grained distributed memory parallel computers. We consider several algorithms for parallel k-d tree construction and analyze them theoretically and experimentally, with a view towards identifying the algorithms that are practically efficient. We have carried out detailed implementations of all the algorithms discussed on the CM-5 and report on experimental results     

Performance analysis of partial-match search algorithms for BD trees

Database systems are becoming increasingly popular for answering queries. Partial-match search queries are an important class of queries in such a system. Several storage structures have been proposed to answer these queries efficiently. The BD tree is an example of such a storage structure. A previous study indicated that the k-d tree performance is better than that of the BD tree for partial-match search queries. A recent paper reported some improved algorithms. However, it is unclear whether the improved algorithms show the BD tree in a favourable light for partial-match search queries. This paper explores the performance of these algorithms and compares their performance to that of the k-d tree. Since the BD tree construction process uses some heuristics to make it a better balanced tree, this paper also evaluates the effect of these heuristics on the partial-match search algorithms. The major conclusions of this study are that the BD tree performance for partial-match search is better than that of the k-d tree when an improved algorithm is used for partial-match search, and only the DZ expression rearrangement heuristic has substantial effect on partial-match search performance.     

两种基于对象的嵌入式小波图像编码算法比较分析

为进一步研究现有基于对象的图像压缩技术,介绍两种基于对象的嵌入式小波图像编码算法——基于对象的集合分裂嵌入块（0bject-Based Set Partitioned Embedded bloCK,OB—SPECK）编码算法和基于k—d树的二元集合分裂（Binary Set Splitting with k—d trees,BISK）编码算法,并进行比较分析、结果表明两种算法在集合分裂方案、对透明因数的处理方法及算法复杂度上有不同之处．在Matlab中进行的仿真实验表明,在对任意形状对象进行编码时,BISK编码算法在算法性能和图像压缩质量上较OB—SPECK编码算法更优．     

用K-D树实现对双模态多媒体数据库的有效查询

论文提出了一种用k-d树来查询双模态视觉听觉语音识别数据库的方法。这种方法揉合了查询地理信息系统的多维数据库和空间数据库的方法,结合双模态视觉听觉语音数据库自身的特点提出了在数据库中插入、查询和删除记录的算法。最后还对把查询多维数据的方法应用在双模态语音识别数据库领域进行了展望。     

Fast training algorithms for multilayer neural nets

An algorithm that is faster than back-propagation and for which it is not necessary to specify the number of hidden units in advance is described. The relationship with other fast pattern-recognition algorithms, such as algorithms based on k-d trees, is discussed. The algorithm has been implemented and tested on artificial problems, such as the parity problem, and on real problems arising in speech recognition. Experimental results, including training times and recognition accuracy, are given. Generally, the algorithm achieves accuracy as good as or better than nets trained using back-propagation. Accuracy is comparable to that for the nearest-neighbor algorithm, which is slower and requires more storage space.     

Multidimensional Binary Search Trees in Database Applications

The multidimensional binary search tree (abbreviated k-d tree) is a data structure for storing multikey records. This structure has been used to solve a number of "geometric" problems in statistics and data analysis. The purposes of this paper are to cast k-d trees in a database framework, to collect the results on k-d trees that have appeared since the structure was introduced, and to show how the basic data structure can be modified to facilitate implementation in large (and very large) databases.     

一种基于数据聚类的鲁棒SIFT特征匹配方法

针对噪声敏感造成的SIFT特征匹配鲁棒性低问题,提出一种基于数据聚类的两阶段特征匹配方法.在满足特征匹配几何距离最邻近本质要求下扩展了k d数据结构,使其不但能够完成算术平均化匹配特征离线聚类,而且能够实现第1阶段聚类特征在线匹配.在此基础上,给出一种概率最优投票策略选择关键图像进行第2阶段匹配,最后合并两阶段属于关键图像的所有匹配特征对.实验结果表明,对于大量存在重叠关系的图像集合,该方法能够有效减少重复特征数量,降低噪声信息对特征匹配的干扰,极大地提高特征匹配的鲁棒性.     

基于多判别参数混合方法的散乱点云特征提取

针对以往散乱点云特征提取算法存在尖锐特征点提取不完整以及无法保留模型边界点的问题,提出了一种多个判别参数混合方法的特征提取算法。首先,对点云构建k-d tree,利用k-d tree建立点云k邻域;然后,针对每个k邻域计算数据点曲率、点法向与邻域点法向夹角的平均值、点到邻域重心的距离、点到邻域点的平均距离;最后,据此四个参数定义特征阈值和特征判别参数,特征判别参数大于阈值的点即为特征点。实验结果表明,与已有算法相比,该算法不仅可以有效提取尖锐特征点,而且能够识别边界点。     

Analysis of range search for random k-d trees

We analyze the expected time complexity of range searching with k-d trees in all dimensions when the data points are uniformly distributed in the unit hypercube. The partial match results of Flajolet and Puech are reproved using elementary probabilistic methods. In addition, we give asymptotic expected time analysis for orthogonal and convex range search, as well as nearest neighbor search. We disprove a conjecture by Bentley that nearest neighbor search for a given random point in the k-d tree can be done in O(1) expected time. Received: 27 July 1999 / 2 June 2000