您的当前位置:首页正文

基于改良NB树的内存高维索引算法

来源:化拓教育网
维普资讯 http://www.cqvip.com 《农业网络信 g}2007年第4期 信息资源建设与管理 基于改良N B树的内存高维索引算法 邝颖杰 ,刘燕 f1.华南农业大学信息学院计算机系,广东广州510642;2.广东技术师范学院管理系,广东广州510665) 摘要:基于内容的图像检索是近年来的热门研究内容,其中,有效的高维索引机制是使大规模图像库的检索能够达到实 时性要求的关键技术。以往大部分学者都集中研究磁盘索引,但其实在目前大内存的环境下对内存索引的研究也是非常必 要。本文运用PCA原理改进了一种理想的内存索引方法NB树,经过改进以后其检索性能得到进一步提高。 关键词:基于内容的图像检索;内存索引;高维索引;k-近邻检索 中图分类号:TP319 文献标识码:B 文章编码:1672—625l(2007)04—0059—04 Memory—basedindex algorithm in higI卜dimensional spaces based on the improved NB tree KUANG Ying-jie ,LIU Yan (1.South China Agricultural University,Guangzhou 5 10642,China;2.Guangdong Polytechnic Normal University,Guangzhou 510665,China) Abstract:Content—based image retrieval become hot spot in research for recent years.Eficifent indexing schemes for hJigh— dimensional data are required for real-time retrieval in large-scale image database.For a long time researchers only focus on disk-based index,but research on memory-based index is of great value today because of the mass memory condition.A modification of NB tree based on PCA theory is proposed in this paper.Experiment shows that the search performance Can be further improved by the modiicatifon. Key words:Content-based image retrieval;Memory—based index;High-dimensional index;k-NN search 1 引言 在以往很长的一段时间内.关于高维索引的研究 都集中在磁盘索引这一领域.这与以前的硬件发展状 况有关。当时内存的价格非常高.一般主流计算机的内 存只有几十兆.很难容纳大规模数据库的数据.因此那 少在构造维护索引上所花的开销。很显然.简单的算法 比复杂的算法更适合应用到内存索引当中 下文将介 绍一种理想的内存索引NB树【 1及其改进 NB树的算法 非常简单.在内存索引的环境下.其检索效率不但超越 了顺序搜索,而且超越了很多传统的索引方法。但NB 树在选择参考点的算法上存在弊端.本文将对其运用 PCA原理进行改进,使算法性能进一步提高。 2 NB树 时候把全部数据放到内存中进行搜索基本上是不可能 的。但随着硬件的迅速发展,现在的主流内存配置已经 达到几百甚至上千兆.可以容纳数百万条高维数据.也 使在内存中搜索成为可能 因此对高维索引的研究就 有必要考虑到内存索引这一方面.研究如何在内存中 使用一定的算法令检索速度超越顺序搜索 内存索引 与磁盘索引最大的不同是其搜索时间主要花在CPU的 计算上,而不是磁盘访问上,因此对于内存索引来说, 读取数据的时间基本上是可以忽略不计的.主要考虑 2.1 NB树的结构 NB树是Manuel J.Fonseca和Joaquim A.Jorge于 2003年在文献【11中提出的一种非常高效的高维索引方 法。与其他大多数的方法不同,该方法的原理和算法都 非常简单.为构造索引和维护索引所花的时间空间开销 都非常小。而且.它可以很好的克服“维度灾难”问题,不 管原始数据的维度有多高和数据量有多大.它都可以取 得比顺序搜索要好的性能 文献【11中对NB树的性能进 行了广泛的测试 使用了均匀分布的数据集、不定维度 的应该是计算高维数据之间的距离的次数 为了要在 速度上超越顺序搜索.内存索引就必须尽量减少顺序 搜索中最消耗时间的距离计算次数.而且必须尽量减 收稿日期:2007一Ol一05;修回日期:2007—01—09 作者简介:邝颖杰(1979一),男,硕士,助教,研究方向:计算机软件与理论。 一59— 维普资讯 http://www.cqvip.com 《农业网络信息》2007年第4期 信息资源建设与管理 的数据集和真实数据集来作为实验数据集.数据维度最 高达到256维,数据集大小最高达到1 000 000。全部数 其中.结果集RS是暂时存放k一近邻结果的集合. RS的最大距离是指这k个候选结果中和查询点相距 最远的点的距离 上述算法的正确性也是很容易得到证明 和范围 搜索算法类似.这里的搜索也是为了找到以查询点Q 为圆心.以一定长度为半径的小圆.但这个小圆里必须 包含至少k个点 因为在这个小圆里的点一定是与查 询点相距最近的点.所以只要求出这些点中与查询点 最近的k个点,就得到最终的结果。但由于半径事先不 据放在内存中.不考虑磁盘FO,只考虑搜索的绝对时 间。另外还考察了生成索引的时间和对空间的占用 实 验结果表明,NB树的各项性能都超过了金字塔技术【2]、 SR树13]和A树 ,是一种非常理想的内存索引结构 NB树的基本思想是使用欧几里德范数(Euclidean non)来作为高维数据的索引值,事先排序好该索引 值.以后在搜索的时候就可以利用该索引值快速缩小 搜索范围,减少不必要的距离计算。其中,欧几里德范 数是指高维数据点到原点的欧几里德距离.是一个非 知道.因此必须使用试探的方法.不断增加半径进行范 围搜索,直到找到k个结果为止,如图1所示。 常容易取得的值。而对该索引值的排序则使用B+树.因 为它是一种非常成熟优秀的一维索引方法 使用欧几里德范数作为索引值其实是一种从高维 到一维的映射方法.高维空间中相邻的点的欧几里德 范数也会比较接近(但反之则不然)。因此,在查询的时 候就可以先搜索欧几里德范数和查询点比较相近的 点,从而快速找到结果集。另外,B+树有个特点,就是其 叶子结点会链接成一个排好序的列表.因此可以非常 方便的按顺序遍历B+树的叶子结点 建立NB树的步骤是:首先,计算数据集里所有高 维数据的欧几里德范数.公式如下: e step 图1 NB树的k一近邻搜索 I IP I I=、/P02+Pl +…plD2-1 其中,D是数据的维度 是特征向量P的第i个分量。 然后.把这些D维的数据插人到B+树中,并以其欧几里 德范数作为键值 插人完所有的数据之后我们就得到 了一个根据欧几里德范数排序的D维数据集。 2.2 NB树的k一近邻检索算法 3 NB树的改良 NB树选用数据点和原点的距离(欧几里德范数) 作为索引值,即以原点作为参考点去计算索引值。该方 法虽然简单,但却没有考虑数据的分布状况。文献15中 的LMFile索引运用PCA原理选择landm ̄k点的做法 可以结合到NB树中来。如图2所示,假如数据集里的 NB树的k一近邻搜索算法返回与查询点Q距离最 相近的k个数据点,步骤如下: (1)设定搜索半径的步长值step,迭代系数i=1,置 空结果集RS (2)计算查询点Q的欧几里德范数e(即和原点的 距离)。 ●参考点1 ●磐考点2 (3)利用B+树迅速找到欧几里德范数在(e—step*i) 图2不同参考点的效果 和(e—step*(j_1))之间,以及(e+step j)和(e+step (J1- 1))之间的候选数据点集DS。 数据集中分布在从西北到东南方向的带状区域,左图 我们选择原点作为计算距离的参考点,右图则选择东 南角的一个点作为参考点。可以看到,由于左图中的数 据点和参考点的距离很相近,因此计算出来的距离值 大部分都集中在一个很小的范围内,当要进行范围搜 索或k一近邻搜索时就几乎要搜索全部的数据点,这样 就起不到索引的作用。另一方面,右图的参考点落在数 据主要分布方向的轴上.因此计算出来的距离值具有 较大的差异.进行查询的时候就可以大大的缩小搜索 60— (4)遍历DS中每一个点Pi,计算Pi与Q的距离d。 如果结果集RS不足k个,则把Pi插人RS;否则比较d 和结果集中的最大距离.如果d小于最大距离,则删除 结果集中最大距离的点,插人 。 (5)如果RS中的点不足k个,则j=j+1,返回(3)。 (6)如果RS中的最大距离不大于(step*j),则RS 为最终结果集。否则返回(3)。 一维普资讯 http://www.cqvip.com 《农业网络信  ̄,)2007年第4期 信息资源建设与管理 范围 从以上现象可以发现.要令距离值具有较大的差 异就必须在数据主要分布方向上选择参考点.而不应 该固定使用某个参考点或随机选择参考点。 为了找到数据集中具有最大差异的方向.我们借 助主成分分析(PCA)方法 首先计算数据集的平均向 量 和协方差矩阵C.N为数据集样本总数:然后用正 表1改良NB树的实验结果(10 000人) 在原数据集中抽取10 000个向量作为测试集.最终结 果是这10 000个查询向量性能数据的平均值。表2是 测试结果。 表2改良NB树的实验结果(88 908人) 交矩阵 来对角化C,A 是C的特征值,矩阵 的列 向量 = 。… 是C的特征向量。和最大特征值A 对应的特征向量‘D 就指出了数据集的最大差异方向 因此,参考点应该在直线g=x+v・ 上选择,而且为了 加大距离的差异.参考点应该选在远离数据集的地 方.也就是v的取值应该比较大(在我们的实验中 取 值1 000 000)。 = ‘’ ∑麓c= 1∑ ) ) ‘’ 从表1和表2中可以看到.改进后的方法比原来 ℃ =diag(Al,…,A 的方法有了一定的进步 而且.随着数据库规模的增 大.性能的提高就越明显 直接计算C的特征值和特征向量是比较困难的. 可以使用奇异值分解(Singular Value Decomposition)方 法来确定 5 结束语 本文介绍了一种基于映射的高维检索方法NB树 在实际应用中.由于PCA的计算量比较大.因此 及其改进方法 NB树由于其算法简单,因此维护索引 的开销比其他索引小.而且其设计目的在于减少距离 计算次数,因此非常适合作为内存索引。但该方法有一 个弊端,就是使用固定的点(原点)作为参考点来计算 索引值,没有考虑到数据的分布情况。因此,我们利用 PCA理论对NB树进行了改进,寻找更合理的参考点。 实验表明改进以后的方法比原来有了一定的性能提 升 参考文献 不可能对整个原始数据集应用上述方法来求其最大差 异方向 解决这个问题的办法是随机抽取一部分的数 据来模拟原始数据的分布.然后对这部分数据进行主 成分分析 4实验和讨论 下面用实验去证明对NB树的改进能提高NB树 的性能,使其检索速度进一步提高。程序使用Visual C++6.0实现,全部数据和索引都放在内存中。我们采用 两个数据库进行测试.特征向量是经Fisherfacet61方法 提取代表人脸特征的45维向量 改进了的NB树在生 成树的时间上会比原来要长一些.因为要计算数据的 [1】 Manuel J.Fonseca,Joaquim A.Jorge,Indexing Hih— gDimensional Data for Content-Based Retrieval in Large Databases,in Proceedings of the Eihtgh International Conference on Database Systems for Advanced Applicadons 分布方向.但由于这个操作只需要做一次,因此还是值 得的。 4.1 10 000人数据库 (DASFAA’03),2003. 【2】 S.Berchtold,C.B "ohm,and H.一P.Kriege1.The Pyramid— Technique:Towards Breaking the Curse of Dimensionality.In 在这个数据库中.我们对NB树及其改良方法进 行了1一NN、5一NN、10一NN、15一NN、20一NN五种查询的 Proc.of hte Int.Conf.on Management of Data(SIGMOD’98). ACM Press,1998. 测试.测试数据集和原始数据集一样,最终结果是这 10 000个查询向量性能数据的平均值。由于在内存索 引中.距离计算的时间占了最大的份量,因此这里采用 【3】Norio Katayama and Shin’ichi Satoh,The SR—tree:An index structure for high-dimensional nearest neighbor queries,in Proceedings f ohe 1997 tACM SIGMOD International Conference on Management of Data,May 1997,PP.369-380. “距离计算次数”作为衡量查询效率的准则。表1是测 试结果 4.2 88 908人数据库 【4]Y.Sakurai,M.Yoshikawa,S.Uemura,and H.K ̄ima.The A— tree:An Index Structure for Hi h—Digmensional Spaces Using Relative Approximation.In Proc.of the 26th Int.Conf.on Very 在这个数据库中.我们对NB树及其改良方法进 行了1一NN、10一NN、20一NN、40一NN四种查询的测试, 一Large Data Bases fVLDB’00),pages 516~526,Cairo,Egypt, 61— 维普资讯 http://www.cqvip.com 《农业网络信息》2007年第4期 信息资源建设与管理 (上接第48页) 设、生产管理水平以及园区的示范效果 累我区农业各方面的信息,建立我区农业信息数据库 为我区未来农业规划提供决策依据 4.2继续实行上网鼓励政策,加强上网技术培训 3.1-4 园区WebGIS系统f网络版)的熟化和应用 完善 和熟化园区WebGIS系统.通过网络实现园区远程访问 和技术咨询,宣传园区的自然环境、投资环境和优佳农 副产品。 由于农民自身文化素质的限制.大多数农民停留 在浏览信息阶段,对搜索、发布信息和使用电子邮件还 未能熟练掌握,对信息的需求也只停留在价格、供求信 息上,不善于主动利用科技信息指导调整品种结构、提 高种养技术水平 3.1.5 开发园区蔬菜精准施肥系统和安全生产系统 开展大比例尺(1:5 000或更大)精准施肥.服务到具体田 块。与农民习惯施肥相比,肥料利用率提高10%以上.农 业化学物质(主要是肥料)的投入由随意到精细,同时改 善农业环境污染。同时开展蔬菜安全和标准化生产的 技术咨询,农产品质量的全程监控.提高农产品生产的 安全性。 3.2网络信息服务试点 为此,我们可以成立计算机培训基地.聘请电脑专 家为农民讲课,比较系统地传授计算机知识 4.3加强信息技术的普及应用 (1)加强与市农林渔业局、市农技推广总站的联系 和与华南农业大学的联系。实现网上农业技术推广和 3.2.1建好与完善我区农业信息网 此网作为我区农 业宣传、和百姓沟通交流的平台并逐步整合村级内部 资源,栏目包括:村容村貌f可图文并茂)、名企名品f可提 供相关企业的资料和产品)、供求信息f包括供货信息和 求货信息:农民朋友在网站上要发布供求消息的资料 经审核后发布)、招商引资、农村远程教育f提供各种适 合农民朋友的科普类教育片实时在线点播)、农技知识、 政策法规、旅游资讯、网上论坛、农民信箱入口、最新公 告、友情链接、联系我们等f设置专用接收邮箱)。 病虫害预报与防治的信息应用功能 (2)加强与市气象局、三防办的合作。建立防灾减 灾决策支持系统.提高快速反应和决策调度的自动化 水平。 (3)在全区推进农村基层管理信息化,实行网上镇 务公开、村务公开 (4)重点突破,实行“网上交易”,建立具有独立网 址的公司主页.通过电子邮件成功联系业务。增强产品 市场开拓力度 要选择一批条件成熟的客户发展“网上 交易”.通过典型示范.带动推进。 参考文献 3.2.2建好一个培训教室 利用将要建成的农业研发 大楼,添置一批计算1(E(30台左右)和网络设备,形成局 域网.建成信息技术应用培训教室 充分利用建成的教 室对我区农村干部和40周岁以下村民进行培训.逐步 [1】佟利亭,尹衍波.中国农业信息化的现状及重点发函领域[J】. 世界农业,2004,(6). [2】余艳兰.农业信息卡在“最后一公里”[N】.甘肃经济日报, 2003—12—22(2). 提高他们的信息技术应用能力.并为村民上网搜索信 息提供服务 4农业信息化工作的远景展望 4.1 成立区农业信息科.完善我区农业信息网 [3】吴建寨,东野光亮,等.农业信息化进程中的政府角色剖析[J】_ 农村经济,2004,(4):86~88. 成立农业信息科.充实农业、计算机、信息等专业 的人材.专门负责我区农业信息收集、加工的工作。积 [4】 吕晓燕.试论农业现代化与农业信息化[J】.情报科学,1999, (增刊). 一62— 

因篇幅问题不能全部显示,请点此查看更多更全内容