基于hibert曲线的查询方法研究

《基于hibert曲线的查询方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、理学硕士学位论文基于Hilbert曲线的查询方法研究王龙哈尔滨理工大学2013年3月国内图书分类号：TP391理学硕士学位论文基于Hilbert曲线的查询方法研究硕士研究生：导师：申请学位级别：学科、专业：所在单位：答辩日期：授予学位单位：王龙刘润涛教授理学硕士应用数学应用科学学院2013年3月哈尔滨理工大学ClassifiedIndex：TP391DissertationfortheMasterDegreeinScienceResearchontheQueryofHilbertCurveCandidate：Supervisor：AcademicDegreeA

2、ppliedfor：Specialty：DateofOralExamination：University：Prof．LiuRuntaoAppliedMathematicsMarch，2013HarbinUniversityofScienceandTechnology哈尔滨理工大学硕士学位论文原创性声明本人郑重声明：此处所提交的硕士学位论文《基于Hilbert曲线的查询方法研究》，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进行研究工作所取得的成果．据本人所知，论文中除已注明部分外不包含他人已发表或撰写过的研究成果．对本文研究工作做出贡献的个人和集体

3、，均已在文中以明确方式注明．本声明的法律结果将完全由本人承担．作者签名：互召日期：易少年，肛／日哈尔滨理工大学硕士学位论文使用授权书《基于Hilbert曲线的查询方法研究》系本人在哈尔滨理工大学攻读硕士学位期间在导师指导下完成的硕士学位论文．本论文的研究成果归哈尔滨理工大学所有，本论文的研究内容不得以其它单位的名义发表．本人完全了解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论文和电子版本，允许论文被查阅和借阅．本人授权哈尔滨理工大学可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容．本学位论文属于保密，在口年解

4、密后适用授权书．不保密口．(请在以上相应方框内打√)作者签名：Z名导师签名：朗徇)务日期：≯勿3年弓胸H日期：妇l3年；月叫日基于Hilbert曲线的查询方法研究摘要空间填充曲线有很多种，如Sierpinski陆线、Lebesgue曲线、Schoenberg空间填充曲线、具有正Lebesgue测度的Jordan曲线等．在众多空间填充曲线中最常用的是Hilbert曲线，Z曲线以及Gray曲线，它们的主要区别在于映射的方法不同．近些年来，空间填充曲线因其特有的降低维度特性和数据聚类特性而被用于空间数据库的索引及查询之中．在空间填充曲线被应用于空间数据库以前，最常用

5、的索引方法是基于R树及其变形树的索引结构．在二维空间中基于R树的最近邻查询算法和顺序扫描算法具有较高的查询效率．随着空间维度的增加，数据信息量呈几何级数增加，此时以上两种算法的查询效率急剧下降．因此，可以利用Hilbert曲线的降维和聚类特性，将高维空间中的点映射一一映射到一维空间中，这样不仅不影响点与点之间的距离比较，而且对最近邻查询及其他查询有较高的查询效率．。本文首先引入Hilbert曲线、分析Hilbert曲线性质及特性、重点总结降维及聚类特性．其次提出一种基于Hilbert曲线网格划分的最近邻查询算法．该算法首先将数据空间分成不重叠且相等的网格，然后

6、把网格中的点进行线性排序，最后当要获取最近邻时，只需访问查询点所在网格中的点以及其周边临近网格中的点即可．最后提出一种基于Hilbert曲线的最优位置查询算法．该算法首先将空间中的点利用Hilbert曲线的降维特性映射到一维空间，然后分别利用基于R树的范围查询算法，将所有的数据对象和目标对象保存在两个队列中，最后从目标对象所在队列按照一定的规则遍历所有数据队列从而得到优先集并计算优先权．关键词Hilbert曲线；网格划分；最近邻；最优位置ResearchontheQueryBasedonHilbertCurveAbstractlhereareavarietyo

7、fspace-fillingcurves，suchasSierpinskicurve．Lebesguecurve，Schoenbergcurveofspace．fillingcl／rves，JordancurvewithapositiveLebesguemeasureandSOon．ThemostcommonlyusedonesareHilbertcurve，ZcurveandGraycurve，andthemaindifferencebetweenthemliesinthedifferentmappingmethods．Inrecentyears，space

8、—fillingcurveshaveb