基于倒排表与B+树的联合索引技术

为提高XML文档的查询效率,提出一种基于倒排表与B+树的联合索引技术。DTD结构索引和内容索引采用倒排表作为索引单位,XML文档索引使用B+树作为索引基本组织。在DTD结构索引的结点编码中设置标识信息,便于确定需要查询的文档。通过建立DTD结构索引、XML文档索引和内容索引,实现混合型XML文档的查询。理论分析与实验结果表明,该技术具有较小的空间开销和较高的查询效率。     

一种基于XML文档关键字检索的结构索引

XML数据索引对其检索效率有较大的影响。在深入分析现有XMI、结构索引之后,结合XML文档特点,提出了一种基于关键字检索的结构索引--LSS(Level Structure Summary) . LSS采用了把具有相同标签路径的结点进行合并的策略,具有高效判断结点之间同构异构关系的能力。实现了LSS索引生成算法CSCAN,并在LSS索引的基础上设计了XML关键字检索算法LSSearch。该算法依据LSS索引,将各个关键字的原始倒排表集合分拆成不同类型的子集合,最后在所有子集合上进行查询。实验结果表明,LSS可以帮助减少XML文档中关键字倒排表的规模,提高检索效率。     

n-Gram/2L索引结构的存储与时间优化算法

对分词检索算法n-Gram/2L的索引结构作了改进,在第二级倒排表中加入对文章标识的索引,提出一种基于Zigzag的分词检索算法n-Gram/2LZ（n-Gram/2L on Zigzag join）。在对数据量较大的文章进行检索和索引时,该算法在保留原有算法特性的基础上进一步减少了索引冗余,降低了索引的存储量,同时对查询算法的优化降低了查询时的系统开销,并且减少索引中记录访问次数,提高了查询效率。     

面向XML文档检索的索引技术

XML文档的查询索引是当前研究的热点.该文探讨XML文档的索引技术,包括索引结构的设计等问题,给出了一个高效的XML索引方法,采用独特的编码方法,对XML文档及其遵循的DTD同时建立索引,有效支持内容和结构的双重检索;该方法结合了区间编码、倒排表和路径索引的思想,利用DTD结构信息来提高查询的效率.实验结果表明,本文提出的方法可以有效地降低建立XML数据索引的代价,能够缩短查询的响应时间.     

一种基于编码压缩的数据广播关键字索引方法

无线环境的特殊性导致传统的关键字检索方法不能很好地用于周期数据广播之中.倒排表是全文检索中广泛使用的一种索引技术,但倒排表索引和基于哈希的数据索引无法解决索引结构过大的问题.为此,在周期数据广播环境下,提出一种新型的关键字索引结构,对倒排表进行编码压缩,缩减索引结构来减少访问时间和调谐时间.同时,与编码压缩索引相结合,设计一种周期数据广播下的文档调度方法.在真实数据集上进行的实验结果表明,该方法可缩减索引结构的规模,降低访问延迟和能耗.     

全文索引的研究

在倒排表模型的基础上，从加快索引创建速度和改进索引动态结构两个方面着手，提出了并实现了一种高效的索引创建算法和相应的索引模型，经过测试，新系统的索引创建速度可以和数据复制速度相提并论，而在空间效率上，也得到了一定程序的提高。     

I-XISS：一种改进的XML文档索引结构

节点索引是XML索引中可支持正则路径表达式的最具代表性的一种，但是对于长的查询路径表达式，尤其是在中间结果很多的时候，节点索引的连接操作代价很高。对节点索引的索引结构进行了改进，通过减少中间结果的连接次数，使得查询时间与路径的长度无关，而只与路径的复杂度有关，并且提出了一种利用该索引结构输出查询结果的算法。     

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

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

一种XML数据库上谓词“Contain”的实现方法

路径表达式查询是XML数据查询处理的核心研究问题之一,研究者开展了大量的研究工作.但这些研究更多关注XML数据上路径表达式的匹配,忽略了谓词"包含".研究XML查询处理中谓词"包含"的查询处理方法.采用了两种方法,第一种是采用跳跃表的方法,在XML分枝模式匹配时动态地对结点数据进行读取和关键字匹配.第二种是为XML文档中的词语建立倒排索引,来实现关键字的匹配.并从分枝模式路径长度、查询关键的数量和"包含"谓词判断结点的类型,对两种方法进行了分析和比较.     

