SYSTEMS AND METHODS FOR WEIGHTED SAMPLING

摘要

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.

主权项

1. 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.