Pattern Analysis & Applications (2000)3:19–30! 2000 Springer-Verlag London Limited Nearest Neighbour Editing and Condensing Tools–Synergy Exploitation

Abstract: The objective of this study has been to explore and exploit the synergy among the Nearest Neighbour (NN) editing and condensing tools previously reported in the literature in order to facilitate the use of NN techniques in near real-time applications. The extraordinary progress in the computer field has made NN techniques, once considered impractical from a computational viewpoint, feasible for consideration in time-constrained, real-world applications. This study accordingly addresses the issue of minimising the computational resource requirements of NN techniques, memory as well as time, through the use of prototype reduction techniques such as Minimal Consistent Set (MCS) selection while preserving the performance quality through suitable editing techniques, such as Proximity Graphs (PG). The tools employed in this investigation are first described briefly. Results of experiments conducted on well known data sets in the literature with various combinations of editing and condensing tools are then presented and discussed to assess the benefits of synergy among these tools. These results demonstrate the potential benefits of such synergy, and highlight the desirability of a more thorough exploration of combinations of other alternative editing and condensing tools that have been reported in the literature over the past few decades