基于B+树的数据索引存储

针对传统索引算法在数字数据索引应用中存在的索引建立时间开销较大问题, 提出一种将B+树理论和算法应用于索引的设计方案. 在对B+树索引基础上, 建立了索引存储模型, 结合位图存储方式将B+树节点存储在存储介质上, 实现索引存储. 实验结果表明, 使用B+树, 可按路径读取, 节省了建立索引时间, 同时提高了B+树的稳定性, 在B+树节点存储的情况下访问键值信息, 索引速度得到较大提升.     

适合于配电网GIS系统的空间索引研究

探讨了一种空间数据的组织方式,以及在这种方式下为了加快检索速度而建立的空间索引的方法.针对配电网络的实际应用情况,分析对比了BSP树、KDB树、R 树、网格划分等方法针对二维空间数据索引的效率,及其优缺点.详细讨论了适合于配电网络的网格索引机制的建立方法.     

基于混合索引树的空间文本匹配算法

针对空间文本对象流和订阅流的匹配,采用一种混合索引树来组织数据对象,包括多叉树空间索引、谓词索引和倒排文件三个部分,其中多叉树空间索引用于空间区域管理,谓词索引和倒排文件用于订阅谓词管理.在此基础上,提出了谓词索引建立算法、空间文本对象与倒排项匹配算法和混合索引树检索算法.与基于空间网格加倒排文件的检索方法进行了对比实验,结果表明:所提出的算法提高了用户的检索效率,并验证了其有效性.     

基于B+树索引的动态社会网络差分隐私保护

针对当前社会网络的动态更新速度越来越快,而社会网络中差分隐私保护方法迭代速度慢的问题,提出一种基于B+树索引的动态社会网络差分隐私保护方法.使用B+树索引社会网络图的边,根据差分隐私并行性组合的特点,对B+树的索引数据划分,为数据分配不同的ε并添加拉普拉斯噪声,实现数据隐私后的整体高效用性和局部强保护性;在迭代时利用B+树的高效索引对欲更新的信息快速定位,实现动态社会网络差分隐私保护的快速迭代.实验表明,B+树索引有效提高了动态社会网络差分隐私保护的迭代速度,同时差分隐私的并行性提高了数据的效用性.     

基于P2P分布式多维平衡树的数据索引结构的复杂查询

对等网络(P2P)中,如何高效的支持对多维数据的复杂查询是一个重要的问题.在现有的P2P系统中对于这样的查询经常受到查询类型的约束,或者需要很高的维护开销.将跳跃图技术和平街树索引结合在一起,并借助小波技术辅助平衡负载,设计了一种简单有效的索引结构DMBTI(分布式多维平衡树索引),研究了分布式多维平衡树的构造、导航算法、平衡负载过程和维护方法.进行了性能测试实验,结果证明了这种结构的优越性.     

基于改进R*树的移动GIS多尺度渐进传输与表示

针对传统单一尺度空间数据在低速无线网络环境中难以由移动GIS下载与表示的问题,在研究矢量数据多尺度表示与R*树空间索引的基础上,设计并实现了改进的多尺度R*树空间索引算法.该算法使得R*树中非叶子结点能够关联合适尺度的空间对象实体,保证海量的矢量数据在服务器端得到了有效的多尺度组织.在该算法的基础上,借助于移动GIS端所设计的缓冲式多尺度空间数据存储与管理,以及基于请求/应答模型的GML流式数据传输,设计并实现了面向移动GIS的矢量数据多尺度渐进传输模型,从而使得移动GIS能够以较高的效率下载和表示各种尺度的空间数据.通过真实的土地利用现状空间数据实验,验证了该方法在无线网络情况下能够有效地提高移动GIS的数据传输效率.     

路网中基于RQOP树的移动对象索引技术研究

基于位置的信息服务需要高效的索引方法来管理移动对象.针对PMR QUAD树索引路网空间时不平衡、部分路段重复存储且索引结构可调整性差的问题,用RQOP树对路网空间按照路段的空间分布进行划分,使树的高度尽可能低,改进基于路网的动态组合索引结构.对照实验表明,基于RQOP树的索引结构提高了查询效率.     

基于元素区间编码的GML数据索引方法