基于缓存的倒排索引机制研究

倒排索引创建效率和查询效率是全文检索技术的两个重要方面.针对传统倒排索引创建方法效率低下的问题,提出了基于缓存满再写临时文件和双缓冲区相结合的索引创建机制,充分利用内存和CPU资源以加快倒排索引的创建速度;提出了查询缓存机制,以提高倒排索引的查询效率.分析及实验结果表明,提出的索引创建机制能有效地提高索引创建速度,查询缓存机制能有效地加快查询速度,提高了全文检索系统的时间和空间效率.     

一种改进的XML压缩树索引技术

压缩树索引技术是XML数据压缩的热点问题之一,本文提出一种压缩树索引改进方法.针对压缩树在查询过程中不能很好的解决向上匹配与向下匹配的问题,改进方法引入正排索引和倒排索引.当查询到组一级时,利用正排索引可以快速的查找出以该组为父节点的子组.而选出符合值谓词的元素后,在进行向上匹配时利用倒排索引可找出该元素的父节点.新的索引方法在保留原压缩树索引优点的基础上,解决了压缩树索引在查询过程中匹配问题.     

LAF: a new XML encoding and indexing strategy for keyword‐based XML search

As a large number of corpuses are represented, stored and published in XML format, how to find useful information from XML databases has become an increasingly important issue. Keyword search enables web users to easily access XML data without the need to learn a structured query language or to study complex data schemas. Most existing indexing strategies for XML keyword search are based upon Dewey encoding. In this paper, we proposed a new encoding method called Level Order and Father (LAF) for XML documents. With LAF encoding, we devised a new index structure, called two‐layer LAF inverted index, which can greatly decrease the space complexity compared with Dewey encoding‐based inverted index. Furthermore, with two‐layer LAF inverted index, we proposed a new keyword query algorithm called Algorithm based on Binary Search (ABS) that can quickly find all Smallest Lowest Common Ancestor. We experimentally evaluate two‐layer LAF inverted index and ABS algorithm on four real XML data sets selected from Wikipedia. The experimental results prove the advantages of our index method and querying algorithm. The space consumed by two‐layer LAF index is less than half of that consumed by Dewey inverted index. Moreover, ABS is about one to two orders of magnitude faster than the classic Stack algorithm. Concurrency and Computation: Practice and Experience, 2012.© 2012 Wiley Periodicals, Inc.     

基于多哈希算法的大规模图像快速检索方法

哈希技术被视为最有潜力的相似性搜索方法,其可以用于大规模多媒体数据搜索场合。为了解决在大规模图像情况下,数据检索效率低下的问题,提出了一种基于分段哈希码的倒排索引树结构,该索引结构将哈希码进行分段处理,对每段哈希码维护一个倒排索引树结构,并结合高效的布隆过滤器构建哈希索引结构。为了进一步提高检索准确性,设计了一种准确的排序融合算法,对多个哈希算法的排序结果分别构建加权无向图,采用PageRank的思想对基于多个哈希算法的排序列表的融合技术进行了详细的说明。实验结果表明,基于分段哈希码的倒排索引树结构能极大地提升数据的检索速度。此外,相比于传统的单个哈希算法排序技术,基于多个哈希算法的排序列表融合技术的检索准确率优势显著。     

Universal indexes for highly repetitive document collections

Indexing highly repetitive collections has become a relevant problem with the emergence of large repositories of versioned documents, among other applications. These collections may reach huge sizes, but are formed mostly of documents that are near-copies of others. Traditional techniques for indexing these collections fail to properly exploit their regularities in order to reduce space.We introduce new techniques for compressing inverted indexes that exploit this near-copy regularity. They are based on run-length, Lempel–Ziv, or grammar compression of the differential inverted lists, instead of the usual practice of gap-encoding them. We show that, in this highly repetitive setting, our compression methods significantly reduce the space obtained with classical techniques, at the price of moderate slowdowns. Moreover, our best methods are universal, that is, they do not need to know the versioning structure of the collection, nor that a clear versioning structure even exists.We also introduce compressed self-indexes in the comparison. These are designed for general strings (not only natural language texts) and represent the text collection plus the index structure (not an inverted index) in integrated form. We show that these techniques can compress much further, using a small fraction of the space required by our new inverted indexes. Yet, they are orders of magnitude slower.     

基于Map/Reduce的外壳片段立方体并行计算方法

