高维数据空间索引方法的研究

讨论了高维数据空间索引的基本结构、建树算法,重,最对几种有代表性的索引方法,如R—Tree,X-Tree,M—tree,VP-tree在重叠、插入原则、分裂原则、再插入等方面进行了比较研究。该文中主要介绍了一些索引结构的特点和一些具有代表性的索引结构。     

高维数据空间索引方法的研究

讨论了高维数据空间索引的基本结构、建树算法,重点对几种有代表性的索引方法,如R-Tree,X-Tree,M-tree,VP-tree在重叠、插入原则、分裂原则、再插入等方面进行了比较研究。该文中主要介绍了一些索引结构的特点和一些具有代表性的索引结构。     

ALERT:基于Radix Tree的工作负载自适应学习型索引

学习型索引通过学习数据分布可以准确地预测数据存取的位置,在保持高效稳定的查询下,显著降低索引的内存占用.现有的学习型索引主要针对只读查询进行优化,而对插入和更新支持不足.针对上述挑战,设计了一种基于Radix Tree的工作负载自适应学习型索引ALERT. ALERT使用Radix Tree来管理不定长的分段,段内采用具有最大误差界的线性插值模型进行预测.同时,ALERT使用一种高效的插入缓冲来降低数据插入更新的代价.针对点查询和范围查询提出两种自适应重组优化方法,通过对工作负载进行感知,动态地调整插入缓冲的组织结构.经实验验证,ALERT与业界流行的学习型索引相比,构建时间平均降低了81%,内存占用平均降低了75%,在保持了优秀读性能的同时,使插入延迟平均降低了50%;此外, ALERT使用自适应重组优化能有效感知查询工作负载特征,与不使用自适应重组优化相比,查询延迟平均降低了15%.     

ZFT索引：基于分段线性回归的学习型多维索引

传统索引方式一般是一种通用的数据结构,不特别针对数据分布和特征设计或优化其索引方式,随着数据空间维度或数据量的增加,可能会导致存储消耗大且查询效率急剧下降。针对这些问题提出ZFT索引(Z-order Fiting-tree Index),它主要分为离线和在线两个部分。离线构造部分使用Z-order曲线将多维空间中的数据点映射到一维空间中,构建线性回归模型学习映射后数据的分布与特征;在线部分完成点查询和范围查询。实验结果表明,ZFT索引的空间效率和查询效率明显优于传统的R树以及UB树,并且在范围查询和模型训练速度上都优于ZM索引。     

基于γ划分策略的高维数据索引结构的研究

提出了一种压缩金字塔树,将d维数据空间划分为2d个金字塔,由于在低维空间中无效的信息在高维数据空间中往往无效,采用γ划分策略对低维空间中的数据进行压缩,减小索引结构,克服了金字塔技术的缺点。给出了压缩金字塔树的构造方法以及基于压缩金字塔树的查询算法。实验证明,压缩金字塔树是一种有效的空间划分策略,在高维稀疏空间有良好的性能。     

智能数据库学习型索引研究综述

建立高效的索引结构是提升数据库存取性能的关键技术之一.在数据呈爆发式增长、海量聚集、高维复杂的大数据环境下,传统索引结构（例如B+树）处理海量数据时面临空间代价高、查询效率低、存取开销大等难题.学习型索引技术通过对底层数据分布、查询负载等特征进行建模和学习,有效的提升了索引性能,并减少了访存空间开销.本文从学习型索引技术的基础模型入手,对RMI基础模型实现原理、构造和查询过程进行了分析,并总结了基础模型的优点和存在的问题;以此为基础,按照索引结构特点对学习型索引技术进行分类,从索引创建方式和更新策略两方面对学习型索引技术进行了系统梳理,并对比分析了典型学习型索引技术的优点及不足之处.另外,本文总结了学习型索引技术的扩展研究.最后,对学习型索引的未来研究方向进行了展望.     

基于可扩展LSH的高维动态数据索引

提出了一种可扩展的局部敏感哈希索引(SLSH),以解决高维动态数据索引中,由于数据集大小及分布特征无法确定而导致索引效率降低的问题.SLSH架构于E2LSH之上,继承了其对高维数据索引速度快,并可直接对欧式空间上的数据点进行索引的特点.为了使得哈希索引具有动态的相似性区分能力,SLSH修改了E2LSH的哈希族,通过哈希桶容量约束自适应调节哈希参数.因此对于分布密度动态变化的数据空间,SLSH也能够给出鲁棒的划分.     

高维数据分析中的降维研究

在处理和分析高维数据时通常会碰到维数灾难和传统的低维数据处理方法存在本质困难的问题,通过对各种处理高维数据的方法、技术进行比较和分析高维数据的统计特性后发现,采用降维处理是处理高维数据时的最好的选择。要实现降维的研究,应该从高维数据四方面的特征来展开。     

基于维度分组降维的高维数据近似k近邻查询

针对现有的高维空间近似k近邻查询算法在数据降维时不考虑维度间关联关系的问题, 首次提出了基于维度间关联规则进行维度分组降维的方法.该方法通过将相关联维度分成一组进行降维来减少数据信息的损失, 同时针对Hash降维后产生的数据偏移问题, 设置了符号位并基于符号位的特性对结果进行精炼; 为提高维度间关联规则挖掘的效率, 提出了一种新的基于UFP-tree的频繁项集挖掘算法.通过将数据映射成二进制编码来进行查询, 有效地提高了近似k近邻查询效率, 同时基于信息熵筛选编码函数, 提高了编码质量; 在查询结果精炼的过程, 基于信息熵对候选集数据的编码位进行权重的动态设定, 通过比较动态加权汉明距离和符号位碰撞次数返回最终近似k近邻结果.理论和实验研究表明, 所提方法能够较好地处理高维空间中近似k近邻查询问题.     

