6. The method of claim 5, for searching for k most similar records to specified data using the reduced dimensionality index, comprising the steps of: associating specified data to said one or more clusters, based on stored clustering information; projecting the specified data onto a subspace for an associated cluster based on stored dimensionality reduction information for the associated cluster; generating dimensionality reduction information including an orthogonal complement for projected specified data, in response to said projecting; searching, via the index, for the associated cluster having k most similar records to the projected specified data; determining if any other associated cluster can include any of k most similar records to the projected specified data; and repeating said searching on said any cluster that can include any of the k most similar records to the specified data.
6. The method of claim 5, for searching for k most similar records to specified data using the reduced dimensionality index, comprising the steps of: associating specified data to said one or more clusters, based on stored clustering information; projecting the specified data onto a subspace for an associated cluster based on stored dimensionality reduction information for the associated cluster; generating dimensionality reduction information including an orthogonal complement for projected specified data, in response to said projecting; searching, via the index, for the associated cluster having k most similar records to the projected specified data; determining if any other associated cluster can include any of k most similar records to the projected specified data; and repeating said searching on said any cluster that can include any of the k most similar records to the specified data. 7. The method of claim 6, wherein said searching, via the index, for the associated cluster further comprises the step of: computing the distances (D) between k nearest neighbors in the associated cluster and the projected specified data as a function of a mismatch index .delta..sup.2 wherein, EQU .delta..sup.2 (template, element)=D.sup.2 (projected.sub.-- template, element)+.SIGMA..parallel.orthogonal.sub.-- complement.parallel..sup.2. 8.