51. A computer program product comprising: a computer usable medium having computer readable program code means embodied therein for representing multidimensional data, the computer readable program code means in said computer program product comprising: computer readable program code clustering means for causing a computer to effect (a) partitioning the multidimensional data into one or more clusters; computer readable program code means, coupled to said clustering means, for causing a computer to effect (b) generating and storing clustering information for said one or more clusters; computer readable program code dimensionality reduction means, coupled to said clustering means, for causing a computer to effect, (c) generating one or more reduced dimensionality clusters and dimensionality reduction information for said one or more clusters; computer readable program code means, coupled to said dimensionality reduction means, for causing a computer to (d) effect storing the dimensionality reduction information; computer readable program code means for causing a computer to effect creating a hierarchy of reduced dimensionality clusters by recursively applying said steps a) through d); and computer readable program code means for causing a computer to effect generating and storing one or more low-dimensional indexes for clusters at a lowest level of said hierarchy.
51. A computer program product comprising: a computer usable medium having computer readable program code means embodied therein for representing multidimensional data, the computer readable program code means in said computer program product comprising: computer readable program code clustering means for causing a computer to effect (a) partitioning the multidimensional data into one or more clusters; computer readable program code means, coupled to said clustering means, for causing a computer to effect (b) generating and storing clustering information for said one or more clusters; computer readable program code dimensionality reduction means, coupled to said clustering means, for causing a computer to effect, (c) generating one or more reduced dimensionality clusters and dimensionality reduction information for said one or more clusters; computer readable program code means, coupled to said dimensionality reduction means, for causing a computer to (d) effect storing the dimensionality reduction information; computer readable program code means for causing a computer to effect creating a hierarchy of reduced dimensionality clusters by recursively applying said steps a) through d); and computer readable program code means for causing a computer to effect generating and storing one or more low-dimensional indexes for clusters at a lowest level of said hierarchy. 62. The computer program product of claim 51, for searching for k records most similar to specified data, the method for searching comprising: means for causing a computer to effect identifying a cluster to which specified data belongs, based on the clustering information; means for causing a computer to effect reducing the dimensionality of the specified data based on the dimensionality reduction information for an identified cluster; means for causing a computer to effect generating dimensionality reduction information for reduced dimensionality specified data, in response to said reducing; means for causing a computer to effect searching the multidimensional index, using the dimensionality reduction information, for a reduced-dimensionality version of the cluster to which the specified data belongs; means for causing a computer to effect retrieving via the multidimensional index, the k most similar records in the cluster; means for causing a computer to effect identifying other candidate clusters which can contain records closer to the specified data than the farthest of the k most similar records retrieved; means for causing a computer to effect searching a closest other candidate cluster to the specified data, in response to said identifying step; and means for causing a computer to effect repeating said identifying and searching steps for all said other candidate clusters.