Journal of South China University of Technology (Natural Science Edition) ›› 2007, Vol. 35 ›› Issue (5): 65-69.

• Computer Science & Technology • Previous Articles     Next Articles

Novel Algorithm for K-Nearest Neighbors of Massive Data Based 00 Spacial Partitioo

Ping Xue-lian1  Xu Rong-li1  Kong lun1  Liu Sheng-lan2   

  1. 1. School of Mechanical Engineering , Southem Yangtze Univ. , Wuxi 214122 , Jiangsu , China;2. College of Mechanical and Electrical Engineering , Nanjing Univ. of Aeronautics and Astronautics , Nanjing 210016 ， Jiangsu , China
  • Received:2006-04-26 Online:2007-05-25 Published:2007-05-25
  • Contact: 平雪良(1962-)，男，博士，教授，主要从事逆向工程与快速原型技术方面的研究. E-mail:ping@sytu.edu.cn
  • About author:平雪良(1962-)，男，博士，教授，主要从事逆向工程与快速原型技术方面的研究.
  • Supported by:

    航空科学基金资助项目(03H52059)

PDF

863

Abstract:

In the reverse engineering , the first thing for processing the measured data is to build up the topology of the point cloud , which is generally implemented by calculating the K-nearest neighbors. In this paper , the existing algorithms of K-nearest neighbors are analyzed , and a new algorithm for K-nearest neighbors of massive data based on spacial partition is proposed. In the proposed algorithm , the effects of K value and point-cloud density and number on the side length of small sub-cubes are considered , and the most suitable searching range is obtained by finding the suitable side length of small sub-cubes and by excluding small sub-cubes without point cloud inside. Thereby , the searching speed is raised and the correctness of searched results is ensured. The proposed algorithm is finally verified by the second exploiting programming of reverse engineering software.

Key words: reverse engineering, massive data, K-nearest neighbor, neighbor point searching, algorithm