| 使用R树进行k-NN搜索 |
| |
| 引用本文： | 来琳涵,刘志镜,闫立伟.使用R树进行k-NN搜索[J].计算机工程与设计,2002,23(9):77-80. |
| |
| 作者姓名： | 来琳涵 刘志镜 闫立伟 |
| |
| 作者单位： | 1. 西安电子科技大学,西安,710071
2. 中国航天科工集团二院706所,北京,100854 |
| |
| 摘 要： | 在地理信息系统中经常要做k-NN搜索，进行这些查询用到的算法与位置和范围查询的算法不同，需要专门进行研究，介绍了一种分支界限遍历R树算法，并将该算法概括为k-NN算法。文中讨论了两种方法。对R树进行结点内MBR的排序以及剪枝过程，以减少搜索空间中需访问结点的数量，有效地进行k-NN搜索。
|
| 关 键 词： | R树 k－NN搜索 分支界限算法 剪枝 数据结构 地理信息系统 |
| 文章编号： | 1000-7024(2002)09-0077-04 |
Nearest neighbor search using r-trees |
| |
| LAI Lin-han,LIU Zhi-jing,YAN Li-wei.Nearest neighbor search using r-trees[J].Computer Engineering and Design,2002,23(9):77-80. |
| |
| Authors: | LAI Lin-han LIU Zhi-jing YAN Li-wei |
| |
| Affiliation: | LAI Lin-han1,LIU Zhi-jing1,YAN Li-wei2 |
| |
| Abstract: | A frequently encountered type of query in geographic Information systems is to find the k nearest neighbor objects to a given point in space. Processing such queries requires special search algorithms. This paper introduces an efficient branch-and-bound r-tree traversal algorithm to find the nearest neighbor object to a point, and then generalize it to finding the k nearest neighbors. |
| |
| Keywords: | k-NN search branch-and-bound algorithm pruning |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
