US 9,805,290 B2Granted

Skeleton data point clustering

AssigneeGoogle Inc.

InventorsKrzysztof Marcin Choromanski, Sanjiv Kumar

Life of this patent

Estimating the term…

Loading patent…

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for clustering data points. One of the methods includes maintaining data representing a respective ordered tuple of skeleton data points for each of a plurality of clusters. One or more intersecting clusters are determined for a new data point. An updated tuple of skeleton data points is generated for an updated cluster by selecting updated skeleton data points, including selecting the new data point or an existing jth skeleton data point of one of the one or more intersecting clusters according to which random value, of the jth random value for the new data point or the random value for the jth existing skeleton data point, is closest to a limiting value. The new data point is then assigned to the updated cluster.

Claims9

Dependent claims

A computer-implemented method of assigning a new data point to a cluster, the method comprising:

maintaining a respective ordered tuple of skeleton points for each of one or more clusters of data points, each skeleton point of each respective tuple being one of the data points of the corresponding cluster, wherein each cluster has more total data points than skeleton points, wherein each tuple has M or more skeleton points, where M is greater than three, and wherein each skeleton point at each position in each cluster has a respective associated random value;
receiving the new data point;
identifying two or more intersecting clusters for the new data point, each intersecting cluster being a cluster having at least a threshold number of skeleton points that are within a threshold distance of the new data point;
generating, for the new data point, an ordered tuple of M random values;
generating a new cluster to replace the two or more intersecting clusters, including:
generating a new ordered tuple of M skeleton points for the new cluster, including selecting as the skeleton point in the j-th position in the new tuple, for 1≦j≦M, either (i) the new data point or (ii) a skeleton point in the j-th position of the tuple of one of the two or more intersecting clusters, including
selecting the skeleton point associated with the closest random value to a limiting value among the random values associated with the j-th positions in the tuples if the closest random value is closer to the limiting value than the j-th random value of the new data point, or
selecting the new data point otherwise;
and
associating as the random value of each skeleton point at each position in the new tuple either (i) the random value of the skeleton point selected for the position if a skeleton point was selected or (ii) the random value at the corresponding position in the tuple of random values of the new data point otherwise;
replacing the two or more intersecting clusters with the new cluster, the new cluster having as data points all the data points of the two or more intersecting clusters;
and
assigning the new data point to the new cluster.

10 more elements

A system comprising:

one or more computers and one or more non-transitory storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
maintaining a respective ordered tuple of skeleton points for each of one or more clusters of data points, each skeleton point of each respective tuple being one of the data points of the corresponding cluster, wherein each cluster has more total data points than skeleton points, wherein each tuple has M or more skeleton points, where M is greater than three, and wherein each skeleton point at each position in each cluster has a respective associated random value;
receiving a new data point;
identifying two or more intersecting clusters for the new data point, each intersecting cluster being a cluster having at least a threshold number of skeleton points that are within a threshold distance of the new data point;
generating, for the new data point, an ordered tuple of M random values;
generating a new cluster to replace the two or more intersecting clusters, including:
generating a new ordered tuple of M skeleton points for the new cluster, including selecting as the skeleton point in the j-th position in the new tuple, for 1≦j≦M, either (i) the new data point or (ii) a skeleton point in the j-th position of the tuple of one of the two or more intersecting clusters, including
selecting the skeleton point associated with the closest random value to a limiting value among the random values associated with the j-th positions in the tuples if the closest random value is closer to the limiting value than the j-th random value of the new data point, or
selecting the new data point otherwise;
and
associating as the random value of each skeleton point at each position in the new tuple either (i) the random value of the skeleton point selected for the position if a skeleton point was selected or (ii) the random value at the corresponding position in the tuple of random values of the new data point otherwise;
replacing the two or more intersecting clusters with the new cluster, the new cluster having as data points all the data points of the two or more intersecting clusters;
and
assigning the new data point to the new cluster.

11 more elements

One or more non-transitory computer-readable storage media encoded with instructions that, when executed by one or more computers, cause the one or more computers to perform operations comprising:

maintaining a respective ordered tuple of skeleton points for each of one or more clusters of data points, each skeleton point of each respective tuple being one of the data points of the corresponding cluster, wherein each cluster has more total data points than skeleton points, wherein each tuple has M or more skeleton points, where M is greater than three, and wherein each skeleton point at each position in each cluster has a respective associated random value;
receiving a new data point;
identifying two or more intersecting clusters for the new data point, each intersecting cluster being a cluster having at least a threshold number of skeleton points that are within a threshold distance of the new data point;
generating, for the new data point, an ordered tuple of M random values;
generating a new cluster to replace the two or more intersecting clusters, including:
generating a new ordered tuple of M skeleton points for the new cluster, including selecting as the skeleton point in the j-th position in the new tuple, for 1≦j≦M, either (i) the new data point or (ii) a skeleton point in the j-th position of the tuple of one of the two or more intersecting clusters, including
selecting the skeleton point associated with the closest random value to a limiting value among the random values associated with the j-th positions in the tuples if the closest random value is closer to the limiting value than the j-th random value of the new data point, or
selecting the new data point otherwise;
and
associating as the random value of each skeleton point at each position in the new tuple either (i) the random value of the skeleton point selected for the position if a skeleton point was selected or (ii) the random value at the corresponding position in the tuple of random values of the new data point otherwise;
replacing the two or more intersecting clusters with the new cluster, the new cluster having as data points all the data points of the two or more intersecting clusters;
and
assigning the new data point to the new cluster.

10 more elements

Dependencies are inferred from the claim text.