关于重复词句提取的两种算法分析

针对重复网页的去重问题,对两种重复词句提取算法进行了系统分析比较。STC算法在时间成本上具有优秀性能,重复序列的倒排索引方法在空间复杂度方面更胜一筹。结合STC算法对重复序列方法进行了改进,而面向主题转载的重复网页,先抽取重复串,然后将重复串作索引进行STC算法的重复抽取。实验结果表明,改进算法在保持了原有空间特性的基础上极大地提高了时间效率。     

基于组合索引的语义Web服务发现算法

为提高Web服务发现的效率,将倒排索引和功能兼容性索引相结合,设计一种组合索引方法。组合索引由服务的加权简洁功能兼容图和输出概念的图节点倒排索引构成。基于组合索引,提出一种服务发现算法,与基于倒排索引和功能兼容性索引的服务发现算法的对比分析表明,该算法能够明显减少功能兼容性检查的次数和平均索引链长,具有较优的性能。     

MD5算法在消除重复网页算法中的应用

Internet用户通过常用搜索引擎获取Web信息时,往往得到了大量的重复网页信息,从而导致搜索效率不高.本文利用MD5算法成熟及可移植性好的特点,提出了一种基于MD5的消除重复网页的算法,实验证明该算法能有效的去除重复网页,时间和空间的复杂度不高,具有较强的实用价值.     

MD5算法在消除重复网页算法中的应用

Internet用户通过常用搜索引擎获取Web信息时,往往得到了大量的重复网页信息,从而导致搜索效率不高。本文利用MD5算法成熟及可移植性好的特点,提出了一种基于MD5的消除重复网页的算法,实验证明该算法能有效的去除重复网页,时间和空间的复杂度不高,具有较强的实用价值。     

基于扩展倒排索引的不确定XML关键字查询算法

现有的不确定XML关键字查询算法均需遍历不确定XML文档,并且算法在执行过程中需要频繁的字符串比较,造成时间浪费。针对上述问题,提出基于扩展倒排索引的不确定XML关键字查询算法Pr E。扩展倒排索引有效地存储了不确定XML文档中节点的相关信息,根据扩展倒排索引即可初始化动态哈希表和序号编码链表,并且Pr E算法在执行过程中利用整数的比较代替了字符串的比较。理论分析与实验结果表明,Pr E算法是一种高效的不确定XML关键字查询算法。     

基于Trie树的相似字符串查找算法

基于Trie树的相似字符串查找算法是利用编辑距离的阈值来计算每个节点的活跃节点集,已有算法由于存在大量的冗余计算,导致时间复杂度和空间复杂度都比较高。针对这个问题,采用了基于活跃节点的对称性和动态规划算法的思想对已有算法进行改进,并对活跃节点集进行了修剪,提出了New-Trie-Stack算法。该算法避免了活跃节点的重复计算,以及已有算法在保存所有已遍历节点的活跃节点集时的空间开销。实验结果表明New-Trie-Stack算法在时间复杂度和空间复杂度上都有明显的下降。     

基于CRF的分区倒排索引压缩算法

倒排索引是大型搜索引擎的核心数据结构,本质是倒排列表中整数序列的集合。倒排索引压缩可以有效减少倒排索引所占空间,提高对关键词的检索效率。本文提出的基于条件随机场（CRF）的分区倒排索引压缩算法主要关注域值分区的分区方式。该算法对序列进行预分区,并且使用条件随机场对预分区进行标注并重组,有效减少了压缩时间。根据分区类型,该算法使用相应的编码方式,进一步减少了压缩后的空间占用。与其他倒排索引压缩算法进行对比实验分析,结果表明本文算法在压缩率上超过目前一些域值分区的算法,并且在解压时间上与其他域值分区算法相当。该算法在时间和空间上取得了较好的平衡。     

OIQ-tree:一种支持大规模空间文本数据流上连续k近邻查询的索引

