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.
5. The method of claim 1, wherein said generating a reduced dimensionality cluster comprises a singular value decomposition further comprising the steps of: producing a transformation matrix and eigenvalues of the transformation matrix for said each cluster; and selecting a subset of the eigenvalues including the largest eigenvalues; wherein the dimensionality reduction information includes the transformation matrix and the subset of the eigenvalues.