Using Interval Trees for Approximate Indexing of Instances

Authors: Khalil el Hindi

Abstract:

This paper presents a simple and effective method for approximate indexing of instances for instance based learning. The method uses an interval tree to determine a good starting search point for the nearest neighbor. The search stops when an early stopping criterion is met. The method proved to be very effective especially when only the first nearest neighbor is required.

Keywords: Instance based learning, interval trees, the knn algorithm, machine learning.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1078362

References:

[1] S. Cost, and S. Salzberg, (1993) A weighted Nearest Neighbor Algorithm for Learning with Symbolic Features. Machine Learning, Vol. 10, pp. 57-78.
[2] Hindi, K (2003) Early-Halting Criteria for Instance-Based Learning, in Proc of ACS/IEEE International Conference on Computer Systems and Applications, AICCSA03, Tunisia.
[3] S. K. Pal, S.C. K. Shiu, Foundations of Soft Case-Based Reasoning, John Wiley & sons.2004.
[4] Sproull, Robert F. (1991). Refinement to Nearest-Neighbor Searching in K-Dimensinal Trees. Algorithmica, Vol. 6, pp. 579-589.
[5] C. Stanfill, D. Waltz, (1986). Toward memory-based reasoning. Communications of ACM, 29 No 12, pp 1213-1228.
[6] Wess, Stefan, Klaus-Dieter Althoff and Guido Derwand, (1994). Using k-d Trees to Improve the Retrieval Step in Case-Based Reasoning. Stefan Wess, Klaus-Dieter Althoff, & M. M. Rithcher (Eds.), Topics in Case-Based Reasoning. Berlin: Springer-Verlag, pp. 167-181.
[7] D. R. Wilson, T. R. Martinez (2000). Reduction Techniques for Examplar-Based Learning Algorithms. Machine Learning 38, pp. 257-268.
[8] D.R. Wilson , T. R. Martinez (1997). Improved Heterogeneous Distance Functions. Journal of AI Research, 6, pp. 1-34.