Concept of applying universal hashing and open addressing for performance enhancement of Lazy Learning method

Lazy Learners are those that postpone building Classifier models until a new data tuple is presented. Case-Based Reasoners fall under the category of Lazy Learners. CBRs treat every freshly encountered unclassified object as a case, and endeavours to place it in a storage area called Case-Base, after supplementing the object with its correct class. This process of insertion is preceded by a search amongst the old cases in the Base. If an exact match is found there is no need to insert. Otherwise, some near matches are found whose class information help to provide the new case with a suitable class and insert it in the Case-Base. Search and insertion techniques are optimized by first generating keys for each data tuple or case and then using universal hashing functions to map these onto the base while searching for matches. Collisions are next resolved by open addressing strategies such as linear and quadratic probing, and double hashing. Performance of the Classifiers are analysed with the help of some standard datasets provided by the UCI machine learning repository.