可重构造网孔机器上k-近邻并行算法  

A Parallel Algorithm for k-Nearest-Neighbor on Reconfigurable Meshes

作　　者：赵建勇[1,2] 许胤龙[1,2] 陈龙斌 

机构地区：[1]中国科学技术大学计算机科学技术系,合肥230027 [2]国家高性能计算中心,合肥230027

出　　处：《计算机研究与发展》2004年第9期1559-1564,共6页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目 (2 0 0 1AA1110 41)

摘　　要：最近邻问题是计算几何学中的基本问题之一 ,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

关 键 词：并行算法 K-近邻 可重构造网孔机器 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP338.6[自动化与计算机技术—计算机科学与技术]