一种障碍空间中的反犽最近邻查询方法-计算机学报.PDF

第卷第期 计 算 机 学 报 ３４ １０ 　 　　　　　　　　 Ｖｏｌ．３４Ｎｏ．１０ 年月 ２０１１１０ ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳ Ｏｃｔ．２０１１ 　 一种障碍空间中的反最近邻查询方法 犽 于晓楠谷峪张天成于戈 　　　 　　 （东北大学信息科学与工程学院沈阳 ） １１０８１９ 　 　 （医学影像计算教育部重点实验室（东北大学）沈阳 ） １１０８１９ 　 　 摘要随着基于位置的服务（）和物联网的快速发展，空间查询技术越来越重要，而空间查询中的最近邻查询 ＬＢＳ 　　 ， （ ） ， 及其各种变体有着广泛的应用近几年已有较多对于查询前个反最近邻对象 的研究其中大部分针对 ． 犽 Ｒ犽ＮＮ 的都是理想欧氏空间而在真实的情况下，反最近邻查询通常受障碍物影响文中研究了障碍空间中反最近邻 ． 犽 ． 犽 ， ， 查询算法提出了一种基于障碍 图的高效的剪枝方法根据 图和障碍距离的特性大幅度减少了 Ｖｏｒｏｎｏｉ ． Ｖｏｒｏｎｏｉ ， ， 数据点处理个数最后作者使用真实的数据集和多种方式分布的模拟数据验证了算法的高效性和准确性 ． ． 关键词 ； （ ）； ； 空间查询反最近邻 障碍空间 图 犽 Ｒ犽ＮＮ Ｖｏｒｏｎｏｉ 　 中图法分类号 号： ／ ＴＰ３１１ 犇犗犐１０．３７２４ＳＰ．Ｊ．１０１６．２０１１．０１９１７ 　　　 犃犕犲狋犺狅犱犳狅狉犚犲狏犲狉狊犲犽犖犲犪狉犲狊狋犖犲犻犺犫狅狉狌犲狉犻犲狊犻狀犗犫狊狋狉狌犮狋犲犱犛犪犮犲狊 犵 犙 狆 ＹＵＸｉａｏＮａｎＧＵＹｕＺＨＡＮＧＴｉａｎＣｈｅｎＹＵＧｅ