EFFICIENT SIMILARITY COMPUTING METHODS IN HIGH DIMENSIONAL DATA

Similarity is a pivotal notion in research on lazy learning, such as case based reasoning and k NN （nearest neighbor）. A method of how to decrease complexity of computing similarity is studied, and a similarity calculation algorithm is introduced, that is based on partial features and the similarity calculation algorithm that is based on projection. For briefness and clarity, they are described in the procedure of k NN: partial feature based k NN algorithm and projection based k NN algorithm. In the steps of acquiring distance, using only few features can improve efficiency. This improvement is remarkable in our experiment: the former increases about 26%~28%, and the latter increases from 48% to 83%. At the same time, those algorithms have been adapted in application successfully.