Systems and methods for weighted sampling
AssigneeFacebook, Inc.
InventorJeff Pasternack
Life of this patent
Estimating the term…
Abstract
Techniques provided herein allow for a plurality of weighted samplings without replacement to be performed in O(n) time. According to some embodiments, the weighted sampling without replacement may be performed on a data set X of data elements {x1, x2, x3, . . . , xn}, where each data element xi of the data set X has an associated weight wi. The data set X may comprise data generated by a social networking system. Each data element xi in the data set X may be assigned with a random score si based on the weight wi associated with the data element xi. The random score si can be used to perform weighted sampling without replacement.
Claims20
A computer system comprising:
- at least one processor;
- and
- a memory storing instructions configured to instruct the at least one processor to perform:
- identifying a data set X of n data elements from which to generate a sample set of m data elements, wherein n≧m, each data element xi of the data set X has a weight wi associated with the data element xi, and the data set X comprises data generated by a social networking system;
- assigning each data element xi in the data set X with a random score si based on the weight wi associated with the data element xi;
- and
- identifying the m data elements in the data set X, wherein the m data elements have assigned scores that are higher than scores assigned to remaining data elements of the data set X.
A computer-storage medium storing computer-executable instructions that, when executed, cause a computer system to perform a computer-implemented method comprising:
- identifying a data set X of n data elements from which to generate a sample set of m data elements, wherein n≧m, each data element xi of the data set X has a weight wi associated with the data element xi, and the data set X comprises data generated by a social networking system;
- assigning each data element xi in the data set X with a random score si based on the weight wi associated with the data element xi;
- and
- identifying the m data elements in the data set X, wherein the m data elements have assigned scores that are higher than scores assigned to remaining data elements of the data set X.
A computer implemented method comprising:
- identifying, by a computer system, a data set X of n data elements from which to generate a sample set of m data elements, wherein n≧m, each data element xi of the data set X has a weight wi associated with the data element xi, and the data set X comprises data generated by a social networking system;
- assigning, by the computer system, each data element xi in the data set X with a random score si based on the weight wi associated with the data element xi;
- and
- identifying, by the computer system, the m data elements in the data set X, wherein the m data elements have assigned scores that are higher than scores assigned to remaining data elements of the data set X.
Dependencies are inferred from the claim text.