搜索引擎分块索引技术研究

搜索引擎通常使用签名文件、倒排索引、后缀树/后缀数组来构建索引,其中倒排文件由于性能可靠、实现简单,得到广泛应用.但是在现今海量数据情况下,有时倒排索引仍显力不从心,导致检索性能不佳,提出了分块索引术,可以有效提高基于倒排索引搜索系统检索效率.     

一种UDP报文数据的搜索方法

在分布式数据传输中,UDP协议由于实现机制简单、传输效率高,被大量应用系统所采用。为了数据分析和处理的需要,常常要对录取得到的海量UDP报文数据进行搜索,以得到符合要求的报文。针对以上需求,文章在UDP报文数据的搜索中引入倒排索引机制。从存储、生成两个方面对UDP报文倒排索引进行了详细论述,并介绍了利用UDP报文倒排索引的报文搜索方法。     

自然语言网络答疑系统中倒排索引技术的研究

为了提高自然语言网络答疑系统(Natural Language Web Answer System,简称NLWAS)中问答对的匹配速度和精度,提出了基于倒排词的倒排索引设计方案,详细阐述了索引体系结构、数据结构、匹配策略、动态维护,并对时间复杂度进行了分析。实际应用结果表明,使用倒排索引后系统性能优化效果明显增强。     

自然语言网络答疑系统中倒排索引技术的研究

为了提高自然语言网络答疑系统（Natural Language Web Answer System，简称NLWAS）中问答对的匹配速度和精度，提出了基于倒排词的倒排索引设计方案，详细阐述了索引体系结构、数据结构、匹配策略、动态维护，并对时间复杂度进行了分析。实际应用结果表明，使用倒排索引后系统性能优化效果明显增强。     

基于倒排索引的可搜索加密数据共享方案

针对当前医疗数据共享难、数据被攻击、密文搜索效率低的问题，提出了一种基于倒排索引的可搜索加密数据共享方案。采用基于私有链和联盟链的双链结构存储数据并实现数据共享；设计了一种新型倒排索引结构，防止敏感数据被攻击；提出了一种基于新型倒排索引结构的密文搜索算法，利用可搜索加密技术将陷门信息提交至倒排索引结构中实现密文搜索。实验表明，所提出的方案可以有效保证数据安全，提高搜索效率。     

编码单位可变的倒排索引压缩算法研究

倒排索引是大多数大型文本搜索系统的核心数据结构，索引压缩可以有效地减少倒排索引的空间占用，提升检索效率。针对倒排索引压缩算法中的字节对齐编码进行研究，对于其压缩率不够优秀的问题，提出了分区可变单位编码（PVU编码）。算法以可变单位方式代替固定字节存储，使实际存储空间更加贴合原码长度，从而提高压缩效果。针对序列均匀分区并非最优分区的问题，提出将最优分区问题转化为图论中最短路径问题的方法，使用Dijkstra算法求解序列的最优编码分区。通过对比实验验证了改进优化的PVU编码相较于传统的字节对齐编码能够更好地压缩倒排索引序列。     

基于分布式倒排索引和VSM算法的P2P复杂搜索

传统的基于DHT的结构化P2P系统有一定的局限性,如不支持多特征词的复杂搜索,无法对搜索结果进行排序等.通过改进的分布式倒排索引,支持多特征词的复杂搜索,并极大改善了传统的倒排索引技术引起的网络流量消耗;通过改进的VSM算法,对搜索结果进行排序;提出了新的资源发布算法.     

分布式环境下多关键词并行密文检索方案

对于可搜索加密需要均衡数据的安全性和检索效率。针对SSE-1密文检索方案中检索性能低、单关键词检索模式不足和传统单服务器架构中的单机资源局限性等问题，设计并实现了一种多关键词并行密文检索系统。该系统采用不同的索引加密方式提高密文检索性能；通过对密文倒排索引的切分实现倒排索引的分块检索，克服了单机资源的局限性并提高了检索效率；通过结合分布式特点扩展了传统单机检索架构并实现了多关键词的并行检索。实验结果表明，与SSE-1方案相比，在保证密文数据安全性的前提下所提方案能够提高检索、更新等操作的效率，实现多关键词的检索，同时动态扩展系统分布式架构以提高系统负载能力。     