CKDB-Tree:一种有效的高维动态索引结构

在高维数据空间中提出了一种新的索引结构:CKDB-Tree(Compact KDB-Tree),该索引结构采用一种新的分裂策略,在进行分裂时,引入插入安全点和删除安全点的概念,不仅考虑到将来的数据,而且对已经进行索引的数据也进行考虑;给出了CK-DB-Tree的定义以及节点结构的特点,针对CKDB-Tree,给出了相应的插入、查找、删除操作的算法;对该索引结构的存储性能进行定量分析和推理;最后经实验证明,CKDB-Tree是高维空间中一种有效的动态索引结构。     

机器学习化数据库系统研究综述

数据库系统经过近50年的发展,虽然已经普遍商用,但随着大数据时代的到来,数据库系统在2个方面面临挑战.首先数据量持续增大期望单个查询任务具有更快的处理速度;其次查询负载的快速变化及其多样性使得基于DBA经验的数据库配置和查询优化偏好不能实时地调整为最佳运行时状态.而数据库系统的性能优化进入瓶颈期,优化空间收窄,进一步优化只能依托新的硬件加速器来实现,传统的数据库系统不能够有效利用现代的硬件加速器;数据库系统具有成百个可调参数,面对工作负载频繁变化,大量繁琐的参数配置已经超出DBA的能力,这使得数据库系统面对快速而又多样性的变化缺乏实时响应能力.当下机器学习技术恰好同时符合这2个条件：应用现代加速器以及从众多参数调节经验中学习.机器学习化数据库系统将机器学习技术引入到数据库系统设计中.一方面将顺序扫描转化为计算模型,从而能够利用现代硬件加速平台;另一方面将DBA的经验转化为预测模型,从而使得数据库系统更加智能地动态适应工作负载的快速多样性变化.将对机器学习化数据库系统当前的研究工作进行总结与归纳,主要包括存储管理、查询优化的机器学习化研究以及自动化的数据库管理系统.在对已有技术分析的基础上,指出了机器学习化数据库系统的未来研究方向及可能面临的问题与挑战.     

基于Hilbert曲线的高维k-最近对查询算法

利用Hilbert曲线的数据聚类特性,将高维空间中的点映射到线性空间中,给出相应的降维方法,提出基于Hilbert曲线的高维k-最近对查询算法,并证实了其正确性。算法能够删减点集中大量的点以优化扫描过程,减少运行时间,实验结果表明该算法优于连续扫描算法。     

N维Hilbert编码的计算

针对高维Hilbert曲线的复杂性问题,给出了一种N维Hilbert码计算方法.其基本思想是面向一个称为基因的静态演化规则表,根据基因信息进行相应的坐标变换,编解码始终依照Hilbert单元的映射特征进行映射转换;在逐层编解码过程中,把不断变化的映射形态转成固定的Hilbert单元映射方式,同时采用二进制位操作进行计算,从而实现高效的N维Hilbert映射转换.     

DRAMA: 更新分布感知的学习型索引

学习型索引因其低内存占用和高查询性能的特点, 正辅助或逐步取代传统的索引结构. 然而, 数据更新导致的在线重新训练使其无法适应数据频繁更新的场景. 为了在不过多消耗内存的前提下尽量避免由于数据频繁更新导致的索引重构, 提出了一种自适应的感知更新分布学习型索引结构DRAMA. 使用类LSM-Tree的延迟学习方式主动学习数据更新的分布特征; 利用近似拟合技术快速建立更新分布模型; 采用模型合并策略代替频繁的重训练过程; 采用一种混合压缩技术降低索引中模型参数的内存占用率. 在真实和合成的数据集上构建了索引并进行验证. 结果表明, 相比于传统索引和最先进的学习型索引, 该索引可以在不额外消耗过多内存的情况下, 有效降低数据更新环境下的查询延迟.     

高维数据中鲁棒激活函数的极端学习机及线性降维

极端学习机(extreme learning machine, ELM)训练速度快、分类率高,已经广泛应用于人脸识别等实际问题中,并取得了较好的效果.但实际问题中的数据往往维数较高,且经常带有噪声及离群点,降低了ELM算法的分类率.这主要是由于：1)输入样本维数过高;2)激活函数选取不当.以上两点使激活函数的输出值趋于零,最终降低了ELM算法的性能.针对第1个问题,提出一种鲁棒的线性降维方法(RAF-global embedding, RAF-GE)预处理高维数据,再通过ELM算法对数据进行分类;而对第2个问题,深入分析不同激活函数的性质,提出一种鲁棒激活函数(robust activation function, RAF),该激活函数可尽量避免激活函数的输出值趋于零,提升RAF-GE及ELM算法的性能.实验证实人脸识别方法的性能普遍优于使用其他激活函数的对比方法.     

基于符号图的高维时间序列检索

提出一种基于符号图的高维时间序列数据库索引方法,通过等分空间法对高维时间序列数据进行预处理,将其转化为高维符号序列,利用符号状态转换图对数据库进行索引。应用CMU Graphics lab发布的Motion Capture Database动作数据库进行实验,取得了较好的结果。     

A new algorithm for generating hilbert curves

A new algorithm is described which generates the co-ordinates of the tth point along a Hilbert curve, given the value of the parameter t. The algorithm is expressed in the concurrent programming language occam.