一种基于二层网格的移动对象B+树索引

在已有的基于空间分割的移动对象B+树索引基础上,提出一种分割空间的新方法,对空间进行二层网格分割,使空间分割很好地解决由移动对象在空间中分布不均造成的索引效率下降的问题。给出基于这种索引结构的Range查询和kNN查询算法。实验结果表明, 该索引结构的性能基本不受移动对象分布的影响。     

一种空间更优的数据流查询包含编码区间索引

给出一种基于CEI(containment-encoded intervals)的存储优化的数据流查询区间索引结构.在数据流处理中涉及到大量的数值型区间查询操作,构造一个基于主存并支持快速查询的区间索引结构十分必要.对CEI索引结构而言,虽然支持高速查询,但存储利用率较低.针对该问题,提出了索引结构ACEI(advanced-CEI).在CEI索引结构的基础上,通过数据结构调整和参数优化,ACEI可在保持原有查询速度的前提下将CEI的空间复杂度由O(R+N(W/L+N(log(L))降为O(sqrt(R(N)+N(sqrt(W)).实验结果表明,ACEI结构可以极大地提高索引结构的存储利用率,并且可以用于大端点值域下的区间索引.     

基于路网的移动对象索引机制研究

本文基于FNR-Tree的思想提出了一种新的索引算法FNR-Tree,该算法可以实现基于轨迹的查询,而这正是FNR-Tree索引结构所欠缺的,接着给出了FNR-Tree的数据结构和插入算法,查询算法,最后给出了两种索引结构的试验对比结果。     

MapReduce环境下支持精确查询的嵌套式数据索引技术

目前,针对嵌套式数据集上的高效查询处理已成为Web数据检索的一个重要任务.不同于传统信息检索,嵌套式数据集既要存储数据又要存储结构,导致了针对该类数据集查询的低效性,特别是对如何保证精确查询效率更是一个挑战.结合列存储结构和倒排索引技术,首先定义了表达嵌套式数据集中数据位置信息的唯一路径UPath,提出一种新的支持嵌套式数据集精确查询的索引结构——Uni Hash.在此基础上,给出了生成数据值的唯一路径UPath以及基于MapReduce框架建立Uni Hash索引的相关算法.通过将其与XPath检索进行对比,验证了Uni Hash索引结构的有效性.实验表明,将嵌套式数据集进行列式存储并建立Uni Hash索引,能够明显地提高精确查询的效率.     

CQRtree空间数据库索引结构及实现算法

空间数据库的索引是提高空间数据库存储效率、空间检索性能的关键技术.本文在R树索引的基础上提出了一种新的空间数据库索引结构CQRtree,给出了CQRtree的数据结构、插入、删除、查询实现算法以及性能分析与比较,最后指出了进一步的研究方向.     

一种快速的子序列匹配算法

提出一种在时间序列上快速匹配子序列的算法,该算法不同于FRM算法,而是采用VA-file这种索引结构,将数据点直接存储在索引上,并在该索引的基础上设计了一种进行范围查询的方法.实验采用了三种时间序列数据集,从不同的角度验证算法的有效性,结果表明该算法大大提高了查询性能.     

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

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

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

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

基于双层索引结构的起源图查询方法

为解决现有的起源图查询效率低和资源占用率高的问题,考虑起源信息和数据本身之间的关联关系以及起源信息内部结构特点,提出了一种基于双层索引结构的起源图查询方法。首先,面向起源图查询,提出了一种包括基于词典表全局索引和基于位图局部索引的双层索引结构,全局索引用于查询起源图所存储的服务器节点,局部索引用于对全局索引查询到的服务器节点细化查询;然后,基于双层索引结构,设计了一种起源图查询方法,针对6种选择索引和3种join链接索引实现了查询算法。实验结果表明,所提方法既提高了查询效率,又降低了内存资源的浪费。     

图数据隐私保护可达性查询算法研究

数据库领域越来越多的数据通过图的结构进行存储,随着图数据规模的快速增长和云计算的兴起,数据拥有者希望将数据外包给具有强大计算能力的服务商为其客户提供查询服务。为解决数据库中的可达性查询问题,提出一种隐私保护的可达性索引和查询方法。对原始的2-hop索引构建方法进行优化,设计maxISCover启发式方法,给出根据人工节点添加算法建立pp-2-hop索引的unifyIS和unifyLS算法,并在此基础上,给出基于密文域的优化可达性查询方法。实验结果表明,基于maxISCover优化方法和unifyIS算法建立的索引大小相比于基于原始2-hop索引的方法减小1个~2个数量级。     

一种新颖的对比子图索引算法

针对当前图索引算法存在的问题,提出一种基于对比子图索引框架,开发冗余感知机制,选择一个小型的具有明显区分力的索引特征集,改善索引性能。实验结果表明,该算法对不同的包容搜索载荷能达到近优化的修剪力,与传统图搜索方法相比,具有明显的索引性能优势。     

Efficient high-dimensional indexing by sorting principal component

The vector approximation file (VA-file) approach is an efficient high-dimensional indexing method for image retrieval in large database. Some extensions of VA-file have been proposed towards better query performance. However, all of these methods applying sequential scan need read the whole vector approximation file. In this paper, we present a new indexing structure based on vector approximation method, in which only a small part of approximation file need be accessed. First, principal component analysis is used to map multidimensional points to a 1D line. Then a B⁺-tree is built to index the approximate vector according to principal component. When performing k-nearest neighbor search, the partial distortion searching algorithm is used to reject the improper approximate vectors. Only a small set of approximate vectors need to be sequentially scanned during the search, which can reduce the CPU cost and I/O cost dramatically. Experiment results on large image databases show that the new approach provides a faster search speed than the other VA-file approaches.     

一种国内信息导航系统中的中文信息自动标引方法的设计与实现

中文信息的标引是国内信息导航系统实现的基础,汉语分词和语义提取是目前尚未解决的难题。本文比较了信息检索系统中目前主要使用的标引方法,根据国内信息导航系统处理对象的“中文”特征,提出了关键词标引与全文标引相结合的混合标引方法,并给出了具体的实现方法,较好地解决了查全、查准和标引空间的增长问题。文中最后也给出了中文信息标引处理后入库的数据的检索方法。     

基于Lucene的全文检索引擎研究与应用

快速有效地索引企业累积的大量的信息资源,是提供高质量检索服务的基础。Lucene是一个用Java写的全文索引引擎工具包,访问索引时间快,支持多用户访问,可以跨平台使用。文中研究了Lucene系统结构和数据流,分析了Lucene的索引文件格式,实现了一个基于Lucene文档检索的应用实例。     

Adaptive indexing for content-based search in P2P systems

One of the major challenges in Peer-to-Peer (P2P) file sharing systems is to support content-based search. Although there have been some proposals to address this challenge, they share the same weakness of using either servers or super-peers to keep global knowledge, which is required to identify importance of terms to avoid popular terms in query processing. As a result, they are not scalable and are prone to the bottleneck problem, which is caused by the high visiting load at the global knowledge maintainers. To that end, in this paper, we propose a novel adaptive indexing approach for content-based search in P2P systems, which can identify importance of terms without keeping global knowledge. Our method is based on an adaptive indexing structure that combines a Chord ring and a balanced tree. The tree is used to aggregate and classify terms adaptively, while the Chord ring is used to index terms of nodes in the tree. Specifically, at each node of the tree, the system classifies terms as either important or unimportant. Important terms, which can distinguish the node from its neighbor nodes, are indexed in the Chord ring. On the other hand, unimportant terms, which are either popular or rare terms, are aggregated to higher level nodes. Such classification enables the system to process queries on the fly without the need for global knowledge. Besides, compared to the methods that index terms separately, term aggregation reduces the indexing cost significantly. Taking advantage of the tree structure, we also develop an efficient search algorithm to tackle the bottleneck problem near the root. Finally, our extensive experiments on both benchmark and Wikipedia datasets validated the effectiveness and efficiency of the proposed method.     

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

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

The PN-Tree: A Parallel and Distributed Multidimensional Index

Multidimensional indexing is concerned with the indexing of multi-attributed records, where queries can be applied on some or all of the attributes. Indexing multi-attributed records is referred to by the term multidimensional indexing because each record is viewed as a point in a multidimensional space with a number of dimensions that is equal to the number of attributes. The values of the point coordinates along each dimension are equivalent to the values of the corresponding attributes. In this paper, the PN-tree, a new index structure for multidimensional spaces, is presented. This index structure is an efficient structure for indexing multidimensional points and is parallel by nature. Moreover, the proposed index structure does not lose its efficiency if it is serially processed or if it is processed using a small number of processors. The PN-tree can take advantage of as many processors as the dimensionality of the space. The PN-tree makes use of B⁺-trees that have been developed and tested over years in many DBMSs. The PN-tree is compared to the Hybrid tree that is known for its superiority among various index structures. Experimental results show that parallel processing of the PN-tree reduces significantly the number of disk accesses involved in the search operation. Even in its serial case, the PN-tree outperforms the Hybrid tree for large database sizes.     

基于参考集索引的高效序列相似性查找算法

序列数据在文本、Web访问日志文件、生物数据库中普遍存在,对其进行相似性查找是一种重要的获取和分析知识的手段.基于参考集索引技术是一类解决序列相似性查找的有效方法,主要思想是找到序列数据库中的少数序列作为参考集,通过参考集过滤掉数据库中与查询序列不相关的数据,从而高效地回答查询.在现有基于参考集索引技术的基础上,提出一种过滤能力更强的序列相似性查询算法IRI(improved reference indexing).首先,充分利用了先前的查询结果集来加速当前的查询,其次考虑了基于序列特征的上界和下界,使得应用参考集进行过滤的上下界更紧,过滤能力进一步加强.最后,为了避免候选集中费时的编辑距离计算,则只计算前缀序列间的编辑距离,从而进一步加速算法运行.实验采用真实的DNA序列和蛋白质序列数据,结果表明,算法IRI在查询性能上明显优于现有的基于参考集索引方法RI(reference indexing).     

基于P2P的隐含语义索引模型的研究

P2P作为一种新型的网络结构正受到越来越多的关注。目前在大多数P2P网络中的信息检索方法都是依据关键词匹配,通过查询请求与信息标识之间的简单匹配关系来获得查询结果。但是关键词匹配会产生很多用户不需要的结果。隐含语义索引是基于文本语义的检索模型。为提高系统的查准率,扩展在P2P下的查询方式,本文提出了在P2P网络中引入隐含语义索引模型进行信息检索,并模拟实现了一个基于P2P网络的隐含语义索引模型的试验平台。     

面向高维数据集的近邻顺序查询方法

对顺序索引方法进行了研究,提出一种基于向量近似的高维顺序索引结构,该结构顺序访问部分文件就能完成k近邻查询。在查询过程中依据投影值来终止查询过程,依据距离来排除不匹配的数据。为进一步降低数据访问率,采用椭圆体聚类算法对数据集进行划分。新索引结构支持以多个顺序访问过程完成k近邻查询,能够同时降低查询过程中的I/O开销和CPU开销。在大型高维图像特征库上的实验表明,新的高维索引结构的查询性能优于其他高维索引方法。