Back to results
US 2010/0169258 A1Published application
Scalable Parallel User Clustering in Discrete Time Window
AssigneeMicrosoft Corporation
InventorsJun Yan, Ning Liu, Lei Ji, Zheng Chen
Life of this patent
Estimating the term…
Loading patent…
Loading patent…
AssigneeMicrosoft Corporation
InventorsJun Yan, Ning Liu, Lei Ji, Zheng Chen
Estimating the term…
Described is an internet user clustering technology, such as useful in behavioral targeting, in which users are clustered together based on MinHash computations that produce signatures corresponding to users' internet-related activities. In one aspect, users are clustered together based on commonality of signatures between each set of signatures associated with each user. The signature sets and/or clusters may be associated with timestamps, whereby clusters may be determined for a given discrete time window or set of discrete time windows. To facilitate efficient processing, existing, prior signature sets of a user may be incrementally updated (e.g., daily), and/or the MinHash computations for users are partitioned among parallel computing machines. The timestamps may be used to selectively determine a cluster within a continuous time, a time window or set of time windows.
In a computing environment, a method comprising, processing internet-related data corresponding to users, including determining a signature set for each user, including performing MinHash computations for that user, and clustering together users having similar signature sets.
In a computing environment, a system comprising, a plurality of computing machines, each computing machine receiving internet-related data of different users for processing the internet-related data in parallel, each machine including a parallel MinHash computation mechanism that determines a signature set for a user that corresponds to the internet-related data, the signature set based on a computation of the user's internet-related data relative to permutations of combined internet related data of a plurality of users, and a clustering mechanism that clusters together users having similar signature sets.
One or more computer-readable media having computer-executable instructions, which when executed perform steps, comprising, processing internet-related data corresponding to a user, including performing MinHash computations for that user' internet-related data to determine a recent signature set for that user indicative of that user's activities, incrementally updating an existing signature set for that user with the recent signature set, and clustering together users having similar signature sets.
Dependencies are inferred from the claim text.