COMPRESSION OF DATA PARTITIONED INTO CLUSTERS

• US 20130031063A1
• Filed: 07/19/2012
• Published: 01/31/2013
• Est. Priority Date: 07/26/2011
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Vlachos, Michail, Freris, Nikolaos
• Application Number:
  US13/552,916
• Publication Number:
  US 20130031063A1
• Time in Patent Office: Days
• US Class Current: 707/693
• CPC Class Codes: G06F 18/23213 with fixed number of clusters, e.g. K-means clustering
• CPC Class Codes: G06F 18/24137 Distances to cluster centroïds
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: H04N 19/124 Quantisation

Abstract

The invention notably relates to a computer-implemented method for compressing data. The data is partitioned into clusters of pieces of data resulting from K-means clustering. Each cluster has a centroid. The method comprises applying (S10) a compression scheme to the data. The compression scheme preserves the centroid of each cluster and reduces the variance of each cluster. The method also comprises rescaling (S20) the data by moving the pieces of data towards the centroid of their cluster. Such a method improves the compression of data partitioned into clusters.

Claims

1. A computer-implemented method for compressing data, wherein the data are partitioned into clusters of pieces of data, resulting from a K-means clustering of the data, each cluster having a centroid, the method comprising:

applying a compression scheme to data that preserves a centroid of each respective cluster and reduces variance of each cluster; and

rescaling the data by moving pieces of data towards the centroid of the respective cluster.

2. The method of claim 1, wherein the rescaling comprises determining a key (α

) that is a number in interval (0,

     1) and moving each piece of data by an affine transformation having the centroid of the cluster of the piece of data as origin and the key (α

) as factor.

3. The method of claim 2, wherein determining a key comprises determining for each cluster a minimal box that contains all pieces of data of the cluster and determining, as the key, a largest number in the interval (0, 1) for which, for the box of each cluster, for each other cluster, a distance between the centroid of the other cluster and a point of the box which is closest to said centroid of said other cluster is larger than a distance between the centroid of the cluster of the box and said point.

4. The method of claim 2, wherein the method further comprises storing the key.

5. The method of claim 1, wherein the compression scheme is, for each cluster, a quantization performed on the cluster.

6. The method of claim 5, wherein the compression scheme is a MMSE (Minimum Mean Square Error) quantization.

7. The method of claim 6, wherein the compression scheme is a multi-bit MMSE quantization.

8. The method of claim 7, wherein the compression scheme comprises, for each cluster, a determination of an optimal number of bits allocated for the cluster.

9. The method of claim 1, wherein the method further comprises, prior to the applying and the rescaling, performing K-means clustering of the data using one of Lloyd'"'"'s algorithm and a Kmeans++ algorithm.

10. A computer-implemented method for decompressing data, wherein data is partitioned into clusters of pieces of data, resulting from a K-means clustering of the data, each cluster having a centroid, the method comprising:

rescaling data by moving pieces of data away from a centroid of the respective cluster.

11. A computer readable storage medium having recorded thereon a computer program for compressing data, wherein the data are partitioned into clusters of pieces of data, resulting from a K-means clustering of the data, each cluster having a centroid, the method comprising:

applying a compression scheme to data that preserves a centroid of each respective cluster and reduces variance of each cluster; and

rescaling the data by moving pieces of data towards the centroid of the respective cluster.