一种基于混合索引的最近邻查找方法.pdf
《一种基于混合索引的最近邻查找方法.pdf》由会员分享,可在线阅读,更多相关《一种基于混合索引的最近邻查找方法.pdf(6页珍藏版)》请在咨信网上搜索。
1、数据库系统中,一般使用索引技术来提升数据的存储性能。数据库系统通常把磁盘作为持久性的存储设备。然而使用磁盘会带来较高的访问延迟,磁盘输入和输出次数的降低成为提高数据A Nearest Neighbor Search Method Basedon Hybrid IndexPENG Yong-xin1,LUO Ying2(1.School of Mathematics and Computer Applications/Engineering Research Center of QinlingHealth Welfare Big Data,Universities of Shaanxi Prov
2、ince,Shangluo University,Shangluo726000,Shaanxi;2.China Weapons Industry Information Center,Haidian100089,Beijing)Abstract:Aiming at the problem that the learned KD tree model has low accuracy in nearest neighborlookup in some scenarios,a hybrid index structure based on learned index model and tradi
3、tional KD treeis proposed.The structure simultaneously inputs the data to be found into the trained learned KD treemodel and several candidate k neighbors in the KD tree,so as to combine the advantages of the learnedindex model in the search efficiency and the traditional index method in the search
4、accuracy.Theexperimental results show that the hybrid index of learned KD tree and tree structure KD tree based onlearned index model combines the advantages of the two in nearest neighbor lookup,realizes the balanceof search efficiency and search accuracy,and meets the search needs under various co
5、nditions.Key words:learned index;nearest neighbor search;hybrid index一种基于混合索引的最近邻查找方法彭永鑫1,罗英2?摘 要:针对某些场景下可学习KD树模型在最近邻查找中准确率较低的问题,提出了一种基于可学习索引模型和传统KD树的混合索引结构。该结构将待查找数据同时输入已经训练好的可学习KD树模型和KD树中得到若干个候选的k近邻点,从而将可学习索引模型在查找效率和传统索引方法在查找准确率上的优点相结合。试验结果证明,使用基于可学习索引模型的可学习KD树和树形结构KD树的混合索引,综合了两者在最近邻查找中的优点,实现了查找效率
6、和查找精度的平衡,满足了多种条件下的查找需求。关键词:可学习索引;最近邻查找;混合索引中图分类号:TP391.41文献标识码:文章编号:1674-0033(2023)04-0031-05引用格式:彭永鑫,罗英.一种基于混合索引的最近邻查找方法J.商洛学院学报,2023,37(4):31-35.(1.商洛学院 数学与计算机应用学院/秦岭康养大数据陕西省高校工程研究中心,陕西商洛 726000;2.中国兵器工业信息中心,北京海淀 100089)收稿日期:2023-04-18基金项目:商洛学院科研基金项目(21SKY004)作者简介:彭永鑫,男,陕西山阳人,硕士,讲师doi:10.13440/j.s
7、lxy.1674-0033.2023.04.005第 37 卷 第 4 期23 年 8 月商洛学院学报 Vol37 4Aug.23库性能的重要指标。如何高效地在磁盘中进行数据检索成为数据库系统中被人们所关注的问题。传统方法通常从改进查找过程及更快命中数据两个角度来提高范围查找效率,但只能在一定程度上降低维度和数据量的增加对查找效率所带来的影响,所能取得的效果有限。作为树型索引结构的代表,KD1树由于具有准确度高、对异常数据不敏感和查找准确等优点广泛应用在最近邻查找之中。然而,在大数据环境下,传统的索引都面临诸如空间占用率高、查找过程需要多次间接搜索等问题,影响到了查询性能。尤其是树形结构,随着
8、实际应用中数据维度的不断升高,在进行精确查找的过程中,会产生“维度灾难”2,使得搜索变为线型扫描。找到一种既能提高索引效率,同时又能满足一定索引精度的算法,成为新的研究方向。随着人工智能的发展,研究人员开始使用机器学习技术来提高数据库的索引性能。关于可学习索引(learned index)3的工作为索引结构的研究开辟了新的方向。树型索引结构例如 B 树,可以被认为是一棵把键映射到索引条目排序数组中相应位置的回归树。这项工作开启了用基于数据分布构建的学习模型替换现有索引树可能性的研究,提出的 RM-Index3在搜索性能和索引空间开销方面都优于传统的 B 树。在可学习索引中,可以把索引本身当作一
9、个机器学习模型。无论是 B 树还是可学习索引模型,输入值都为一个待查找的键。不同之处在于 B 树通过搜索查找,会得到这个键所在记录的位置。而可学习索引模型在待查找的键输入后,经过神经网络模型的一系列运算,会输出一个包含最大误差和最小误差的区域,并能在这个误差区域内使用二分法找到记录的确定位置。传统的索引结构往往没有考虑数据的分布,而可学习索引利用机器学习进行模型的构建,在训练的过程中能够通过不同层级的神经网络得到数据的分布信息。Peng 等4研究发现,相对于传统的 KD 树,使用基于可学习索引的可学习 KD 树模型可以有效地提高最近邻查找的查找效率。本文在可学习的 KD 树4的基础上,提出一种
10、基于混合索引的最近邻查找方案。混合索引将传统 KD 树在查找精度和可学习 KD 树在查找效率上的优势相结合,能够根据对查找效率和查找精度的不同要求,更加灵活地解决空间中的最近邻查找问题,并表现出较好的试验结果。1 KD树与混合索引1.1 KD树及其改进KD 树的概念自从提出以来,就被广泛应用于最近邻查找之中,用来解决在 k 维数据空间中如何为数据集建立索引的问题。为了在已知的样本空间中高效地查找到输入点的最近邻点,通常采取建立索引的方式,“以空间换时间”。KD 树采用分治法的思想,利用已有数据对 k 维空间进行切分。作为 KD 树的改进,Ball5树中划分特征空间后形成的超矩形体改为超球体,提
11、高了查找效率。然而,树形结构需要对空间进行细分,对可能是精确的近邻点都要进行对比计算,会占用较高的计算资源。因此,Zhou 等6利用了 GPU 的加速功能,让 KD 树在 GPU 上运行,目的是为了提高KD 树的运算速率。其他一些方法也能在一定程度上解决由于维度升高造成的影响,但所能达到的效果有限。1.2可学习索引RMI3采用了类似 B 树的分层机器学习模型来代替传统的索引结构,构建了一个层次化的模型,如图 1 所示。除去第一层外,每一层都由多个小模型构成,每一层模型都和上一层模型互相关联,上一层模型的预测结果将会决定接下来一层的数据如何进行划分。每一层模型都会缩小查找范围,直到最底层得到记录
12、位置的最终预测。由于误差的存在,一般情况下还需要使用二分法定位记录的精确位置。相对于传统的 B 树,可学习索引在查找性能和减少内存占用上有了较大的提升。除了一些专注于可学习索引模型本身的研究,例如 Xindex7和 Colin8外,还有一些研究将注意力集中在多维范围的可学习索引上9-10。官嘉林等11研究了内存预分配策略,较好地降低了内存缺页中断率,提高了可学习索引的性能。2混合索引的构建混合索引模型由可学习索引和传统 KD 树两部分构成。可学习索引部分通过构建机器学习模型,来代替传统索引结构中的查找和计算部分。可以将通过索引进行最近邻查找的过程看作是一个机器学习中的分类任务。在最近邻查找中,
13、输入值和其所对应的最近邻点存在联23 年 8 月商洛学院学报32(a)B 树的查找(b)可学习模型的查找图1B树索引与可学习索引系,这种联系以距离的形式体现,距离越接近的,联系越紧密,可以认为是进行聚类的过程。在构建模型的时候,采用监督学习的方式。模型训练的过程如下:对于处理好的数据集,首先将其构建成一棵 KD 树,随后,产生一系列随机数作为 KD 树的索引值,即为标签一,与构成 KD树的每一个节点相对应。接着,通过 KD 树得到训练集和测试集的最近邻点,并将所对应的最近邻点转化成为索引值,即为标签二。标签二就是训练集和测试集的标签。准确率定义为正确查找到真实 k 近邻点的所有数据占所有待查询
14、数据的比值。键B 树位置位置-0位置+页大小键模型位置-最小误差位置+最大误差模型训练阶段的算法如 Algorithm 1 所示:Algorithm 1:Learned KD tree Training StrategyInput:Dataset D,Iteration IOutput:Trained IndexTraining:1Label_1=KD tree(D)2Label_2=Transform(Label_1)3Build a deep neural network model4For i=1 to I do5Logits=Network_model(D)6.Index=round(
15、Logits)7.Loss=Loss(Logits,Label_2)8.Back propogation to minimize Loss9Return index影响可学习索引运行速度的一个重要因素是神经网络的层数。一般来说,隐藏层的数目越多,提取到的特征就会越准确,整个神经网络的误差就会越低,从而让精度得以上升。然而,当层数增加时,会使得总的参数量增加,导致神经网络更加复杂。同时也可能会使神经网络的训练出现过拟合现象,训练时间也会变长。为了使神经网络的性能得到一定程度的保证,同时保证模型的泛化能力,尽量避免过拟合的发生,在保证准确率的基础上,尽可能使用较少的神经网络层数。使用 KD 树进行
16、最近邻查找时,主要包含两个部分:首先是把最近邻点的叶子节点当作待查找点的近似邻最近点。其次是进行回溯操作,以待查找点和最近邻的近似点的距离沿树根部进行回溯和迭代。一般来说,KD 树能够有效降低查找的次数。但是在某些场景中,待查询数据点所在的位置会需要在另外一棵子树上进行查找,造成查找次数增加,从而降低了查找的效果。随着数据维度的升高,使用 KD 树进行最近邻查找的性能会明显降低。通常情况下 KD 树在 20 维以内的数据集上较为有效。在使用 KD 树进行最近邻查找的过程中,需要经过大量的回溯操作和距离计算,从而得到精确的结果。对于可学习索引来说需要做的是将这些回溯和计算用神经网络进行代替,同时
17、辅以少量的计算和排序,在提高神经网络准确性的基础上,尽量得到相同或相似的结果。Peng等4详细介绍了基于可学习索引的可学习 KD 树的构建过程和在最近邻查找中相对于传统 KD树的优势。使用基于神经网络的可学习索引方法,利用神经网络并行计算的优势,可以有效地降低运算过程所花费的时间。同时,神经网络模型还可以通过设计更好的网络结构、降低参数数量等方法进行改进和优化,在确保模型准确率的情况下提彭永鑫,罗英:一种基于混合索引的最近邻查找方法33第 4 期23 年 8 月商洛学院学报34待查找数据可学习索引模型得到 k 个近邻点由一半节点构成的新 KD 树得到 k 个近邻点得到 2k 个近邻点得到最终
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一种 基于 混合 索引 近邻 查找 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。