针对高维、维度分层的大数据集,提出一种基于Map/Reduce框架的并行外壳片段立方体构建算法。算法采用Map/Reduce框架,实现外壳片段立方体的并行构建与查询。构建算法在Map过程中,计算出各个数据分块所有可能的数据单元或层次维编码前缀;在Reduce过程中,聚合计算得到最终的外壳片段和度量索引表。实验证明,并行外壳片段立方体算法一方面结合了Map/Reduce框架的并行性和高扩展性,另一方面结合了外壳片段立方体的压缩策略和倒排索引机制,能够有效避免高维数据物化时数据量的爆炸式增长,提供快速构建和查询操作。     

Energy- and Latency-Efficient Processing of Full-Text Searches on a Wireless Broadcast Stream

In wireless mobile computing environments, broadcasting is an effective and scalable technique to disseminate information to a massive number of clients, wherein the energy usage and latency are considered major concerns. This paper presents an indexing scheme for the energy- and latency-efficient processing of full-text searches over the wireless broadcast data stream. Although a lot of access methods and index structures have been proposed in the past for full-text searches, all of them are targeted for data in disk storage, not wireless broadcast channels. For full-text searches on a wireless broadcast stream, we firstly introduce a naive, inverted list-style indexing method, where inverted lists are placed in front of the data on the wireless channel. In order to reduce the latency overhead, we propose a two-level indexing method which adds another level of index structure to the basic inverted list-style index. In addition, we propose a replication strategy of the index list and index tree to further improve the latency performance. We analyze the performance of the proposed indexing scheme with respect to the latency and energy usage measures, and show the optimality of index replication. The correctness of the analysis is demonstrated through simulation experiments, and the effectiveness of the proposed scheme is shown by implementing a real wireless information delivery system.     

On the selection of the access path in inverted database organization

The query in inverted file organization can be expressed in the form of a Boolean expression, that states the data selection criterion. In response to a query the system accesses inverted lists, merges them and then accesses those records in the secondary storage, that satisfy the search logic. Because the stored inverted lists are selected by taking into consideration the file organization as a whole, it is not always advantageous to use all the stored inverted lists. The remaining conditions will be examined from the records that fulfil the conditions, which are examined using inverted lists, In this paper we present an optimization algorithm for the selection of the address lists that are worth using.     

一种并行计算平台KD-60上的可实时更新文本搜索

实时性是影响搜索引擎性能的重要因素.针对这个因素,提出一种可实时更新的倒排索引结构并将其应用于国产万亿次高性能计算平台KD-60.该方案采用主、辅倒排索引和内容过滤索引相结合的方式,实现了搜索过程的实时性.同时,我们将其应用于高性能绿色计算平台KD-60,使之在一定的程度上实现了搜索的高效能.实验证明,基于KD-60平台的倒排索引结构有效的解决了搜索引擎的实时性问题,并可作为绿色计算的实际应用的一个典型实例.     

封闭立方体反转索引查询优化技术 *

处理用户复杂查询请求的速度是数据仓库关键性能之一。论述了在 QC算法产生的聚集表上建立反转索引和查询并还原出立方体上界的方法 ,查询算法包括位图查询算法和反转列表查询算法。最后进行了性能测试 ,结果表明这两种算法均能够提高查询的速度。     

基于Voronoi-R*的隐私保护路网k近邻查询方法

针对已有的保护位置隐私路网k近邻查询依赖可信匿名服务器造成的安全隐患,以及服务器端全局路网索引利用效率低的缺陷,提出基于路网局部索引机制的保护位置隐私路网近邻查询方法.查询客户端通过与LBS服务器的一轮通信获取局部路网信息,生成查询位置所在路段满足l-路段多样性的匿名查询序列,并将匿名查询序列提交LBS服务器,从而避免保护位置隐私查询对可信第三方服务器的依赖.在LBS服务器端,提出基于路网基本单元划分的分段式近邻查询处理策略,对频繁查询请求路网基本单元,构建基于路网泰森多边形和R^*树的局部Vor-R^*索引结构,实现基于索引的快速查找.对非频繁请求路网基本单元,采用常规路网扩张查询处理.有效降低索引存储规模和基于全局索引进行无差异近邻查询的访问代价,在保证查询结果正确的同时,提高了LBS服务器端k近邻查询处理效率.理论分析和实验结果表明,所提方法在兼顾查询准确性的同时,有效地提高了查询处理效率.