| 最大空圆约束下的最邻近计算方法 |
| |
| 引用本文： | 闫超德,郭王,白建军,贺添,赵姗.最大空圆约束下的最邻近计算方法[J].测绘科学,2012,37(6):157-159. |
| |
| 作者姓名： | 闫超德 郭王 白建军 贺添 赵姗 |
| |
| 作者单位： | 1. 郑州大学水利与环境学院,郑州,450001
2. 陕西师范大学旅游与环境学院,西安,710062 |
| |
| 摘 要： | 移动目标的最邻近查询是位置服务的重要内容之一。本文针对地理目标分布不均的情况,将离散点集的最大空圆参数引入到最邻近查询中,提出了最大空圆约束下的k-D树最邻近查询算法。通过实验证明该算法可以有效地减少节点访问次数,减少距离计算次数,从而提高最邻近的查询效率。进而将该算法应用于移动目标的k阶邻近查询中,可以有效地减少移动点在三角网中的定位次数,改善k阶邻近的查询效率。
|
| 关 键 词： | 移动目标 最大空圆 k-D树 最邻近查询 k阶邻近查询 |
Nearest neighbor searching algorithm with largest empty circle constraint |
| |
| YAN Chao-de
,
GUO Wang
,
BAI Jian-jun
,
HE Tian
,
ZHAO Shan.Nearest neighbor searching algorithm with largest empty circle constraint[J].Science of Surveying and Mapping,2012,37(6):157-159. |
| |
| Authors: | YAN Chao-de GUO Wang BAI Jian-jun HE Tian ZHAO Shan |
| |
| Institution: | ①(①School of Environment and Water Conservancy Engineering,Zhengzhou University,Zhengzhou 450001,China;②School of Tourism and Environment,Shanxi Normal University,Xi’an 710062,China) |
| |
| Abstract: | The nearest neighbor queries of moving objects are of important service terms in LBS(Location-Based Services)field.But the uneven distribution of geographical objects greatly deteriorates the searching efficiency.This paper proposed an optimization nearest neighbor searching algorithm based on k-D tree with the largest empty circle constraint of discrete point set.The experiment showed the new algorithm could be better comparing with non-constraint algorithm in searching efficiency,because it effectively reduced the number of visiting nodes also the number of calculating distance.Furthermore,this algorithm could be used in searching k-order neighbor objects of moving objects to reduce the positioning number in the triangle network. |
| |
| Keywords: | moving object largest empty circle k-D tree nearest neighbor k-order neighbor |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
