变化 Wiener指数的变点研究

Wiener指数是 Harold Wiener提出的广泛应用于化学研究中的一个重要拓扑指数。I ．Gutman等把Wiener指数推广为变化Wiener指数。M ．H ．Liu等给出了最大度Δ≥ n/2时,树中最大的变化Wiener指数的极图。论文用数值计算方法研究了树 F（n ,Δ）和 H（n ,Δ）的变化Wiener指数的大小关系,得到了刻画树 F（n ,Δ）和树 H （n ,Δ）的变化Wiener指数大小关系的变点λ0和 n ,Δ之间的变化规律,以及给定最大度的树中次大（小）的变化Wiener指数的极图。特别地,得出Δ＜ n/2时的变化规律。     

一种新的删除红黑树的结点的算法

提出一种新的删除红黑树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。证明新算法是正确的。设n是红黑树的内部结点的个数。执行新算法时进行O（1）次旋转。新算法的时间复杂性是O（log2n）。实验结果表明新算法的平均执行时间比Tarjan的算法和Guibas-Sedgewick算法的短。新算法的空间复杂性是O（1）。     

基于B_树的证书吊销实用系统

针对公钥基础设施PKI中证书吊销问题,提出一种B_树解决方案,将查询与更新时的最大时间复杂度始终保持在O（logd（（n＋1）/2）＋1）量级,与其他方案相比,当数据量特别大时,更能显示其优越性,同时介绍基于B_树的证书管理方案。实验结果表明,该方案对工程实现具有一定指导意义。     

存在完整性约束时最小化树模式查询的算法

树模式是查询树型结构数据如XML和LDAP的天然模型。在一个给定的数据库上进行查询,查询的效率很大程度上依赖于查询的大小。因此,在查询前删除查询中的冗余分支,使查询最小化是非常重要的。在树型结构数据库中,存在孩子必需、后代必需和子类3种完整性约束是十分普遍的。针对存在这3种完整性约束的情况,基于扩展的模拟概念提出了一种复杂度为O（n^2）的最小化树模式查询算法（n为树模式查询的节点数）。分析结果表明这个算法的效率要远高于同类算法。     

改进的赫夫曼树（Huffman Tree）和赫夫曼编码（Huffman Code）构造算法

通过将待排序的数据应用快速排序算法进行排序处理,使得赫夫曼算法（Huffman Algorithm）65时间复杂度从O（n^2）降低为O（n＊log2n）。当用于构造赫夫曼树（Huffman Tree）的结点比较多时,可较大的提高程序的运行时间。     

快速动态优先搜索树的实现及其应用

对形如（x1：x2,[-∞：y]）的二维查询问题,提出一种快速的、易于实现的动态优先搜索树数据结构及其相关算法,采用只在叶节点存储数据的结构,以及在常数时间内实现旋转操作的算法。设n为数据点的个数,k为满足搜索条件的解的个数,则该动态搜索树空间复杂度为O（n）,插入、删除操作的时间复杂度为O（10gn）,搜索复杂度为O（logn＋k）。     

高速公路收费站模型优化设计的研究

利用排队论、最优化理论等方法对问题进行了较为全面的分析,在此分析的基础上以司机满意度y＝f（t）为目标函数分别建立了p条车道,n条通道,一条通道上一个收费亭的数学模型M（p,n,1）和一条通道上两个收费亭的数学模型M（p,n,2）,通过对建立的模型进行对比给出不同车流量的情况下,一道一亭和一道两亭的平均延误时间。最后综合考虑了高速公路和收费站的基本情况,给出了模型进一步改进的方向,从而进一步扩大了模型的应用范围。     

旅行商问题中巡回路径的数据结构

旅行商问题中巡回路径的数据结构对局部启发式算法的效率起着非常关键的作用。巡回路径的数据结构必须能够查询一条回路中每个城市的相对顺序,并且能够将一条回路中的部分城市逆序。分析了数组表示法、伸展树表示法和两级树表示法表示巡回路径时各种基本操作的实现过程及时间复杂度。数组表示法能够在常数时间内确定一条回路中每个城市的相对顺序,但是最坏情况下完成逆序操作需要Ω（n）时间,不适用于大规模的旅行商问题。伸展树表示法执行查询和更新操作的平摊时间复杂度是O（logn）,适用于极大规模的旅行商问题。而两级树表示法在最坏情况下每一个更新操作的时间复杂度是O（n^0.5）,适用于大规模的旅行商问题。     

插值两个平行平面曲线的可展B样条曲面

两条位于平行平面上的分别是[n]次和[n+1]次B-样条曲线,以这两条曲线作边界生成一个直纹面,即[(n,n+1)]次B样条曲面,得到了该直纹面为可展曲面的充要条件,构造了（2,3）次可展B－样条曲面。通过对以上可展B样条曲面进行凸性分析,得到了（n,n+1）次可展B样条曲面为凸曲面的充要条件。给出了几个（2,3）次B-样条可展曲面。     

基于改进渐进最优的双向快速扩展随机树的移动机器人路径规划算法

针对带启发式的快速扩展随机树（RRT-Connect）算法路径生成的随机性以及渐进最优的双向快速扩展随机树（B-RRT^*）算法收敛速度的缓慢性，提出了一种基于B-RRT^*改进的高效路径规划算法（EB-RRT^*）。首先引入一种智能采样函数，使随机树的扩展更具方向性，从而减少寻路时间，并提高路径的平滑性；其次在B-RRT^*算法的基础上，在EB-RRT^*算法中加入了一种快速扩展策略，使改进后的算法在自由空间中使用RRT-Connect算法的扩展方式进行快速扩展，而在障碍物空间则使用改进的渐进最优的快速扩展随机树（RRT^*）算法进行扩展，在提高扩展效率的同时避免算法陷入局部最优。将EB-RRT^*算法分别与快速扩展随机树（RRT）、RRT-Connect、RRT^*和B-RRT^*算法进行仿真对比，仿真结果表明，改进后的算法在路径规划效率及路径平滑性方面均明显优于其他算法；且相对于B-RRT^*算法，其在路径规划时间上降低了68.3%，在迭代次数上减少了48.6%。     

基于动态文档集的索引技术*

倒排文件是全文检索中广泛使用的索引结构,对静态文档集合建立倒排索引的研究已有较长时间。随着计算机技术的发展,需要存储的数据越来越大。同时特定的应用领域如新闻搜索、桌面搜索等对实时更新性能要求较高,这需要使用有效的索引更新策略,也称动态索引。描述了常用的动态索引技术,并详细分析了其使用代价。     

利用垂直植被指数推算作物叶面积系数的理论模式

从作物冠层对光谱的反射特征出发，推导了叶面积系数LAI的遥惑枯算模式，并利用水稻样点观浏数据对模式进行了验证，取得了良好效果。     

一种有效的混合空间索引机制

论文结合网格索引和R树索引的特点,提出了一种基于粗分网格和聚类R树的混合索引方案(HSIBGR)。该方案首先将矩形地理空间进行粗网格划分建立一级索引,然后针对每个小网格建立基于R树的二级索引,采用聚类技术处理溢出R树结点的分裂。论文还对HSIBGR索引机制进行了理论分析和实验验证,结果表明HSIBGR索引机制能有效地减少存储开销,提高检索效率,具有良好的性能。     

基于分区的Elias-Fano-Golomb-Rice倒排索引压缩算法

基于分区的Elias-Fano算法被应用于倒排索引压缩,显示出良好的空间压缩性能。本文证明了Golomb-Rice算法的压缩性能优于Elias-Fano算法。结合基于分区的Elias-Fano算法中“分区”思想,提出一种基于分区的Elias-Fano-Golomb-Rice倒排索引压缩算法。实验结果表明,与其他倒排索引压缩算法相比,基于分区的Elias-Fano-Golomb-Rice倒排索引压缩算法有更好的压缩性能。     

使用索引提升数据库性能

影响到数据库性能的最大因素是索引,建立合理的索引可以大幅度的提升数据库性能,这里以SQL SERVER为例,我简单的介绍一下索引的相关知识,以及如何设置合理的索引提高数据库性能.     

单汉字检索中的集合索引方法

根据汉字在文献中使用的频度和分布规律，利用图书分类的原则，提出了基于汉字在成组（连续索引号）文献中出现的集合索引方案。与基于单值表达的常规索引方案作了比较，并对一类短语料进行了实验，给出了部分比较结果以及索引调整的一些分析结果。模拟图书分类中汉字非均匀分布的特点，从理论上分析文献索引各参量间的关系。分析表明，集合索引法与单值表达索引相比，能够显著提高索引效率，减少索引空间，还可进行随机动态调整。     

一种新型索引结构

传统Hash算法中溢出桶与主桶、溢出桶与溢出桶之间一般通过指针实现链接,对海量数据的等值查询采用指针方式效率很低。该文提出一种动态哈希索引算法,用B+树结构表示桶地址表,在桶地址表与记录键值之间建立一个B+树结构,通过二分查找可直接找到相应桶元素。实验结果表明,该算法的综合性能优于其他索引,其等值查询效率提高了15%。     

基于Lucene的分布式并行索引

索引技术是搜索引擎的核心技术之一,索引技术的好坏直接影响到搜索引擎的查准率以及对用户的响应速度。Lucene是一个优秀的全文检索引擎架构,采用高度优化的倒排索引结构并支持增量索引。但在实际应用Lucene时存在一个值得关注的问题：随着被索引文件的增多,索引时间成线性增长,导致建索引的过程会影响搜索体验;在搜索引擎应用中,当索引文件量达到一定等级时,搜索引擎就遇到性能瓶颈。在深入分析和研究Lucene索引机制的基础上,采用以内存为缓冲区建索引文件的分布式并行索引技术形成了一个可扩展的搜索引擎解决方案,极大地缓解了建索引给搜索带来的瓶颈问题。     

基于Cassandra的可扩展分布式反向索引的构建

随着云计算时代的到来,大型Web应用的不断发展,海量数据不断增加,集中式的数据检索已不再满足需求.如何在分布式的环境中高效地处理数据检索成为亟待解决的问题.传统的关系型数据存储也无法完全适应云环境,NoSQL(Not only SQL)作为一种云存储形式应运而生,其中Cassandra的应用较为广泛.以分布式的多节点架...     

被含均匀度及其仿真

均匀度是一个有限点集在一个多面体内分布均匀性的描述,已经证明被含均匀度CL渐近服从x2(2m)/2Vn(1)m分布,且有E(CL)=Г(n/2 1)/πn/2,用地理信息系统开发语言Avanue对均匀度和被含均匀度进行了摸拟,为均匀度的收敛性证明打下了基础.