Sampling a set of data
View Patent ↗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.
1. 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.
2. The method of claim 1 , wherein modifying N comprises increasing N if Y data objects are determined to be responsive to the search query before the end of the set is reached.
3. The method of claim 2 , wherein increasing N comprises doubling N.
4. The method of claim 1 , wherein modifying N comprises decreasing N if the end of the set is reached and fewer than X data objects are determined to be responsive to the search query.
5. The method of claim 1 , wherein the data objects comprise web pages.
6. The method of claim 1 , wherein the data objects comprise user profiles of a social-networking system.
7. The method of claim 1 , wherein the data objects comprise photographs.
8. The method of claim 1 , wherein stepping through the set of data objects with step size N comprises stepping through the set of data objects with step size N using a memory addressing algorithm.
9. The method of claim 1 , further comprising, by one or more computing devices, searching the set of data objects based on the search query during the operation.
10. 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.
11. The method of claim 10 , wherein modifying N comprises increasing N if Y data objects are determined to be responsive to the search query before the end of the set is reached.
12. The method of claim 11 , wherein increasing N comprises doubling N.
13. The method of claim 10 , wherein modifying N comprises decreasing N if the end of the set is reached and fewer than X data objects are determined to be responsive to the search query.
14. The method of claim 10 , wherein the data objects comprise web pages.
15. The method of claim 10 , wherein the data objects comprise user profiles of a social-networking system.
16. The method of claim 10 , wherein the data objects comprise photographs.
17. The method of claim 10 , further comprising, by one or more computing devices, searching the set of data objects based on the search query concurrently with the operation.
18. The method of claim 10 , wherein stepping through the set of data objects with step size N comprises stepping through the set of data objects with step size N using a memory addressing algorithm.