US 12,743,471 B1Granted

Clustering in a storage system

AssigneeVast Data Ltd.

InventorsEyal Gordon, Asaf Levy, Eitan Yaakobi, Sagi Grimberg, Roman Veinbrand

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method for clustering and re-clustering in a storage system, the method includes (a) randomly selecting a first number of sets of clusters of a vast number of clusters stored in the storage system; wherein the vast number of clusters comprises first clusters and second clusters, wherein each first cluster is generated regardless of similarities between members of the first cluster, wherein each second cluster is generated based on at least similarities between members of the second cluster; (b) for each set of clusters, calculating by a processing circuit, a set re-clustering score that is based on (i) a sparseness measure of each clusters of the set of clusters, and (ii) one or more inter-clusters relationship measure indicative of spatial relationships between the clusters of the set of clusters; (c) identifying, by the processing circuit and based on set re-clustering scores of the first number of sets of clusters, one or more sets of clusters to be re-clustered; (d) re-clustering each one or more sets of clusters to provide updated second clusters; and (e) storing the updated second clusters in the storage system.

Claims16

Dependent claims

A method for clustering and re-clustering in a storage system, the method comprises:

generating, by one or more processing circuits of one or more compute nodes of the storage system, first clusters without executing similarity calculations regarding the members of the first clusters;
randomly selecting, by the one or more processing circuits, a first number of sets of clusters of a plurality of clusters of a millions of clusters stored in the storage system, the plurality of clusters exhibit a spareness measure that exceeds a sparseness threshold;
wherein the millions of clusters comprises the first clusters and second clusters, wherein each second cluster is generated based on at least similarities between members of the second cluster;
for each set of clusters, calculating by the one or more processing circuits, a set re-clustering score that is based on (i) sparseness measure of each cluster of the set of clusters, and (ii) one or more inter-clusters relationship measure indicative of spatial relationships between the clusters of the set of clusters;
identifying, by the one or more processing circuits and based on set re-clustering scores of the first number of sets of clusters, one or more sets of clusters to be re-clustered;
re-clustering, by the one or more processing circuits, each one of the one or more sets of clusters to provide updated second clusters;
and
storing the updated second clusters in non-volatile memory units of the storage system.

5 more elements

A non-transitory computer readable medium for clustering and re-clustering in a storage system, the non-transitory computer readable medium stores instructions executable by a processing system for:

generating, by one or more processing circuits of one or mor compute nodes of the storage system, first clusters without executing similarity calculations regarding the members of the first clusters;
randomly selecting, by the one or more processing circuits, a first number of sets of clusters of a plurality of clusters of a millions of clusters stored in the storage system, the plurality of clusters exhibit a spareness measure that exceeds a sparseness threshold;
wherein the millions of clusters comprises second clusters and some of the first clusters, wherein each second cluster is generated based on at least similarities between members of the second cluster;
for each set of clusters, calculating by the one or more a processing circuits, a set re-clustering score that is based on (i) a sparseness measure of each cluster of the set of clusters, and (ii) one or more inter-clusters relationship measure indicative of spatial relationships between the clusters of the set of clusters;
identifying, by the one or more ss g circuits and based on set re-clustering scores of the first number of sets of clusters, one or more sets of clusters to be re-clustered;
and
re-clustering, by the one or more processing circuits, each one or more sets of clusters to provide updated second clusters;
and
storing the updated second clusters in non-volatile memory units of the storage system.

6 more elements

Dependencies are inferred from the claim text.