Computing nearest neighbors in real time

The nearest-neighbor method can successfully be applied to correct possible errors induced into bit strings transmitted over noisy communication channels or to classify samples into a predefined set of categories. These two applications are investigated under real-time constraints, when the deadlines imposed can dramatically alter the quality of the solution unless a parallel model of computation (in these cases, a linear array of processors) is used. We also study a class of real-time computations, referred to as reactive real-time systems, that are particularly sensitive to the first time constraint imposed.