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.
63. The computer program product of claim 51, for performing an exact search, comprising: means for causing a computer to effect associating specified data to one of the clusters based on stored clustering information; means for causing a computer to effect reducing the dimensionality of the specified data based on stored dimensionality reduction information for a reduced dimensionality version of a cluster, in response to said associating step; and means for causing a computer to effect searching, based on reduced dimensionality specified data, for the reduced dimensionality version of the cluster matching the specified data.