Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (3): 790-795.DOI: 10.11772/j.issn.1001-9081.2018081647

Previous Articles     Next Articles

k nearest neighbor query based on parallel ant colony algorithm in obstacle space

GUO Liangmin1,2, ZHU Ying1,2, SUN Liping1,2   

  1. 1. School of Computer and Information, Anhui Normal University, Wuhu Anhui 241003, China;
    2. Anhui Provincial Key Laboratory of Network and Information Security(Anhui Normal University), Wuhu Anhui 241003, China
  • Received:2018-08-08 Revised:2018-09-10 Online:2019-03-10 Published:2019-03-11
  • Contact: 郭良敏
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61672039, 61602009), the Natural Science Foundation of Anhui Province (1508085QF133, 1608085MF145).


郭良敏1,2, 朱莹1,2, 孙丽萍1,2   

  1. 1. 安徽师范大学 计算机与信息学院, 安徽 芜湖 241003;
    2. 网络与信息安全安徽省重点实验室(安徽师范大学), 安徽 芜湖 241003
  • 作者简介:郭良敏(1980-),女,安徽肥东人,副教授,博士,CCF会员,主要研究方向:云计算、信息安全、服务推荐;朱莹(1994-),女,江苏泰州人,硕士研究生,主要研究方向:空间查询、信息安全;孙丽萍(1980-),女,安徽芜湖人,教授,博士,CCF会员,主要研究方向:数据挖掘、信息安全。
  • 基金资助:

Abstract: To solve the problem of k nearest neighbor query in obstacle space, a k nearest neighbor Query method based on improved Parallel Ant colony algorithm (PAQ) was proposed. Firstly, ant colonies with different kinds of pheromones were utilized to search k nearest neighbors in parallel. Secondly, a time factor was added as a condition of judging path length to directly show the searching time of ants. Thirdly, the concentration of initial pheromone was redefined to avoid the blind searching of ants. Finally, visible points were introduced to divide the obstacle path into multiple Euclidean paths, meawhile the heuristic function was improved and the visible points were selected by ants to conduct probability transfer making ants search in more proper direction and prevent the algorithm from falling into local optimum early. Compared to WithGrids method, with number of data points less than 300, the running time for line segment obstacle is averagely reduced by about 91.5%, and the running time for polygonal obstacle is averagely reduced by about 78.5%. The experimental results show that the running time of the proposed method has obvious advantage on small-scale data, and the method can process polygonal obstacles.

Key words: obstacle space, k nearest neighbors, ant colony algorithm, parallelization, visible point

摘要: 为解决障碍空间中的k近邻查询问题,提出一种基于改进的并行蚁群算法的k近邻查询方法(PAQ)。首先,利用不同信息素种类的蚁群实现并行查询k近邻;其次,增加时间因素作为路径长短的判断条件,以最直接地呈现蚂蚁的搜索时间;然后,重新定义初始信息素浓度,以避免蚂蚁的盲目搜索;最后,引入可视点将障碍路径分割为多段欧氏路径,选择可视点进行概率转移,并改进启发函数,以促使蚂蚁朝着更为正确的方向搜索,避免算法过早陷入局部最优。与WithGrids相比,当数据点个数小于300时,对于线段障碍,算法运行时间平均缩短约91.5%;对于多边形障碍平均缩短约78.5%。实验结果表明,该方法在数据规模较小时的运行时间具有明显的优势,且可以处理多边形障碍。

关键词: 障碍空间, k近邻, 蚁群算法, 并行化, 可视点

CLC Number: