Nearest Neighbor Search Using Additive Binary Tree

Abstract

Classifying an unknown input is a fundamental problem in pattern recognition. One standard method is finding its nearest neighbors in a reference set. It would be very time consuming if computed feature by feature for all templates in the reference set; this naive method is O(nd) where n is the number of templates in the reference set and d is the number of features or dimension. For this reason, we present a technique for quickly eliminating most templates from consideration as possible neighbor. The remaining candidate templates are then evaluated feature by feature against the query vector. We utilize frequencies of features as a pre-processing to reduce query processing time burden. The most notable advantage of the new method over other existing techniques occurs where the number of features is large and the type of each feature is binary although it works for other type features. We improved our OCR system by at least a factor of 2 (without a threshold) or faster (with higher threshold value).