Nearest neighbor search using additive binary tree

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 numb...

Full description

Saved in:
Bibliographic Details
Main Authors: Sung-Hyuk Cha, Srihari, S.N.
Format: Conference Proceeding
Language:English
Subjects:
Additives
Binary trees
Electronic mail
Frequency
Nearest neighbor searches
Optical character recognition software
Pattern recognition
Prototypes
Query processing
Text analysis
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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).
ISSN:1063-6919
DOI:10.1109/CVPR.2000.855900