根据GML数据查询的需要,在分析XML文档编码和空间索引技术的基础上,提出一种基于扩展的元素区间编码的GML索引方法.首先通过扩展的区间编码方法对GML文档中的元素、属性、文本、几何体等要素进行编码;其次依据元素编码算法并将非空间节点、空间节点、元素节点从GML文档树中分离,产生元素编码序列;在此基础上根据节点类型的不同对属性和文本节点建立B+树索引以实现值查询,对几何体节点建立R树索引以实现空间数据的分析操作,并在查询处理时通过查询优化算法避免不必要的节点的遍历,进一步提高查询效率.实验结果表明,基于元素区间编码的GML数据索引方法是可行的、高效的.     

基于B~+树的索引字段加密

针对索引字段加密难的问题,提出一种基于B~+树的索引字段加密处理技术.该技术采用DBMS内部加密机制,选取在页/段映射到块时使用加密组件对索引字段进行加密,它能够使加密后的索引仍然保持有序,不会失去索引的快速查询功能.为了进一步保证索引字段本身的安全性,对索引按结点实施加密.实验中,模拟Postgresql中B~+树的构造方法,研究基于B~+树的加密索引字段的查询性能,并在页结点数和B~+树深度参数变化时,对分结点加密的查询性能进行测试.研究结果表明:基于B~+树的索引字段加密的查询速度虽然比明文查询速度下降20%左右,但采用分结点加密方式能够有效地减少解密代价,避免索引字段加密对查询性能产生较大影响.     

面向交易实时数据库内存数据的组织方法

研究面向大规模电子交易实时数据库中密集内存数据的高效组织方法.采用线性存储池实现内存数据的物理存储组织,并根据交易事务更新内存数据的update-in-place和append-only特点,采用T树索引实现元组固定数据的逻辑组织,采用缠绕的双向链式索引实现动态数据的逻辑组织.简化了物理空间的分配和调整算法,提高了数据更新和索引重构的效率,降低了内存数据查询访问的时间复杂度.结果表明,基于T-树索引和链式索引的数据查询算法的时间复杂度分别控制在O(lnN)和O(ln(N 1)-1),满足大规模电子交易的需要.     

图形处理器上CSB~+-树索引的并行构建算法

为提高缓存敏感CSB+-树索引的操作效率,在图形处理器(GPU)上研究CSB+-树的并行构建和查询性能.通过分析索引树内部节点的每一键与对应叶子节点的映射关系,提出了一种一次性并行构建CSB+-树所有内部节点键值的无锁并行算法,以最大并行度来快速构建索引树.该算法通过设计GPU平台上支持CSB+-树的索引数据任意伸缩的动态数组来解决GPU上不能动态分配显存空间的问题,通过在索引内部节点的边界增加填充位来减少线程块的线程分支数,从而提高CSB+-树的查询效率.实验结果表明,文中所提算法的运行时间比基于单个节点和基于树层的并行算法分别提高了31.0和1.4倍.     

基于数据广播的空间关键字查询处理

为了解决无线广播环境下空间关键字查询的问题,研究广播环境下空间关键字k近邻查询处理(BkSKQ),设计了一种结合kd树、倒排位图和(1,m)索引机制的空间关键字索引(ISKW)结构,以有效地组织对象的关键字信息、位置信息以及索引信息.该索引结构为客户的查询处理提供有效的指导,使得他们尽可能只下载查询处理所必须的数据信息.在ISKW索引结构的基础上,提出了BkSKQ查询处理算法.最后,通过模拟实验验证了提出的索引结构和算法的性能,实验结果表明所提出方法在访问时间和调谐时间上明显优于基于IR树的方法(BIRM).     

基于改进NSGA-Ⅲ的文本空间树聚类算法

构建倒排文本空间索引树(IR)分裂聚类多目标模型,对非支配排序遗传算法(NSGA-Ⅲ)的求解过程进行改进,提出一种基于先验初始种群策略的非支配排序遗传算法(PIPS-NSGA-Ⅲ),使其更适应于倒排文本空间对象分裂聚类问题的求解.通过PIPS-NSGA-Ⅲ算法寻求对象最小包围矩形(MBR)之间的重叠与覆盖面积、对象群间平均距离以及语义相似度等目标的最优前端解.通过对比PIPS-NSGA-Ⅲ,NSGA-Ⅱ,NSGA-Ⅲ和SPEA-Ⅱ进化多目标算法,从对象分类时间、效率、查询时间和准确度等多个方面来评估算法的优劣.实验结果表明:PIPS-NSGA-Ⅲ算法对文本空间对象聚类分裂具有较高的效率;相对于简化传统R树(STR树)与R树空间索引结构,基于改进NSGA-Ⅲ文本空间索引的平均查询时间减少24.8%,平均准确度提高3.75%.     

