Compressing n-dimensional data

• US 8,811,156 B1
• Filed: 11/14/2006
• Issued: 08/19/2014
• Est. Priority Date: 11/14/2006
• Status: Expired due to Fees

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Jiang, Qin, Rockwood, Troy D
• Primary Examiner(s): Nawaz, Asad
• Assistant Examiner(s): HARLEY, JASON A
• Application Number:
  US11/559,786
• Time in Patent Office: 2,835 Days
• Field of Search: 713/200, 382/240
• US Class Current: 370/225
• CPC Class Codes: H03M 7/3059 Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94

Abstract

In certain embodiments, a method for compressing n-dimensional data includes applying a data clustering algorithm to n-dimensional data to partition the n-dimensional data into one or more clusters. Each of the one or more clusters includes a cluster center and a cluster membership. The cluster membership includes an index of one or more cluster members of the cluster. The method further includes performing, for each of the one or more clusters, a subspace projection technique to generate, for each of the cluster members of the cluster, one or more projection coefficients for the cluster member.

Claims

1. A method for compressing n-dimensional data, comprising:

applying, by one or more processing modules, a data clustering algorithm to n-dimensional data to partition the n-dimensional data into one or more clusters, each of the one or more clusters comprising;

a cluster center; and

a cluster membership that comprises an index of one or more cluster members of the cluster;

performing, by the one or more processing modules, for each of the one or more clusters, a subspace projection technique to generate, for each of the cluster members of the cluster, one or more projection coefficients for the cluster member; and

performing, on the projection coefficients generated by the subspace projection technique, a tree-structured vector quantization;

wherein resulting compressed n-dimensional data comprises, for each of the one or more clusters, a quantized cluster center for the cluster, one or more basis vectors for the cluster, and projection coefficients for the cluster, and wherein the n-dimensional data comprises an n-dimensional graph that comprises a plurality of points, each dimension corresponding to an attribute of an event in a network,

the method further comprising determining an optimum number of clusters in which to partition the n-dimensional data by processing the n-dimensional data using a genetic algorithm, the genetic algorithm providing an indicator of an optimal number of clusters, the indicator of the optimal number of clusters being an input to the data clustering algorithm.

2. The method of claim 1, wherein the compressed n-dimensional data comprises, for each of the one or more clusters:

a quantized cluster center for the cluster;

a losslessly coded cluster membership for the cluster;

one or more basis vectors for the cluster; and

one or more projection coefficients for each cluster member of the cluster.

3. The method of claim 1, wherein the data clustering algorithm comprises a Fuzzy C-Mean algorithm.

4. The method of claim 1, comprising performing, for each of the one or more clusters, scalar quantization of the cluster center of the cluster.

5. The method of claim 1, wherein performing the subspace projection comprises, for each of the one or more clusters:

determining k−

1 fixed vectors generated from linearly independent polynomial vectors, k being less than n, determining a cluster-varying vector from the cluster center;

generating an orthonormal set of one or more basis vectors from the k linearly independent vectors; and

generating, for each cluster member of the cluster, k projection coefficients.

6. The method of claim 1, wherein performing the subspace projection comprises, for each of the one or more clusters:

generating, using a random projection technique, m independent vectors from the cluster members of the cluster;

selecting k vectors as basis vectors using a voting scheme based on geometric closeness, k being less than m, the k vectors being linearly independent;

generating an orthonormal set of one or more basis vectors from the k linearly independent vectors; and

generating, for each cluster member of the cluster, k projection coefficients.

7. The method of claim 1, wherein the n-dimensional data comprises intrusion detection data.

8. A method for compressing n-dimensional data, comprising:

applying, by one or more processing modules, a data clustering algorithm to n-dimensional data to partition the n-dimensional data into one or more clusters, each of the one or more clusters comprising;

a cluster center; and

a cluster membership that comprises an index of one or more cluster members of the cluster;

performing, by the one or more processing modules, for each of the one or more clusters, a subspace projection technique to generate, for each of the cluster members of the cluster, one or more projection coefficients for the cluster member; and

performing, on the projection coefficients generated by the subspace projection technique, a tree-structured vector quantization;

wherein resulting compressed n-dimensional data comprises, for each of the one or more clusters, a quantized cluster center for the cluster, one or more basis vectors for the cluster, and projection coefficients for the cluster, and wherein the n-dimensional data comprises an n-dimensional graph that comprises a plurality of points, each dimension corresponding to an attribute of an event in a network, wherein;

the method is performed by a node in a network; and

the method further comprises performing entropy coding of the compressed n-dimensional data to generate binary code for communicating the compressed n-dimensional data over a network to one or more other nodes.

9. A system for compressing n-dimensional data, the system comprising:

one or more memory elements; and

one or more microprocessors operable to;

apply a data clustering algorithm to n-dimensional data to partition the n-dimensional data into one or more clusters, each of the one or more clusters comprising;

a cluster center; and

a cluster membership that comprises an index of one or more cluster members of the cluster;

perform, for each of the one or more clusters, a subspace projection technique to generate, for each of the cluster members of the cluster, one or more projection coefficients for the cluster member; and

perform on the projection coefficients generated by the subspace projection technique, a tree-structured vector quantization;