倒排索引中的文档序号重排技术综述

倒排索引作为文本搜索的核心索引技术,广泛应用于搜索引擎、桌面搜索和数字图书馆领域。倒排索引由字典和对应的倒排表组成,倒排表一般采用差值存储和整数编码进行压缩。研究表明,当倒排表具有较好的局部连续性时,上述方法能够获得很高的压缩率。整数编码研究通过不断改进编码算法来充分利用倒排表的局部连续性特征,而文档序号重排正是一种对文档序号重新排列来产生局部连续性的技术。通过文档序号重排,索引压缩率得到显著提高。该文主要介绍近年来文档序号重排技术取得的研究成果: 首先介绍索引压缩的基本原理,然后详细介绍文档序号重排技术,包括分析、对比各个方法的优劣;最后对文档序号重排技术进行总结、整理和展望。     

搜索引擎建立倒排索引的算法研究

搜索引擎并不真正搜索互联网,它搜索的实际上是预先整理好的网页索引数据库.因此网页索引库建立的好坏直接影响最后的查询结果的准确性和用户的查询速度.本文提出了一种建立倒排索引的算法并进行了分析和研究.     

Semplore: A scalable IR approach to search the Web of Data

The Web of Data keeps growing rapidly. However, the full exploitation of this large amount of structured data faces numerous challenges like usability, scalability, imprecise information needs and data change. We present Semplore, an IR-based system that aims at addressing these issues. Semplore supports intuitive faceted search and complex queries both on text and structured data. It combines imprecise keyword search and precise structured query in a unified ranking scheme. Scalable query processing is supported by leveraging inverted indexes traditionally used in IR systems. This is combined with a novel block-based index structure to support efficient index update when data changes. The experimental results show that Semplore is an efficient and effective system for searching the Web of Data and can be used as a basic infrastructure for Web-scale Semantic Web search engines.     

面向路网的移动对象全时态高效索引模型

针对现有索引模型的冗余搜索问题,考虑路网拓扑结构及交叉口转向约束条件,提出一种面向路网的移动对象全时态高效索引模型。采用添加临近路段信息的方法索引历史轨迹和实时位置信息,设计新型窗口查询算法,实现移动对象查找,并运用指数平滑法进行轨迹的预测。实验结果表明,该模型具有较好的更新及查询性能。     

Trustworthy keyword search for compliance storage

Intense regulatory focus on secure retention of electronic records has led to a need to ensure that records are trustworthy, i.e., able to provide irrefutable proof and accurate details of past events. In this paper, we analyze the requirements for a trustworthy index to support keyword-based search queries. We argue that trustworthy index entries must be durable—the index must be updated when new documents arrive, and not periodically deleted and rebuilt. To this end, we propose a scheme for efficiently updating an inverted index, based on judicious merging of the posting lists of terms. Through extensive simulations and experiments with two real world data sets and workloads, we demonstrate that the scheme achieves online update speed while maintaining good query performance. We also present and evaluate jump indexes, a novel trustworthy and efficient index for join operations on posting lists for multi-keyword queries. Jump indexes support insert, lookup and range queries in time logarithmic in the number of indexed documents.     

基于中间层的可扩展学习索引技术

在大数据与云计算时代,数据访问速度是衡量大规模存储系统性能的一个重要指标.因此,如何设计一种轻量、高效的数据索引结构,从而满足系统高吞吐率、低内存占用的需求,是当前数据库领域的研究热点之一.Kraska等人提出使用机器学习模型代替传统的B树索引,并在真实数据集上取得了不错的效果,但其提出的模型假设工作负载是静态的、只读的,对于索引更新问题没有提出很好的解决办法.提出了基于中间层的可扩展的学习索引模型Dabble,用来解决索引更新引发的模型重训练问题.首先,Dabble模型利用K-Means聚类算法将数据集划分为K个区域,并训练K个神经网络分别学习不同区域的数据分布.在模型训练阶段,创新性地把数据的访问热点信息融入到神经网络中,从而提高模型对热点数据的预测精度.在数据插入时,借鉴了LSM树延迟更新的思想,提高了数据写入速度.在索引更新阶段,提出一种基于中间层的机制将模型解耦,从而缓解由于数据插入带来的模型更新问题.分别在Lognormal数据集以及Weblogs数据集上进行实验验证,结果表明,与当前先进的方法相比,Dabble模型在查询以及索引更新方面都取得了非常好的效果.     

