Optimizing nearest neighbor retrieval by similarity template and retrieval query generation

The nearest neighbor algorithm is the most basic class of techniques in the sub-fields of machine learning such as case-based reasoning (CBR), memory-based reasoning (MBR), and instance-based learning (IBL). In the nearest neighbor algorithm, the computational cost of example retrieval is one of the most important issues. This paper proposes a novel technique for optimizing the nearest neighbor algorithm. Its basic idea is based on the use of similarity template, which is a data structure that enumerates all the possible patterns of calculating similarity between two examples. In the method, the nearest neighbor retrieval process is optimized by generating retrieval queries from an input and similarity templates in a certain order. Its major advantages are as follows: 1) unlike the hierarchical organization of memory, it is guaranteed that examples with the greatest similarity value according to the given similarity measure are retrieved, 2) it is easy to add new examples to the example database, 3) without any expensive hardware such as massively parallel computers, nearly constant time nearest neighbor retrieval can be achieved, independently of the number of examples in the database.http://library.naist.jp/mylimedio/dllimedio/show.cgi?bookid=100009583&oldid=1688