wherein resulting compressed n-dimensional data is stored in the memory element and comprises, for each of the one or more clusters, a quantized cluster center for the cluster, one or more basis vectors for the cluster, and projection coefficients for the cluster, and wherein the n-dimensional data comprises an n-dimensional graph that comprises a plurality of points, each dimension corresponding to an attribute of an event in a network, and

wherein the one or more microprocessors are operable to determine an optimum number of clusters in which to partition the n-dimensional data by processing the n-dimensional data using a genetic algorithm, the genetic algorithm providing an indicator of an optimal number of clusters, the indicator of the optimal number of clusters being an input to the data clustering algorithm.

10. The system of claim 9, wherein the compressed n-dimensional data comprises, for each of the one or more clusters:

a quantized cluster center for the cluster;

a losslessly coded cluster membership for the cluster;

a basis vector for the cluster; and

one or more projection coefficients for each cluster member of the cluster.

11. The system of claim 9, wherein the one or more microprocessors are operable to perform the subspace projection by, for each of the one or more clusters:

determining k−

1 fixed vectors generated from linearly independent polynomial vectors, k being less than n, determining a cluster-varying vector from the cluster center;

generating an orthonormal set of one or more basis vectors from the k linearly independent vectors; and

generating, for each cluster member of the cluster, k projection coefficients.

12. The system of claim 9, wherein the one or more microprocessors are operable to perform the subspace projection by, for each of the one or more clusters:

generating, using a random projection technique, m independent vectors from the cluster members of the cluster;

selecting k vectors as basis vectors using a voting scheme based on geometric closeness, k being less than m, the k vectors being linearly independent;

generating an orthonormal set of one or more basis vectors from the k linearly independent vectors; and

generating, for each cluster member of the cluster, k projection coefficients.

13. The system of claim 9, wherein the n-dimensional data comprises intrusion detection data.

14. A system for compressing n-dimensional data, the system comprising:

one or more memory elements; and

one or more microprocessors operable to;

apply a data clustering algorithm to n-dimensional data to partition the n-dimensional data into one or more clusters, each of the one or more clusters comprising;

a cluster center; and

a cluster membership that comprises an index of one or more cluster members of the cluster;

perform, for each of the one or more clusters, a subspace projection technique to generate, for each of the cluster members of the cluster, one or more projection coefficients for the cluster member; and

perform on the projection coefficients generated by the subspace projection technique a tree-structured vector quantization;

wherein resulting compressed n-dimensional data is stored in the memory element and comprises, for each of the one or more clusters, a quantized cluster center for the cluster, one or more basis vectors for the cluster, and projection coefficients for the cluster, and wherein the n-dimensional data comprises an n-dimensional graph that comprises a plurality of points, each dimension corresponding to an attribute of an event in a network, wherein

the system is a node in a network; and

the one or more microprocessors are further operable to perform entropy coding of the compressed n-dimensional data to generate binary code for communicating the compressed n-dimensional data over a network to one or more other nodes.

15. A non-transitory computer-readable medium comprising logic for compressing n-dimensional data, the logic when executed by one or more processing modules operable to:

apply a data clustering algorithm to n-dimensional data to partition the n-dimensional data into one or more clusters, each of the one or more clusters comprising;

a cluster center; and

a cluster membership that comprises an index of one or more cluster members of the cluster;

perform, for each of the one or more clusters, a subspace projection technique to generate, for each of the cluster members of the cluster, one or more projection coefficients for the cluster member; and

perform, on the projection coefficients generated by the subspace projection technique, a tree-structured vector quantization;

wherein resulting compressed n-dimensional data comprises, for each of the one or more clusters, a quantized cluster center for the cluster, one or more basis vectors for the cluster, and projection coefficients for the cluster,

wherein the n-dimensional data comprises an n-dimensional graph that comprises a plurality of points, each dimension corresponding to an attribute of an event in a network, and wherein performing the subspace projection comprises, for each of the one or more clusters;

determining k−

1 fixed vectors generated from linearly independent polynomial vectors, k being less than n, determining a cluster-varying vector from the cluster center;

generating an orthonormal set of one or more basis vectors from the k linearly independent vectors; and

generating, for each cluster member of the cluster, k projection coefficients.

16. A non-transitory computer-readable medium comprising logic for compressing n-dimensional data, the logic when executed by one or more processing modules operable to:

apply a data clustering algorithm to n-dimensional data to partition the n-dimensional data into one or more clusters, each of the one or more clusters comprising;

a cluster center; and

a cluster membership that comprises an index of one or more cluster members of the cluster;

perform, for each of the one or more clusters, a subspace projection technique to generate, for each of the cluster members of the cluster, one or more projection coefficients for the cluster member; and

perform, on the projection coefficients generated by the subspace projection technique, a tree-structured vector quantization;

wherein resulting compressed n-dimensional data comprises, for each of the one or more clusters, a quantized cluster center for the cluster, one or more basis vectors for the cluster, and projection coefficients for the cluster,

wherein the n-dimensional data comprises an n-dimensional graph that comprises a plurality of points, each dimension corresponding to an attribute of an event in a network, and wherein performing the subspace projection comprises, for each of the one or more clusters;

generating, using a random projection technique, m independent vectors from the cluster members of the cluster;

selecting k vectors as basis vectors using a voting scheme based on geometric closeness, k being less than m, the k vectors being linearly independent;

generating an orthonormal set of one or more basis vectors from the k linearly independent vectors; and

generating, for each cluster member of the cluster, k projection coefficients.