基于半度量路网的高效查询算法

《基于半度量路网的高效查询算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC作者姓名：指导教师：申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅人：密级学位论文基于半度量路网的高效查询算法张晶晶杨晓春教授东北大学信息科学与工程学院硕士学科类别：工学计算机应用技术2014年6月论文答辩曰期：2014年6月2014年7月答辩委员会主席：申德荣王斌，石祥滨东北大学2014年6月万方数据AThesisinComputerApplicationTechnologyQueryAlgorithmsinSemimetricRoadNetworkByZhangJingjingSupervisor

2、：ProfessorYangXiaochunNortheasternUniversityJune2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：多次赫晶日期：2DJ牛．6．≯毕学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国

3、家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口两年∥学位论文作者签名：弓歌晶晶导师签名：％砭勿农签字日期：】of峪．6．了牛签字日期：)。l‰6．L垆万方数据东北大学硕士学位论文摘要基于半度量路网的高效查询算法摘要空间数据库己成为数据库领域中的热点研究方向，路网作为空间数据库领域中重要的一部分，目前在各个地图服务、商用在线导航系统以及基于位置的查询应用软件中有着广泛的应用，路网中

4、的查询得到了越来越广泛的关注。由于路网具有道路数量多、密度大、交叉频繁、路况复杂等特性，如何在路网中高效的查询至关重要。路网中利用网络距离作为距离的度量方式，广泛存在不满足三角不等式关系的情况，称这样的路网为半度量路网。由于半度量路网不满足三角不等式关系，常见的度量空间中的索引结构无法有效工作，目前已提出的预计算的方法存在查询速度慢、计算代价慢的问题，如何在半度量路网中高效的查询是本文的研究重点和难点。为了解决半度量路网中的查询速度慢、计算代价大的问题，本文提出了半度量路网中的高效查询方法。首先，由于直接在半度量路网中查询代价大，本文

5、提出了两种方法将半度量路网转化为度量路网来降低查询代价。一种方法为随机删除边算法将半度量路网转化为度量路网，该方法简单，容易实现，但转化过程中信息损失比较大。为了进一步降低查询代价，以最小化的信息损失将半度量路网转化为度量路嘲，这是一个NP．hard问题，因此本文提出了另一种启发式的排序删除边算法以近似最小化的信息损失完成度量化。其次，提出了QM一树索引结构，在查询中利用三角不等式关系剪枝不可能包含查询结果的子树，有效的减少了查询时问。最后，本文提出j=，半度量路网中的范围查询方法以及K近邻查询方法。这两种查询方法都包括查询和验证两部

6、分，查询部分利用三角不等式关系来剪枝不可能为查询结果的子树，快速的找出查询结果，有效的加速查询；验证部分对找到的查询结果节点和查询点中指针指向的包含信息损失的链表中的元素分别进行验证，有效的保证了查询的正确性。最后，本文在真实的数据集上进行了大量的测试研究，通过对实验结果的分析与总结，证明了排序删除边算法能够以近似最小化的信息损失将半度量路网转化为度量路网；基于QM．树索引结构的半度量路网中的范围查询算法以及K近邻查询算法有效的降低了查询代价并保证了查询结果的准确性。关键词：路网；三角不等式：半度量；范围查询；K近邻查询万方数据东北大

7、学硕士学位论文AbstractQueryAlgorithmsResearchinSemimetricRoadNetworkAbstractSpatialdatabaseshavebecomeahotresearchdirectioninthefieldofthedatabase，inwhichroadnetworkasanimportantparthascurrentlybeenwidelyappliedinvariousmapservices，commercialonlinenavigationsystemsandlocation-

8、basedqueryapplication．Queryinginroadnetworkhasgotmoreandmoreattention．Duetothelargenumberofroads，highdensity,c