Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 31200
Using Interval Trees for Approximate Indexing of Instances

Authors: Khalil el Hindi


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: Machine Learning, Instance based learning, interval trees, the knn algorithm

Digital Object Identifier (DOI):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1234


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