A Study Of Learned KD Tree Based On Neural Network

With the continuous development of the time,people have paid more and more attention to the efficiency and accuracy of data retrieval.The dimensions of data in the real world are often high.Traditional indexing methods,such as hash indexes,are widely used in various information retrieval systems as an efficient information retrieval method,but it is increasingly difficult to cope with complex happening.How to perform data retrieval efficiently and effectively has become a hot topic.In order to ensure retrieval efficiency,it becomes a feasible method to sacrifice certain accuracy in exchange for higher query efficiency.In recent years,with the development of artificial intelligence and deep learning,machine learning has played a huge role in more and more fields.Based on this,Google proposed a new idea of using machine learning models instead of traditional index structures,and proposed a learned index architecture.This article first summarizes the previous work of building hash functions using machine learning models,and introduced a traditional tree structure: KD trees.Based on the learned index architecture,a learned index framework for nearest-neighbor search and k-nearest neighbor search is proposed: the learned KD tree LK.The framework consists of six phases,each of which defines specific roles and rules.Compared with the predecessors,the innovation of this paper is to propose a brand new LK framework.The LK framework is used to implement nearest neighbor search and k nearest neighbor search.Based on the selection of an appropriate loss function,the possible effects of various parameters on the experimental results are analyzed,and summarizes how to choose the appropriate parameters in specific situations.Finally,the feasibility of the LK framework is verified through experiments,and compare with the KD tree from the two perspectives of running time and accuracy,and improved methods are proposed for the problems of the framework.The experimental results show that,whether it is a generated data set or a real data set,the LK framework can obtain a certain advantage in search time on the basis of ensuring a certain search accuracy.