# US 10,120,838 B2 · Systems and methods for weighted sampling > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,120,838 B2 - Document ID: US10120838B2 - Status: Granted - Kind: B2 - Application number: 13/951,441 - Filed: 2013-07-25 - Published: 2015-01-29 - Granted: 2018-11-06 - Earliest claimed: 2013-07-25 - Assignees: Facebook, Inc. - Applicants: Facebook, Inc. - Inventors: Jeffrey Pasternack - Web page: https://patentgrep.com/patent/US10120838B2 ## CPC - G06F 17/18: for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} - G06F 16/951: Indexing; Web crawling techniques - G06F 16/953: Querying, e.g. by the use of web search engines - G06F 16/958: Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking - G06Q 10/40: Business processes related to social networking or social networking services - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR ## 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. ## Claims ### Claim 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 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. ### Claim 2 (depends on 1) The computer system of claim 1, wherein the instructions are configured to instruct the at least one processor to further perform: generating random scores si. ### Claim 3 (depends on 2) The computer system of claim 2, wherein r is drawn with a random number generator. ### Claim 4 (depends on 1) The computer system of claim 1, wherein the identifying the m unannotated web pages comprises: using a Median of Medians algorithm to identify an mth highest score ŝ; and identifying a particular unannotated web page of the unannotated web pages xi in the data set X having a particular score si where si≥ŝ. ### Claim 5 (depends on 1) The computer system of claim 1, wherein the identifying the m unannotated web pages comprises performing a structured query language (SQL) query. ### Claim 6 (depends on 5) The computer system of claim 5, wherein the SQL query comprises a SELECT command configured to order data rows using scores assigned to the unannotated web pages of the set X. ### Claim 7 (depends on 6) The computer system of claim 6, wherein the SELECT command is further configured to limit the data rows to m rows. ### Claim 8 (depends on 1) The computer system of claim 1, wherein a probability of drawing the unannotated web page xi from the data set X is based on the associated weight wi. ### Claim 9 (depends on 1) The computer system of claim 1, wherein the identifying the data set X of n unannotated web pages comprises selecting the data set X. ### Claim 10 (depends on 1) The computer system of claim 1, wherein the identifying the data set X of n unannotated web pages comprises determining a set W including some or all of the weights associated with the data set X. ### Claim 11 (depends on 1) The computer system of claim 1, wherein the instructions are configured to instruct the at least one processor to further perform: determining a set W including some or all of the weights associated with the data set X. ### Claim 12 (depends on 1) The computer system of claim 1, wherein the data generated by the social networking system comprises data used for machine learning. ### Claim 13 (depends on 1) The computer system of claim 1, wherein the data generated by the social networking system comprises user behavior information. ### Claim 14 (depends on 1) The computer system of claim 1, wherein the weight wi of each unannotated web page is based on a number of impressions of each unannotated web page on the social networking system. ### Claim 15 (depends on 1) The computer system of claim 1, wherein the weight wi of each unannotated web page is based on a number of times each unannotated web page has been shared on the social networking system. ### Claim 16 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. ### Claim 17 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.