道路网中基于RRN-Tree的CKNN查询.pdf

《道路网中基于RRN-Tree的CKNN查询.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第40卷第6期计算机工程2014年6月Vl0l

2、40NO．6ComputerEngineeringJune2014·开发研究与工程应用-文章编号：1000—3428(2014)06—0306—06文献标识码：A中图分类号：TP311．13道路网中基于RRN．Tree的CKNN查询孙海龙，王霓虹(东北林业大学信息与计算机工程学院，哈尔滨150040)摘要：现有针对基于道路网络的CKNN查询研究，主要是将道路网络以路段和节点的形式进行建模，转化成基于内存的有向／无向图，该模型存在2个问题：一个是道路网络中路段数据量大，导致

3、索引结构分支过多、移动对象更新频繁；另一个是图表示方法不能很好地处理十字路VI转向、u型转弯等交通规则。针对此问题，提出道路网中基于RRN—Tree的移动对象CKNN查询算法，包括索引结构设计和移动对象查询算法设计，采用路线对道路网建模，基于网络边扩展方式，实现复杂条件下的道路网络CKNN查询。实验结果表明，在各种网络密度和兴趣点对象分布密度下，与经典的IMA／GMA算法相比，基于RRN—Tree索引方法的查询性能提高1．5倍～2．13倍。关键词：道路网络；连续K最近邻查询；RRN树；扩展网络边；K近邻监测区；兴趣点分

4、布密度CKNNQueryBased0nRRN-TreeinRoadNetworkSUNHai—long，WANGNi-hong(CollegeofInformationandComputerEngineering，NortheastForestryUniversity,Harbin150040，China)[Abstract]MostofexistingmethodsforContinuousKNearestNeighbors(CKNN)queryofmovingobjectsinroadnetworksmodelth

5、eroadnetworksasroadsegmentsandnodes，andconvertthemintodirectionalgraphorundirectionalgraphinmemory．Therearetwoproblemswiththismode1．First，thenumberofroadsegmentsisSOhugethattherearetoomanybranchesinindexstructureandfrequentupdateofmovingobjects．Second，traficregu

6、lationslikethecrossroadsturnandUtumcannotbeprocessedingraphmode1．ThispaperproposesaCKNNqueryalgorithmofmovingobjectsbasedonRRN—Treeinroadnetworks，whichincludesthedesignofindexstructureandqueryalgorithmformovingobjects，modelsroadnetworkasroutes，andimplementsCKNNq

7、ueryinroadnetworksundercomplicatedroadconditionsbyexpandingtheroadedges．ExperimentalresultsshowthatthemethodbasedonRRN—TreehasbetterqueryperformancethanclassicalIMA／GMAalgorithmundervariousnetworkdensityandobjectsdistributiondensity,andtheperformanceisincreasedb

8、y1．5-2．13times．[Keywords]roadnetwork；ContinuousKNearestNeighbors(CKNN)query；RRN—Tree；expandnetworkedge；KNearestNeighbors(KNN)monitorarea；distributiondensityofinterestpointDoI：10．3969／j．issn．1000—3428．2014．06．065决此类问题的关键在于：(1)快速实时计算任意2个移动对1概述象之间的最短路径；(2)移动对象位置更新的

9、维护与管理。随着无线通信技术的发展和具有GPS定位功能的移动本文针对现有算法查询效率较低和不能处理十字路口电话、PDA等便携设备的普及，基于位置服务(Location转向和u型转弯问题，提出道路网中基于RRN—Tree的移BasedService，LBS)得以快速发展，已广泛应用于地理信息动对象连续K最近邻查询算法。系统、应急服务