Multidimensional data clustering and dimension reduction for indexing and searching

A program storage device readable by a machine which includes one or more reduced dimensionality indexes to multidimensional data, the program storage device tangibly embodying a program of instructions executable by the machine to perform method steps for representing multidimensional data, said method steps comprising:

• a) partitioning the multidimensional data into one or more clusters;
• b) generating and storing clustering information for said one or more clusters;
• c) generating one or more reduced dimensionality clusters and dimensionality reduction information for said one or more clusters;
• and
• d) storing the dimensionality reduction information;
• e) creating a hierarchy of reduced dimensionality clusters by recursively applying said steps a) through d);
• and
• f) generating and storing one or more low-dimensional indexes for clusters at a lowest level of said hierarchy.

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.

A computerized method of representing multidimensional data which includes spatial geographic information, said method comprising the steps of:

• a) partitioning the spatial geographic information into one or more clusters;
• b) generating and storing clustering information for said one or more clusters;
• c) generating one or more reduced dimensionality clusters and dimensionality reduction information for said one or more clusters;
• d) storing the dimensionality reduction information;
• e) creating a hierarchy of reduced dimensionality clusters by recursively applying said steps a) through d);
• and
• f) generating and storing one or more low-dimensional indexes for clusters at a lowest level of said hierarchy.

A computerized method of representing multidimensional data which includes point-of-sale transactions with associated geographic coordinates, said method comprising the steps of:

• a) partitioning the point-of-sales transactions into one or more clusters;
• b) generating and storing clustering information for said one or more clusters;
• c) generating one or more reduced dimensionality clusters and dimensionality reduction information for said one or more clusters;
• and
• d) storing the dimensionality reduction information.