Back to results
US 10,120,838 B2Granted
Systems and methods for weighted sampling
AssigneeFacebook, Inc.
InventorJeffrey 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.
Claims17
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 unannotated web pages from which to generate a sample set of m unannotated web pages, wherein n≥m, each unannotated web page xi of the data set X is associated with a URL posted to a posting-based newsfeed of a social networking system by one or more users of the social networking system, each unannotated web page xi of the data set X has a weight wi associated with the unannotated web page xi, the weight wi of each unannotated web page xi is indicative of an importance of the unannotated web page xi, and the data set X comprises data generated by the social networking system;
- assigning each unannotated web page in the data set X with a random score si based on the weight wi associated with the unannotated web page xi, wherein the random score si is generated according to the following formula:
- si=r1/wi, where r is a [0,1] real value drawn uniformly at random;
- identifying the m unannotated web pages in the data set X, wherein the m unannotated web pages have assigned scores that are higher than scores assigned to remaining unannotated web pages of the data set X;
- automatically identifying a set of annotations for the m unannotated web pages based on a scraper process, each unannotated web page of the m unannotated web pages being associated with at least one annotation of the set of annotations;
- and
- providing the m unannotated web pages and the set of annotations for presentation in a web page panel for review by an operator.
7 more elements
A non-transitory 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 unannotated web pages from which to generate a sample set of m unannotated web pages, wherein n≥m, each unannotated web page xi of the data set X is associated with a URL posted to a posting-based newsfeed of a social networking system by one or more users of the social networking system, each unannotated web page xi of the data set X has a weight wi associated with the unannotated web page xi, the weight wi of each unannotated web page xi is indicative of an importance of the unannotated web page xi, and the data set X comprises data generated by the social networking system;
- assigning each unannotated web page xi in the data set X with a random score si based on the weight wi associated with the unannotated web page xi, wherein the random score si is generated according to the following formula:
- si=r1/wi, where r is a [0,1] real value drawn uniformly at random;
- identifying the m unannotated web pages in the data set X, wherein the m unannotated web pages have assigned scores that are higher than scores assigned to remaining unannotated web pages of the data set X;
- automatically identifying a set of annotations for the m unannotated web pages based on a scraper process, each unannotated web page of the m unannotated web pages being associated with at least one annotation of the set of annotations;
- and
- providing the m unannotated web pages and the set of annotations for presentation in a web page panel for review by an operator.
4 more elements
A computer implemented method comprising:
- identifying, by a computer system, a data set X of n unannotated web pages from which to generate a sample set of m unannotated web pages, wherein n≥m, each unannotated web page xi of the data set X is associated with a URL posted to a posting-based newsfeed of a social networking system by one or more users of the social networking system, each unannotated web page xi of the data set X has a weight wi associated with the unannotated web page xi, and the data set X comprises data generated by the social networking system;
- assigning, by the computer system, each unannotated web page in the data set X with a random score si based on the weight wi associated with the unannotated web page xi, wherein the random score si is generated according to the following formula:
- si=r1/wi, where r is a [0,1] real value drawn uniformly at random;
- identifying, by the computer system, the m unannotated web pages in the data set X, wherein the m unannotated web pages have assigned scores that are higher than scores assigned to remaining unannotated web pages of the data set X;
- automatically identifying a set of annotations for the m unannotated web pages based on a scraper process, each unannotated web page of the m unannotated web pages being associated with at least one annotation of the set of annotations;
- and
- providing the m unannotated web pages and the set of annotations for presentation in a web page panel for review by an operator.
4 more elements
Dependencies are inferred from the claim text.