基于内容图像检索中的一种动态多维索引方法

多维索引技术是基于内容检索的图像数据库的关键技术。SR-tree和X-tree是目前比较成熟有效的多维索引技术。为了提高多维索引的性能,我们在分析SR-tree和X-tree的结构和性能的基础上,针对SR-tree分裂算法的不足,引入X-tree中超级节点的思想,通过改进插入和分裂算法,设计了一种新的多维索引结构ESR-tree,即ExtendedSR-tree。实验表明,随着数据量和维数的增多,ESR-tree的性能明显优于SR-tree和X-tree。     

基于Hadoop的并行共享决策树挖掘算法研究

共享知识挖掘是指通过学习不同事物之间的共享知识,将学习到的知识应用到未知事物来加快认知未知事物。针对大数据集中串行共享知识挖掘算法效率低下的问题,结合云计算技术,提出了一种基于Hadoop的并行共享决策树挖掘算法(PSDT)。该算法采用传统的属性表结构实现并行挖掘,但 其I/O操作过多,影响算法性能,为此,进一步提出了一种混合并行共享决策树挖掘算法(HPSDT)。该算法采用混合数据结构,在计算分裂指标阶段使用属性表结构,在分裂阶段采用数据记录结构。数据分析表明,HPSDT算法简化了分裂过程,其I/O操作是PSDT的0.34左右。实验结果表明,PSDT和HPSDT都具有良好的并行性和扩展性;HPSDT比PSDT性能更好,并且随着数据集的增大,HPSDT的优越性更加明显。     

基于均值漂移和双层群结构模型的群目标GMPHD滤波

针对不可分辨群目标跟踪算法中群合并、交叉及分裂前后群目标数出现漏估及量测划分数多、计算量大两个问题,提出一种基于均值漂移(MS)和双层群结构(BGS)模型的群目标高斯混合概率假设密度(GMPHD)滤波算法.该算法采用MS进行量测划分,同时依据第2层群结构反馈回的群信息判断是否需要进行2次划分;然后,采用基于椭圆随机超曲面模型(RHM)的群目标GMPHD滤波进行预测更新和状态提取;最后,使用提取出的群目标状态进行第二层群结构更新,并将所得群信息反馈回量测划分步.仿真对比实验表明,所提出算法可获得更高的实时性,能够解决群目标合并、交叉及分裂前后群数目的漏估问题.     

关于无穷计算问题的水平分裂算法分析及改进

首先介绍了用于路由选择的DVR(距离矢量路由)算法及其存在的无穷计算问题。然后阐述了用于解决该问题的水平分裂算法的思想,并运用MST(最小生成树)分析法对其进行了基于树型、环型和网状3种网络拓扑结构的算法分析。最后提出了一种改进的水平分裂算法———下一跳算法,并在实例分析的基础上对其存在的问题进行了总结。     

超光谱图像的三维小波嵌入零块压缩编码

超光谱图像作为一种三维图像,其海量的数据导致在有限带宽信道上传输和存储非常困难,必须对它进行有效的压缩编码.提出了一种基于非对称三维小波变换(3D wavelet transform,简称3DWT)和三维集合块分裂的超光谱遥感图像压缩方法.因为大多数超光谱图像在各个方向上具有非对称的统计特性,所以利用非对称三维小波变换去除图像的谱间和空间冗余.与传统的对称三维小波变换相比,非对称的三维小波变换能够更有效地去除相邻谱段间的冗余.提出了一种改进的3DSPECK(3D set partitioning embedded block)算法--非对称三维集合分裂块算法(asymmetric transform 3DSPECK,简称AT-3DSPECK),并被用于编码变换后的系数.根据变换系数的能量分布特点,三维零块分裂和三维octave子带分裂方法被有效地结合在所提出的AT-3DSPECK算法中.为了优化率失真和加速编码速度,也给出了一种零块优化排序的快速算法.实验测试表明:AT-3DSPECK算法的平均PSNR(peak signal to noise ratio)分别比AT-3DSPIHT(asymmetric transform 3D set partitioning in hierarchical trees)和3DSPECK算法高0.4dB和1.4dB.此外,AT-3DSPECK还具有比零树算法更快的编码速度.     

基于分割聚类技术的R树结点分裂方案

在分析了R树结点分裂方案存在不足的基础上,将分割聚类技术应用到R树结点分裂中,提出基于分割聚类技术的R树结点线性分裂算法(C-Linear),并对C-Linear分裂算法进行了理论分析和实验验证,结果表明该算法具有良好的性能,能有效地提高R树的操作效率.     

基于TPE的SpaRC算法超参数优化方法

