Compressing n-dimensional data
First Claim
Patent Images
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
16 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
- 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;
-
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.
- 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;
-
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. - View Dependent Claims (10, 11, 12, 13)
- one or more memory elements; and
-
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.
- one or more memory elements; and
-
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.
- 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;
-
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.
-
Specification