Sampling a set of data
AssigneeFacebook, Inc.
InventorsMichael Curtiss, Tudor Bosman
Life of this patent
Estimating the term…
Abstract
In one embodiment, a method includes receiving a search query by one or more computing devices. A set of data objects to search are identified, and then an operation is executed. The operation involves stepping through the set of data objects with a step size of N, and at each step determining whether the object is responsive to the query. If the end of the set is reached before Y data objects are determined to be responsive, and X or more data objects are determined to be responsive, then an estimate of the number of responsive data objects in the set is provided. Otherwise, N is modified and the operation is re-executed.
Claims18
A method comprising:
- by one or more computing devices, receiving a search query;
- by one or more computing devices, identifying a set of data objects to search based on the search query;
- and
- by one or more computing devices, executing an operation evaluating the search query on a first subset of the set of data objects, comprising:
- stepping through the set of data objects with a step size of N;
- determining, at each step, whether the data object at that step is responsive to the search query;
- counting the number of data objects that are determined to be responsive to the search query;
- and
- if the end of the set is reached after X or more data objects are determined to be responsive to the search query and before Y data objects are determined to be responsive to the search query:
- then multiplying the count of the data objects determined to be responsive to the search query by N and providing the result as an estimate of a number of data objects in the set that are responsive to the query;
- else modifying N and re-executing the operation on a second subset of the set of data objects,
- wherein N, X, and Y have pre-determined values based on a data-object type of the data objects in the set.
A method comprising:
- by one or more computing devices, receiving a search query;
- by one or more computing devices, identifying a set of data objects to search based on the search query;
- and
- by one or more computing devices, executing an operation evaluating the search query on a subset of the set of data objects, comprising:
- stepping through the set of data objects with a step size of N;
- determining, at each step, whether the data object at that step is responsive to the search query;
- counting the number of data objects that are determined to be responsive to the search query;
- and
- if the end of the set is reached after X or more data objects are determined to be responsive to the search query and before Y data objects are determined to be responsive to the search query:
- then providing as a search-result sample the data objects determined to be responsive to the query or links to the data objects determined to be responsive to the query;
- else modifying N and re-executing the operation on a second subset of the set of data objects,
- wherein N, X, and Y have pre-determined values based on a data-object type of the data objects in the set.
Dependencies are inferred from the claim text.