摘要
最近邻问题是计算几何学中的基本问题之一 ,k 近邻是最近邻的扩展 ,它在VLSI设计、数据库检索、模式匹配以及图像处理等领域有着广泛的应用背景 对于点数为N的平面点集S ,在规模为N×N的可重构造网孔机器上 ,提出了时间复杂度为O(k)的求S中所有点k 近邻的并行算法
Nearest neighbor query is a basic problem of computational geometry As an extension of nearest neighbor query, k nearest neighbor is widely applied in the fields of VLSI design, data retrieval, pattern matching, graph processing, etc A parallel algorithm on a reconfigurable mesh of size N×N for k nearest neighbor search in a planar point set S of N points is presented The time complexity of this algorithm is O(k) It attains the lower bound of this problem
出处
《计算机研究与发展》
EI
CSCD
北大核心
2004年第9期1559-1564,共6页
Journal of Computer Research and Development
基金
国家"八六三"高技术研究发展计划基金项目 (2 0 0 1AA1110 41)
关键词
并行算法
K-近邻
可重构造网孔机器
parallel algorithm
k-nearest-neighbor
reconfigurable mesh
