S. Grolimund & J -G. Ganascia Speeding-up Nearest Neighbour Memories: The Template Tree Case Memory Organisation La mémoire de cas est un point important pour tout système de raisonnement à partir de cas. Deux grands types d'organisation de cette mémoire ont été proposés.: l'un basé sur les techniques des plus proches voisins, et l'autre sur les techniques d'indexation selon attributs communs. Nous proposons une forme d'organisation basée sur les arbres de prototypes (Ramapriyan 1976), qui pour sa part cumule les avantages des deux approches précédentes. Elle permet d'une part l'intégration de fonctions complexes d'évaluation de la similarité entre deux cas, à l'exemple des méthodes des plus proches voisins, et d'autre part, elle accélère l'acquisition et la recherche de cas dans la mémoire à la manière des techniques d'indexation. L'évaluation expérimentale est con­ duite dans le domaine de l'apprentissage de connaissances de con­ trôle pour la résolution de problèmes d'optimisation à l'aide de la méthode tabou. Elle montre que l'organisation de la mémoire de cas du type arbres de prototypes accélère considérablement son fonctionnement par rapport à une technique du type plus proches voisins classique, sans pour autant altérer les performances du système Case retrieval is a crucial part of any CBR system as it pro­ vides the raw material for constructive solution generation by the reasoner. Case memories, as substrates for retrieval, are based on one of two main techniques: nearest neighbours classifi­ cation or common feature indexing. While the former admits the incorporation of sophisticated similarity functions for accurate case retrieval, the latter provides rapid access to the stored cases. In this paper, we propose a case memory based on template trees. For this reason, we introduce the dynamic template trees, which are an adaptation of the classic template trees, originally introduced for classification in the pattern recognition field. They combine the benefits of both major approaches to case memory organisation. The hierarchical organisation of cases speeds-up case acquisition as well as case retrieval. Moreover, as they rely on the integration of an explicit similarity function, they maintain the advantages of nearest neighbour memories. Further, they can be iteratively. Results from experimental evaluation in case-based optimisation of the NP-hard capacitated facility loca­ tion problem show that the proposed memory organisation exhibits a considerably better scale-up behaviour than does a conventional flat list memory. This scale-up is achieved without degrading solution quality.