空间索引并行批量加载算法研究

空间索引是提高空间数据库查询性能的关键技术。空间数据具有海量、空间目标不规则、结构和关系复杂等特征,要动态地维护空间索引结构,传统R树的构建方法插入代价非常高。在深入分析空间索引批量加载算法基础上,面向多核处理器的新型硬件架构,基于OpenMP并行编程模型,实现Hilbert R树索引的并行批量加载算法。实验结果表明,相对于串行经典算法,该算法的并行效率接近50%,通过查询实验验证,并行加载算法保持了串行算法生成索引的优良查询性能。     

SCBT-index:基于谱编码的子图索引算法

随着图模型规模的扩大,单机算法难以适应大规模数据集下的子图查询.而现有的分布式算法基于无索引的简单遍历,join过程容易出现内存溢出,而且查询图分布异常时易出现负载不均衡.提出了一种基于谱编码的二叉索引树（SCBT-index）,首先对数据图中的顶点谱编码,根据编码信息构建二叉索引树.然后对查询图使用最小查询计划进行分解,最后join过程使用3个剪枝策略：基于拓扑结构的预剪枝、序列化join和基于分布式下的join优化.实验结果表明,SCBT-index在图集下的综合性能优于现有主流算法,单图下的查询时间为现有算法的1/2到1/4.     

基于频繁闭图的图包含查询算法

 交通网络可利用图数据进行描述与分析,常用的方法包括挖掘、查询、分类等.提高大规模图集上查询算法效率的问题是当前图数据分析领域中一个重要的研究方向.给定图集,图包含查询返回图集中所有查询图的子图.本文提出一种基于频繁闭图的包含查询算法.算法首先通过选择比消除频繁闭图之间的冗余,然后将具有强选择性的频繁闭图通过树的结构组织起来建立索引,并在此索引基础上实现图包含查询.在文章的最后,给出了理论与实验的分析结果.结果表明,该算法不但能高效的进行索引筛选,而且能显著的减小候选集尺寸,进而大大的降低了查询图与索引模式之间以及与候选集之间的子图同构测试次数,提高了查询效率.     

基于质心片的不确定高维索引研究

 提出一种基于质心片的(CU-Tree)不确定高维索引结构.对于高维空间中的不确定数据对象,首先通过k平均聚类算法将其聚成若干类,然后分别计算每个不确定超球进行质心"切片",并对其进行复合编码得到对应的统一索引键值,并且用B+树建立索引.这样,高维空间的概率查询就转变成对一维空间的启发式的范围查询及求精运算.实验证明该方法能更有效地缩小搜索空间,减少积分计算的代价.实验都表明,CU-Tree索引在查询效率方面要明显优于其它的索引方法,尤其适合海量高维不确定数据的查询.     

HR-Tree——一种基于P2P端点的XML树型索引方法

提出一种应用在P2P平台上的XML索引方法HR-Tree。HR-Tree索引方法首先利用区域划分的方法对于XML数据进行处理,再使用散列的方法把数据进行分类,最后利用HR-Tree树建立索引。和XR-Tree等索引方法相比,HR-Tree查询更为灵活,更能满足P2P各端点查询的要求。实验表明,该算法在XML数据的查询处理上是一个有效的方法。     

分布式空间数据索引机制研究

在分析各种空间数据索引的基础上,研究利用分布式并行技术建立网络环境下海量空间数据的大规模索引机制的关键技术。对经典的R-树进行了改进,基于R-和散列hash表,提出了一种分布式环境下面向海量空间数据的分布式索引树结构DR-H,此索引树结构充分利用了R-树的范围查询和散列hash表的高效单key查询。经模拟实验结果表明,该分布式索引机制结构能够有效提高分布式网络环境下海量空间数据的检索性能。     

MapReduce框架下的优化高维索引与KNN查询

针对大规模高维数据近似查询效率低下的问题,利用MapReduce编程模型在大规模集群上的数据与任务的并行计算与处理优势,提出MapReduce框架下大规模高维数据索引及KNN查询方法（iPBM）,重点突破MapReduce数据块（block）的优化划分与各数据块对计算的共同贡献两大难题,利用两阶段数据划分策略并依据相关性与并行性原则将数据均匀分配到各数据块中,设计分布式的双层空间索引结构与并行KNN查询算法,检索时利用全局索引、局部索引与二维位码索引实现三层数据过滤,大幅缩小搜索范围并降低高维向量计算代价,实验表明iPBM对大规模高维数据的近似查询具有准确性、高效性和扩展性.     

基于索引框架的XPath求值算法

本文为了解决用倒排表索引XML节点而导致的查询效率低下,以及现有结构连接算法对值约束考虑不够的问题,本文给出运用原生XML数据库索引框架的结构索引合并PC子路径,运用XML值索引及全文索引处理比较运算符,产生查询优化树。实验表明,本文提出的算法极大的减少了查询树节点的个数,缩短了CPU时间开销和磁盘I/O开销。     

大规模数据集的分布式索引机制研究

对大规模结构化半结构化数据集分布式存储环境下索引结构的建立进行了研究,提出了一种基于聚簇索引与分布式B 树的混合索引结构.该结构对数据集的输入,存储及查询等操作进行了定义,并分析了索引服务器与客户端的通信模型建立.由于对记录的主关键字与其他属性进行了不同处理,在各种记录检索情况下具有良好的性能.     

XML索引技术在Web服务发现中的应用

讨论语义Web下服务的发现,借助本体对信息源进行标注,使用本体概念来描述服务参数。利用本体概念之间的包含关系来实现服务匹配,而本体概念关系则依据其在相关本体概念树中的位置来确定。这种结构化数据的存储与搜索和XML数据有共同点,因此尝试把在XML数据查询中应用非常普遍的索引技术（B’-树索引）应用到的语义Web服务发现过程中,讨论了索引的建立方法并给出具体的检索算法,最后通过实验表明在大规模的服务匹配过程中应用索引可以提高搜索效率。