关键词: 近似近邻检索（ANNS）, 哈希编码, 随机森林, 顺序敏感的海明距离

Abstract: The retrieval of approximate data from massive data is the key to many applications in data mining. Especially in the recent years, the scale of data has exploded, and data retrieval needs to face the overlapping test of massive data and “dimension disaster”, which makes the efficiency of traditional nearest neighbor algorithm decrease,while the approximate nearest neighbor algorithms are playing an increasingly important role. Among them, the Hashing algorithm has received extensive attention due to its advantages in storage space and computation time. This paper proposes a Hashing algorithm based on random forest. In the method, by constructing a random forest, the sample of the original space is mapped to the binary Hash code of Hamming space, and an order-sensitive Hamming distance is defined to keep the neighbor relationship of the data in the original space to the maximum extent. Since the feature space and learning process used by different decision trees in a random forest are independent, the length of the Hash code can be flexibly determined in an incremental manner. In addition, the proposed algorithm based on random forest is naturally suitable for parallel deployment, which can greatly improve the speed of the algorithm. Finally, the proposed algorithm is experimentally verified in the MNIST and CIFAR-10 data sets. The results demonstrate the effectiveness and great performance of the algorithm.

Key words: approximate nearest neighbor search (ANNS), Hashing code, random forest, order-sensitive Hamming distance