Accelerating feature-vector matching using multiple-tree and sub-vector methods

We propose two methods to accelerate the matching of an unknown object with known objects, all of which are expressed as feature vectors. The acceleration becomes necessary when the population of known objects is large and a great deal of time would be required to match all of them. Our proposed methods are multiple decision trees and sub-vector matching, both of which use a learning procedure to estimate the optimal values of certain parameters. Online matching with a combination of the two methods is then performed, whereby candidates are matched rapidly without sacrificing the test accuracy. The process is demonstrated by experiments in which we apply the proposed methods to handwriting recognition and language identification. The speed-up factor of our approach is dramatic compared with an alternative approach that eliminates candidates in a deterministic fashion.