空间文本数据流上连续k近邻查询(Continuous k-nearest neighbor Queries over Spatial-Textual data streams,CkQST)能在空间文本对象组成的数据流上检索并实时更新k个包含指定关键字的空间邻近对象,是空间文本数据流上连续查询(Continuous Queries over Spatial-Textual data streams,CQST)的一种,以预订(subscribe)的方式广泛应用于广告定位、微博分析、地图导航等领域.求解CkQST采用CQST的求解框架——构建空间文本混合索引组织查询,利用索引的空间过滤和文本过滤能力,为不断到来的对象匹配查询.该框架的求解效率取决于索引的过滤能力,提高索引过滤能力的主要途径是将查询的空间搜索范围映射到索引结构的最小区域,减少需要验证的查询数量.这一途径适用于查询空间搜索范围很少变化的情况.对于CkQST,覆盖k个最邻近对象的空间范围随着符合文本匹配条件的对象的数量的变化而变化,与之对应的索引项需要同步更新,代价高.针对这一问题,本文选择能够高效支持空间范围变化的Quad-tree和关键字查找的倒排索引,构成空间文本混合索引,组织CkQST.在空间过滤方面,提出内存代价模型VUMBCM(Verification and Update of Memory-Based Cost Model),通过平衡索引更新代价和验证代价,优化查询空间搜索范围到Quad-tree节点的映射.在文本过滤方面,采用基于块的有序倒排索引,组织Quad-tree节点内的查询,以快速定位需要验证的查询,避免对倒排列表中大量不可能匹配查询的访问;批量处理包含共同文本项的对象,提高文本验证时的对象吞吐量.由此构建的混合索引,称为OIQ-tree.实验表明,OIQ-tree中的代价模型及基于块的有序倒排索引能够支持CkQST的高效求解.与目前先进的索引技术相比,当查询规模达到2000万时,因数据流中对象的变化导致的索引平均更新时间降低了 46％,数据流中对象的平均处理时间降低了 22％.     

基于时空域信息融合的视频拷贝检测算法研究

为了有效利用视频独有的时空域特性来提高视频拷贝检测算法的鲁棒性和精度,提出一种基于时空域信息融合的快速拷贝检测算法。该算法包括基于时空域信息融合的指纹提取算法、基于倒排索引的匹配搜索算法和结合异步滑窗策略的基于匹配状态机的匹配搜索算法。指纹提取算法首先将视频分段形成时空域信息帧,然后对该信息帧进行分块,提取DCT系数后,利用其中值进行阈值化得到视频指纹。基于倒排索引的搜索算法根据指纹的二值性特点建立倒排索引表,然后通过索引表快速查询指纹。结合异步滑窗策略的基于匹配状态自动机的搜索算法,利用与最近邻之间的匹配状态来改变搜索范围和步长,而异步滑窗策略通过对在线和离线过程采用不同的提取策略,减少搜索量,加快搜索速度。实验结果表明,提取的指纹对噪声模糊、添加字幕、空间偏移、旋转、掉帧具有较好的鲁棒性,同时提出的搜索方案在时间效率上也有较大的提升。     

DNA序列中基于后继数组索引的LPR查找算法

DNA序列中的重复片段在人类基因研究中有着非常重要的生物意义,因此,查找给定DNA序列中的重复片段是生物序列分析领域中的一个重要课题.基于重复片段的模式提出了新的重复片段定义LPR(largest pattern repetition)和模式单元的概念.对于长度为n的DNA序列,其中的LPR的数量是O(n)数量级的,但提供了与个数可多达n2/4的tandem repeat相同的重复片段信息.基于模式单元设计了可用于重复片段查找的全新索引--后继数组.后继数组有效地降低了索引空间,很好地突破了重复片段查找中的索引空间瓶颈.在后继数组上,通过模式单元可发现构成LPR的全部原子模式,并通过判断相同模式是否在原序列中连续出现完成LPR的查找.理论分析和实验结果均表明,设计的LPR查找算法的时间和空间复杂度均为O(n).     

一种基于HBase的高效空间关键字查询策略

随着移动定位技术的发展以及智能手机的普及,互联网中空间文本对象的数量正在急速增长,如何在规模庞大且动态增长的空间文本对象中进行高效的空间关键字查询成为了许多空间关键字查询应用所关心的问题.现有的方法通常利用基于R树和倒排索引的混合索引结构来处理空间关键字查询,然而,面对数量巨大而且不断增长的空间文本对象,这些方法往往难以为空间关键字查询的高效性和扩展性提供支持.对此,提出一种基于HBase的空间文本数据索引结构SK-HBase.SK-HBase以HBase作为数据存储,通过有效的数据分配策略对空间文本对象的空间信息和文本信息同时进行索引.在SK-HBase的基础上,本文提出了两种空间关键字查询算法,以保证不同空间范围下的空间关键字查询的高效性和可扩展性.实验证明,我们的方法能够在海量数据下进行高效的空间关键字查询并具有良好的可扩展性.     

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

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

海量数据库中实时包的判重算法

关系数据库中的索引技术可以快速判断记录重复,但对于频繁更新的海量数据库,维护索引的时间与资源开销较大。针对交通量数据包及其海量数据库的特点,提出一个交通量实时包的时序区间模型,给出并证明了一个基于区间记录的快速判重算法,分析了算法的复杂度,探讨了改进算法的方法。该算法具有复杂度与数据库大小无关、高效、易于实现等特点。     

无线传感网最大剩余能量索引数据分发算法

