ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2021, Vol. 58 ›› Issue (3): 609-623.doi: 10.7544/issn1000-1239.2021.20200285

Previous Articles     Next Articles

Approximate k-Nearest Neighbor Query of High Dimensional Data Based on Dimension Grouping and Reducing

Li Song, Hu Yanming, Hao Xiaohong, Zhang Liping, Hao Zhongxiao   

  1. (School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080)
  • Online:2021-03-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (61872105), the Natural Science Foundation of Heilongjiang Province of China (LH2020F047), the Scientific Research Foundation for Returned Scholars Abroad of Heilongjiang Province of China (LC2018030), and the Technology Research Project of Heilongjiang Provincial Education Department (12531z004).

Abstract: Aiming at the problem that the existing high-dimensional space AkNN query algorithm does not consider the association relationship between dimensions when reducing the data dimensionality, we propose the method which groups the dimensions based on association rules between dimensions to reduce the data dimensionality first. The algorithm reduces the loss of data information by dividing the related dimensions into a group for dimensionality reduction. At the same time, in order to solve the problem of data offset caused by Hash reduction, the sign bits are set and the query result is refined based on the characteristics of the sign bits. To improve the efficiency of mining association rules between dimensions, a new frequent itemset mining algorithm based on the UFP-tree is proposed in this paper. In order to improve the efficiency of the AkNN query, we map the data into binary codes and query based on the codes. And the coding functions are filtered by information entropy to improve the coding quality. In the process of refining the query results, weights are dynamically set based on the information entropy of the encoded bits of the candidate set data, and the final AkNN results are returned by comparing the dynamic weighted Hamming distance and the number of sign bit collisions. Theoretical and experimental studies show that the proposed method can effectively deal with AkNN query problems in high-dimensional spaces.

Key words: approximate k nearest neighbor, high-dimensional data, association rules, Hash, entropy

CLC Number: