动态权重路网下的连续近邻查询.pdf

第37卷 第 19期 计 算 机 工 程 2011年 10月 、，01-37 NO．19 ComputerEngineering 0ctober2011 · 人工智能及识别技术 · 文章编号：1ooo_．28(2011)l争__o157_3 文献标识码：A 中图分类号：TPI8 动态权重路网下的连续近邻查询 (北京航空航天大学软件开发环境国家重点实验室，北京 100191) 摘 要：现有的近邻查询在查询相同或相近 目标时，会得到相同的行驶路线，从而导致大量用户聚集到该区域，造成二次拥堵。针对上述 问题，提出一种支配关系监控算法。该算法采用实时交通信息作为动态权重，并给出一个在路网权重变化下的连续k近邻查询方法 ，有效 地避免二次拥堵。实验结果验证了该算法的有效性和高效性。 关健诃：连续近邻查询；动态权重；支配关系；实时交通信息；路网 ContinuousNearestNeighborQueriesin DynamicW eightRoadNetworks LVW ei—feng，WANGFei，JIANGXin—xin，ZHUTong-yu (StateKeyLaboratoryofSoftwareDevelopmentEnvironment，BeihangUniversity,Beijing100191，China) [Abstract|Whencontinuousnearestneighborsquerythetragetswhichareclose，hteyalwaysfindhtesameroutestohtenearestneighborsallhte time，whichmakesmoreandmoreusersfollowhtesameway,nadcausesatrafficjam．Aimingathteproblem，htispaperproposesadomination relationshipmonitoringalgorithm ．Itusesreal—timetrafficinformationashtechna geweight，givesanovelform ofcontinuouskneraestneighbor queriesconsideringhtelragescaleweightchangesinroadnetworkstoavoidrtafficjams．Experimentalresultshowshteefficiencynadeffectiveness ofthealgorithm． [Keywords]continuousnearestneighborqueries；dynamicweight；dominationrelationship；real—timertafficinfomration；roadnetworks DOI：10．3969j／．issn．1000—3428．2011．19．051 1 概述 发生改变时，算法会动态调整维护现有的扩展树以尽可能地 在时空数据库中，k近邻(kNearestNeighbor,kNN)查询”J 减少计算时间和扩展空间，并找到正确k近邻。 是一个最基本的问题。kNN查询的目标就是找到距离查询点 2 支配关系监控算法 最近的 个对象。伴随着智能移动终端的普及以及无线通信 本文提出支配关系监控算法解决路网权重变化的问题： 和定位技术的发展，越来越多的用户关注移动过程中的查询 (1)使用 Dijkstra算法，以给定的查询点 q为起点按拓扑 问题。现在研究的焦点也逐渐转移到了连续k近邻查询的问 结构扩展路网，以此得到最初的k近邻和一个包含所有已扩 题 (CkNN)，即在用户指定的时间间隔内[ts，te】，得到每一个 展道路(指路链)的临时网络扩展