提出一种基于索引和局部存储的（Index and Local Storage—based,ILS）数据分发算法MREIB—DD。对于ILS类型的数据分发算法,一个事件的监测数据被存储在该数据的监测节点或监测节点的邻居节点。一个存储节点仅当接收到一个来自Sink的查询,才把监测数据发送至Sink。MREIB-DD算法选择网络中有最大剩余能量的节点存储索引信息,传感器节点监测到数据时向索引节点发送该数据的有关索引信息。用户的查询信息先到达索引节点,索引节点把查询转发到数据存储点,存储点对查询进行响应。此算法避免了感知数据的网内传输和查询泛洪带来的开销,分析表明该算法性能优于GHT—DCS算法而复杂度增加较少,是能量高效的数据分发算法。     

基于数据流的脆弱性静态分析

关系数据库中的索引技术可以快速判断记录重复,但对于频繁更新的海量数据库,维护索引的时间与资源开销较大.针对交通量数据包及其海量数据库的特点,提出一个交通量实时包的时序区间模型,给出并证明了一个基于区间记录的快速判重算法,分析了算法的复杂度,探讨了改进算法的方法.该算法具有复杂度与数据库大小无关、高效、易于实现等特点.     

面向文本拷贝检测的分布式索引

如何对大规模文档集进行高效的拷贝检测是长期以来一直受到研究者们关注的问题。通常的拷贝检测算法都需要借助倒排索引。因此良好的索引结构对于算法性能至关重要。同时,随着文档集规模的增大,单机实现的索引已经不能满足拷贝检测的需求,需要引入分布式存储的索引。为了适应文档集规模的不断增大,良好的分布式索引应该同时具备较高的效率和可扩展性。为此该文比较了两种不同的分布式索引结构,Term-Split 索引和Doc-Split 索引,并且给出了Map-Reduce范式下建立这两种索引的实现,以及以这两种索引为基础的文本拷贝检测方法,Term-Split 方法和Doc-Split方法。在WT10G文档集上进行的实验表明Doc-Split 方法具有更好的效率和可扩展性。     

无线传感网最大剩余能量索引数据分发算法

提出一种基于索引和局部存储的(Index and Local Storage-based,ILS)数据分发算法MREIB-DD.对于ILS类型的数据分发算法,一个事件的监测数据被存储在该数据的监测节点或监测节点的邻居节点.一个存储节点仅当接收到一个来自Sink的查询,才把监测数据发送至Sink.MREIB-DD算法选择网络中有最大剩余能量的节点存储索引信息,传感器节点监测到数据时向索引节点发送该数据的有关索引信息.用户的查询信息先到达索引节点,索引节点把查询转发到数据存储点,存储点对查询进行响应.此算法避免了感知数据的网内传输和查询泛洪带来的开销,分析表明该算法性能优于GHT-DCS算法而复杂度增加较少,是能量高效的数据分发算法.     

基于数据交换的传感器网络低功耗路由算法

由于在敌意或恶劣环境下,传感器网络节点的能量无法补充,研究节点能量用尽时,如何交换工作节点和睡眠节点的工作模式有重大意义。基于节点整体交换算法,提出了数据交换算法,新算法采用正方形网格剖分方法,对收集信息区域进行剖分,当网格某节点能量用尽时,进行节点数据交换。理论分析与实验测试结果表明：新算法能有效延长整个传感器网络的生命周期,并在时间复杂度与空间复杂度方面比整体交换算法具有更优性能。     

基于iMeMex数据模型的数据空间索引方法研究

目前,个人和组织的信息呈现急剧增长趋势,且非结构化数据所占比重在不断增加,这些属于某个主体的海量、分布、异构和共存的数据构成了一个异构数据空间,如何为用户提供高效、便捷和多样化的搜索查询服务是数据空间面临的巨大挑战,为数据空间中异构数据构建高效的索引方法是解决这一问题的基础。对iMeMex数据模型的特点和数据空间中查询方法进行了分析,在此基础上通过扩展倒排列表方法,提出了一种基于iMeMex数据模型的索引方法,来提高对数据空间中异构数据的搜索查询效率。新的索引方法通过扩展倒排列表的关键字列和链表节点信息索引资源视图,来支持和提高关键字查询、谓词查询和路径查询的处理效率。实验结果表明,该索引方法能够有效、可行地解决数据空间中异构数据索引和查询效率问题。     

基于计数型布隆过滤器的文本检索模型

分布式文本检索系统难以兼顾高效率的数据检索和低成本的索引维护。为此,提出一种基于计数型布隆过滤器的文本检索模型CBFTRM。该模型将物理节点分为数据节点和索引节点,分别采用结构化P2P进行网络覆盖。每个数据节点负责存储文档数据并维护与之相应的倒排索引,同时通过倒排索引中的关键词集合计算出计数型布隆过滤器值,发送给相应的索引节点。每个索引节点建立一棵以部分数据节点的特征信息(包括过滤器值)为叶节点、以过滤器值运算结果为内部节点的搜索树,并在叶节点发生变化时对搜索树进行维护。仿真实验结果表明,该模型文档定位快,索引维护通信量小,而且具有较高的查准率。