空间索引的新机制——G树

研制空间数据库管理系统,提出了一种Ｇ树的空间模型和动态格网的操作算法,设计实现了基于页面的新的空间索引机制,有效的解决了Ｎ维空间数据的索引问题。     

一种基于频繁子树的数据库索引方法

为解决带标号的有根无序树的数据库的索引问题,提出一种新的索引方法,首先挖掘频繁子树,并从中挑选出有判别力的子树作为索引属性,然后将索引属性集合中的子树转换成序列,并将索引组织成前缀树的形式.给出了在此类索引树中进行搜索的算法,并用Apriori剪枝和最大的有判别力的子树来减小搜索空间.实验结果表明:与其他基于路径的索引方法相比,这种基于频繁子树的数据库索引在索引大小和查询代价两方面都有较好的优越性.     

基于双树双索引结构的移动查询方法

为实现对有限范围内海量移动对象的有效索引,构建通用的移动查询解决方案,针对移动对象在道路网格中的运动特点,提出了预测实时运动速度的速度积累模型和预测未来聚集位置的基于双树双索引结构的移动对象查询方法.双树双索引结构利用网格划分思想构建空间分割树,实现对现有GG TPR-tree查询结构的拓展,并结合GG TPR-tree索引及建立于内存中的Hash索引以满足各种类型的移动查询请求.仿真实验表明,在回答受限范围内海量移动对象的确定性查询和统计性查询时,与传统方法相比,双树双索引结构在查询结果准确率方面有明显的改善.     

一种基于R树空间索引技术的GIS数据索引方法

地理信息数据库的查询效率作为GIS系统效率的关键,传统的查询和索引技术不能有效地实现地理信息数据库的高速查找和信息提取.提出了GIS中高效信息查询和提取的一种优化方法——一种基于R 树的空间索引技术的方法,介绍通过该方法建立记录地图信息的shape文件对应的索引文件的基本思路和方法并提出了基于此方法的GIS最邻近查询算法. 通过实验表明,该方法能有效提高GIS系统的响应速度和数据提取效率.     

QGrid:一种空间移动对象并行索引结构

为提高空间移动对象数据更新效率和查询准确率,提出了一种空间移动对象并行索引结构.利用主索引和辅助索引支持对空间对象进行基于范围的查询和基于对象标识的查询,还通过查询索引将更新操作和可能受其影响的查询操作相连接,在满足并行操作时间片语义的同时,避免了传统方法进行范围查询时对查询范围内相关对象及相关索引结构全部进行锁定的需求.实验结果表明:高负载环境下,该索引结构不但能保证查询准确率,其处理能力也明显优于传统索引结构.该索引通过提高系统并行度,使同一范围内的更新和查询操作可以并行执行,提升了系统整体运行效率.     

一种高效的空间索引结构

为高效地处理空间数据，必须对数据库建立索引机制以快速存取数据。然而，由于空间数据的特殊性使得传统索引方法不能很好地适应空间数据的存取。介绍了一种目前较流行的索引结构－R树及其主要算法。在所研究的空间分析数据库系统SADBS中实现了R树索引。     

基于大页内存的学习索引内存分配策略

大数据时代,数据信息的不断膨胀给数据的快速存取带来了巨大挑战.因此,设计一种高效的索引结构具有重要意义. ALEX (updatable adaptive learned index)是一种利用机器学习模型代替传统B-树索引结构的学习索引,具有较好的时间、空间性能,但存在频繁的缺页中断问题.为解决此问题,进一步提升ALEX性能,在ALEX基础上提出了一种基于大页内存的内存预分配策略,较好地降低了内存缺页中断率,提升了ALEX性能.在内存分配阶段,采用预分配策略;在内存回收阶段,则采用延迟释放策略.在Longitudes数据集上的实验表明,该策略具有良好的效果.