宏基因组序列组装在计算和内存上面临着巨大挑战。SpaRC(Spark Reads Clustering)是基于Apache Spark的宏基因组序列片段聚类算法,为来自下一代测序技术的数十亿测序片段聚类提供了一种可扩展的解决方案。但是,SpaRC算法参数的设置是一项非常具有挑战性的工作。SpaRC算法拥有许多对算法性能有着很大影响的超参数,选择合适的超参数集对于充分发挥SpaRC算法的性能来说是至关重要的。为了提高SpaRC算法的性能,探索了一种基于树状结构Parzen估计方法(Tree Parzen Estimator,TPE)的超参数优化方法,其能够利用先验知识高效地调节参数,并通过减少计算任务加速寻找最优参数,达到最佳聚类效果,从而避免昂贵的参数探索。对长序列片段(PacBio)和短序列片段(CAMI2)进行实验,结果表明,该方法在改善SpaRC算法性能方面有着良好的效果。     

一种基于SLP的新型编译框架

对于SLP算法不能高效处理并行代码占有率较小的大型应用程序的问题,本文提出并评估了一种新型的基于改进的SLP(Superword level parallel)算法的编译框架。它主要包括三个阶段,首先,将代码中的结构相似的异构语句通过改进的SLP算法尽可能的改为同构语句;然后,用全局的观点,在优化目标代码之前获取其数据模型重用;最后,联合数据布局优化进行进一步的性能提升。本文就此框架做了大量实验,实验结果表明本框架比SLP算法性能更佳,优于它约15.3%。     

基于全局性分裂算子的进化K-means算法

进化算法可以有效地克服K means对初始聚类中心敏感的缺陷,提高了聚类性能。在进化K means聚类算法 (F-EAC)的基础上,针对其变异操作——簇分裂算子的随机性与局部性,提出了两个全局性分裂算子。结合最大最小距离的思想,利用待分裂簇的周边簇信息来指导簇分裂初始点的选择,使簇的分裂更有利于全局划分,以进一步提高进化聚类的有效性。实验结果表明,基于全局性分裂算子的算法在类数发现及聚类精度方面均优于F EAC。     

支持k近邻查询的X*树索引结构

通过分析已有的索引结构在进行k近邻查询时效率上的不足,提出了适合进行k近邻查询的X*树索引结构,采用了新的结点分裂算法,同时不需要额外存储结点分裂的历史信息。实验结果表明它比X树的时间和空间性能更好,更适合k近邻查询的应用。     

基于结点分裂优化的R-树索引结构

针对R-树索引空间查询效率低下的问题,提出一种基于结点分裂优化的R-树索引结构：SR-树索引。SR-树索引在结点分裂过程中,通过增加叶子结点的空间数据聚集性来减少叶子结点最小外接矩形的覆盖面积。为了有效降低磁盘读写消耗,SR-树结点在写入索引时,首先将索引树在内存中建好,然后在文件中写入树信息,最后通过递归的方式写入结点。实验结果表明,与R-树索引相比,SR-树索引可以在减少最小外接矩形重叠面积的同时,有效降低查询响应时间,从而达到提高查询效率的目的。     

基于LSH的中文文本快速检索

目前,高维数据的快速检索问题已经受到越来越多的关注.当向量空间的维度高于10时,R-tree,Kd-tree,SR-tree的检索效率反而不如线性检索,而位置敏感的哈希(Locality Sensitive Hashing,缩写为LSH)算法成功地解决了高维近邻数据的快速检索问题,因而受到国内外学术界的高度关注.首先介绍了LSH算法的基本原理和方法,然后使用多重探测的方法对二进制向量的LSH算法做了进一步改进.最后实现了这两种LSH算法,并通过详细的实验验证表明:在改进后的算法中,通过增加偏移量可以提高检索的召回率,而在不提高时间复杂度的情况下则可降低空间复杂度.     

An efficient technique for nearest-neighbor query processing on the SPY-TEC

The SPY-TEC (spherical pyramid-technique) was proposed as a new indexing method for high-dimensional data spaces using a special partitioning strategy that divides a d-dimensional data space into 2d spherical pyramids. In the SPY-TEC, an efficient algorithm for processing hyperspherical range queries was introduced with a special partitioning strategy. However, the technique for processing k-nearest-neighbor queries, which are frequently used in similarity search, was not proposed. In this paper, we propose an efficient algorithm for processing nearest-neighbor queries on the SPY-TEC by extending the incremental nearest-neighbor algorithm. We also introduce a metric that can be used to guide an ordered best-first traversal when finding nearest neighbors on the SPY-TEC. Finally, we show that our technique significantly outperforms the related techniques in processing k-nearest-neighbor queries by comparing it to the R*-tree, the X-tree, and the sequential scan through extensive experiments.     

移动数据库中一种基于XML的视图增量更新算法

视图增量更新算法作为提高移动数据库响应性能的重要手段已有许多研究。随着XML结构在移动数据库中的应用,现有的算法不适用于目前移动数据库中存储的数据。提出了以XML树型结构为基础的一种新的视图增量更新算法XSIU（XML Structured-based Incremental Update）,通过该算法能有效解决视图的增量更新在XML中的实现。实验表明,当带宽急剧下降时,该算法能有效提高移动环境中视图的增量更新性能。     

Multidimensional Index Structures in Relational Databases

Efficient query processing is one of the basic needs for data mining algorithms. Clustering algorithms, association rule mining algorithms and OLAP tools all rely on efficient query processors being able to deal with high-dimensional data. Inside such a query processor, multidimensional index structures are used as a basic technique. As the implementation of such an index structure is a difficult and time-consuming task, we propose a new approach to implement an index structure on top of a commercial relational database system. In particular, we map the index structure to a relational database design and simulate the behavior of the index structure using triggers and stored procedures. This can be easily done for a very large class of multidimensional index structures. To demonstrate the feasibility and efficiency, we implemented an X-tree on top of Oracle8. We ran several experiments on large databases and recorded a performance improvement up to a factor of 11.5 compared to a sequential scan of the database.     

Time and work optimal simulation of basic reconfigurable meshes on hypercubes

This paper presents a constant slow-down, optimal and locally normal simulation for basic reconfigurable meshes on hypercubes, if the log-time delay model for broadcasting is assumed. Such a simulation algorithm is based on: (i) an $\text{O}\text{(}\text{log}\text{B)}$ time algorithm for the segmented scan problem on a (2n−1)-node toroidal X-tree, where B is the size of the longest segment; this algorithm is time optimal; (ii) a constant slow-down optimal and locally normal simulation algorithm for basic reconfigurable meshes on the mesh of toroidal X-trees; and (iii) a constant slow-down optimal simulation of locally normal algorithms for meshes of toroidal X-trees on the hypercube.     

An encoding-based dual distance tree high-dimensional index

The paper proposes a novel symmetrical encoding-based index structure, which is called EDD-tree （for encoding-based dual distance tree）, to support fast k-nearest neighbor （k-NN） search in high-dimensional spaces. In the EDD-tree, all data points are first grouped into clusters by a k-means clustering algorithm. Then the uniform ID number of each data point is obtained by a dual-distance-driven encoding scheme, in which each cluster sphere is partitioned twice according to the dual distances of start- and centroid-distance. Finally, the uniform ID number and the centroid-distance of each data point are combined to get a uniform index key, the latter is then indexed through a partition-based B^＋-tree. Thus, given a query point, its k-NN search in high-dimensional spaces can be transformed into search in a single dimensional space with the aid of the EDD-tree index. Extensive performance studies are conducted to evaluate the effectiveness and efficiency of our proposed scheme, and the results demonstrate that this method outperforms the state-of-the-art high-dimensional search techniques such as the X-tree, VA-file, iDistance and NB-tree, especially when the query radius is not very large.     

Finding short structural motifs for re-construction of proteins 3D structure

With a view to find useful building blocks (short structural motifs) for reconstruction of 3D structure of proteins, we propose a modified neural gas learning algorithm that we call structural neural gas (SNG) algorithm. The SNG is applied on a benchmark protein data set and its performance is compared with a well known algorithm from the literature (two stage clustering algorithm (TSCA)). The SNG algorithm is found to generate better building blocks compared to TSCA. We have also compared the performance of SNG algorithm with that of a recently reported Incremental Structural Mountain Clustering Method (ISMCM). In general, ISMCM is found to use more building blocks to yield results comparable to that of SNG algorithm. We demonstrate the superiority of SNG over TSCA both in terms of local-fit and global-fit errors using fragments of length five, six, and seven. We also use a graphical means for comparison of the performance of the two algorithms.     

自适应群体结构的粒子群优化算法

粒子群优化算法中,群体结构的组织模式直接决定了粒子间信息的共享和交流方式.根据复杂网络形成过程中的动力学原理,提出了一种自适应群体结构的粒子群优化算法.算法初期粒子空间分布分散,搜索过程中不断产生新的连接,群体的搜索模式由L_best? 模型逐渐进化为G_best? 模型,群体结构的这种进化方式有利于算法早期的“勘探”和后期的“开采”.实验结果表明,新算法在收敛性能上获得了较大提高.