Using Interval Trees for Approximate Indexing of Instances

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.

• Khalil el Hindi

• Instance based learning
• interval trees
• the knn algorithm
• machine learning.

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