基于索引和压缩的超高速路由查找及更新算法

在下一代核心路由器的研究中．需要在规定的硬件成本和功耗限制下同时实现超高速路由表的查找和更新是目前研究的难点．论文提出了一个全新的超高速路由表查找及更新算法．该算法采用了基于索引和路由表隐式压缩的方案，不仅实现了可以在每一个SRAM的访问延时周期内输出一个路由查找结果．而且能够在两次SRAM的读写访问延时下完成路由更新．该算法功耗小，存储效率高，整个路由表的信息都可存放在容量接近于1M字节的SRAM中．     

基于Lucene的中文倒排索引技术的研究

索引是所有搜索引擎的核心概念,为了进行快速查找,就需要把数据处理成一种高效的、可交叉引用的组织格式。倒排索引是一种高效的索引组织模式,其组织模式和存储结构对检索系统的性能起着至关重要的作用,文中探讨了基于Lucene的倒排索引模式,分析了Lucene索引文件的结构、索引过程以及相关排序算法,讨论了Lucene的压缩算法,并且通过设计一个中文模块实现了基于正向减字最大匹配分词方式的中文索引。实验表明新的分词算法比Lucene自带的分词算法性能有了很大的提高。     

度量空间一种自底向上索引树构造算法

在多媒体或复杂对象数据库中,相似性搜索是一种非常重要的操作,这些操作一般可以归结为度量空间的相似性查询．提出一种新的度量空间索引数据结构（bu-tree）,它是基于自底向上的分层聚类来构造索引结构,而传统的度量空间数据结构大部分是基于自顶向下构造的方法．相对于传统的构造方法,bu-tree可以在更小的索引半径内包含更多的对象,这样有利于查询的筛选．给出了bu-tree的构造算法以及相应的范围查询算法．实验表明,bu-tree的性能好于sa-tree,特别是在度量空间不是均匀分布或者查询具有较低的选择度情况下．     

向量空间划分类索引的动态更新代价分析

代价分析是借助代价模型预测和评估空间索引结构的一种有效方法。针对索引的空间划分和数据划分这两种策略,在已有的索引结构基础上建立了向量空间划分类型索引的代价模型,该模型可实现查询以及动态更新的性能评价。以KDB-树系为评估对象,从结点存取次数（NA）值推导计算出页面存取次数（PA）的估计值,并在标准数据分布上对估计值的相关误差率进行了验证。结果表明代价模型的平均相关误差率较低,不超过12%。代价分析的结果有助于对索引结构的动态更新代价的预估和查询的优化。     

基于MongoDB的轨迹大数据时空索引构建方法

近年来,随着计算机技术与无线传感器网络的发展,轨迹大数据越来越得到人们的关注.针对海量轨迹数据在存储与查询中出现的效率问题,文章基于文档型非关系型数据库MongoDB提出了一套基于四叉树的道路网时空索引,实现海量轨迹数据的高效查询.通过对太原市1915辆出租车的50万条轨迹数据进行时空查询,在不同数据量与不同并发数下测试道路网时空索引与MongoDB复合时空索引的效率表现.实验结果显示道路网时空索引在数据量大于10万时有较好表现,并能够适应不同并发数下的时空查询,验证了道路网时空索引构建方法的可行性和高效性.     

面向海量水利数据的索引方法研究

水利数据的存储形式多样、数据量庞大以及水利实体种类丰富,针对每一类水利实体对象,不仅存在基础描述信息,也存在一系列测量业务信息,这2类数据存储和更新频率不相同。水利业务检索不仅要求能实现对象基础信息的快速检索,还要求根据基础描述信息和业务信息之间的依赖进行组合查询,而目前云环境中,尚缺能满足此类兼顾多类型数据之间依赖关系的高效索引方法。此外,水利数据量的急剧增长,给系统检索性能带来了巨大的挑战。为此,本文提出基于Hadoop的分布式双层索引结构HRB,针对不同的数据类型建立不同的索引。经实验验证,HRB索引与常规分布式索引相比,索引创建效率更优,且在数据量达到千万级别时,HRB检索速度更快,表明HRB具有一定的使用价值。