9. In a system including one or more reduced dimensionality indexes to multidimensional data, a method for searching for k records most similar to specified data, using the one or more indexes, the method comprising the steps of: identifying the specified data with a cluster based on clustering information, said cluster being a partition from an original data input set; after said identifying step, reducing a dimensionality of the specified data, based on dimensionality reduction information for an identified cluster; recursively applying said identifying and reducing steps until a corresponding lowest level of a hierarchy of reduced dimensionality clusters has been reached; generating dimensionality reduction information for reduced dimensionality specified data, in response to said reducing; and retrieving the .ltoreq.k records most similar to the specified data from the identified cluster using the one or more reduced dimensionality indexes, the dimensionality reduction information and the reduced dimensionality specified data.
17. The method of claim 9, further comprising the steps of: searching for candidate terminal clusters that can contain one or more of the k records most similar to the specified data at each level of the hierarchy of reduced dimensionality clusters starting from a terminal cluster at a lowest level of said hierarchy to which the specified data belongs; and for each candidate terminal cluster, performing an intra-cluster search for the k records most similar to the specified data.