Generating computationally-efficient representations of large datasets

1. A method comprising:

receiving a request to apply a coverage algorithm to a large input dataset comprising a plurality of sets of elements, each set including one or more elements from a ground set of elements;

generating a computationally-efficient representation of the large dataset, comprising:

generating a reduced set of elements that contains fewer elements than the ground set of elements by removing elements from the ground set of elements based on a defined probability; and

generating the computationally-efficient representation by, for each element in the reduced set of elements:

determining whether the element appears in more than a threshold number of the plurality of sets; and

when the element appears in more than the threshold number of the plurality of sets, removing the element from sets in the plurality of sets until the element appears in only the threshold number of the plurality of sets;

applying the coverage algorithm to the computationally-efficient representation of the large input dataset to identify a subset of the plurality of sets; and

providing data identifying the subset of the plurality of sets in response to the received request.

2. The method of claim 1 , wherein generating the reduced set of elements comprises:

using a hashing function to determine a respective hash value for each element in the ground set of elements; and

removing each element from the ground set of elements whose hash value exceeds the defined probability.

3. The method of claim 2 , wherein generating the reduced set of elements comprises:

assigning each element to a respective machine;

for each element,

using, by the machine to which the element has been assigned, the hashing function to determine a hash value of the element;

if the hash value of the element is less than the defined probability, sending the hash value for the element and a degree of the element to a designated single machine, wherein the degree of the element is a number of sets to which the element belongs;

receiving, by the single machine, the hash values and the degrees of the elements that have hash values less than the defined probability; and

iteratively selecting elements for inclusion in the reduced set by increasing the hash value until a total degree of selected elements in the reduced set reaches a second predefined amount; and

wherein generating the computationally-efficient representation comprises:

for each element in the reduced set:

determining, by the machine to which the element has been assigned, whether the degree of the element exceeds the threshold number;

when the degree does not exceed the threshold number, sending data identifying the sets to which the element belongs to the single machine; and

when the degree exceeds the threshold number, sending data identifying the threshold number of sets to which the element belongs to the single machine;

receiving, by the single machine, the number of selected elements from the respective machines; and

generating, by the single machine, the computationally-efficient representation of the plurality of sets from the received elements.

4. The method of claim 1 , wherein the total size of the computationally-efficient representation of the plurality of sets of elements fits on memory of one machine.

5. The method of claim 1 , wherein the coverage algorithm is a k-cover algorithm.

6. The method of claim 1 , wherein the coverage algorithm is a set-cover algorithm.

7. The method of claim 1 , wherein the coverage algorithm is set-cover with outliers algorithm.

8. The method of claim 1 , wherein the coverage algorithm is a set-cover in iterations algorithm.

9. The method of claim 1 , wherein applying the coverage algorithm to the computationally-efficient representation of the large input dataset comprises:

applying the coverage algorithm to the computationally-efficient representation of the large input dataset in a large-scale computational framework.

10. The method of claim 9 , wherein the large-scale computational framework is a MapReduce model.

11. The method of claim 9 , wherein the large-scale computational framework is a RAM model.

12. The method of claim 9 , wherein the large-scale computational framework is a streaming model.

13. The method of claim 1 , wherein generating the computationally-efficient representation of the large input dataset comprises generating a representation that optimizes a running time of the coverage algorithm.

14. The method of claim 1 , wherein generating the computationally-efficient representation of the large input dataset comprises generating a representation that optimizes space usage.

15. The method of claim 1 , wherein generating the computationally-efficient representation of the large input dataset comprises generating a representation that optimizes an approximation guarantee of the coverage algorithm.

16. The method of claim 1 , wherein generating the computationally-efficient representation of the large input dataset comprises generating a representation that optimizes the number of rounds or passes required to identify the subset.

17. The method of claim 1 , wherein the probability is based on a total number of sets.

18. The method of claim 1 , wherein the threshold is based on a total number of sets.

19. A system comprising:

one or more computers; and

one or more storage devices storing instructions that are operable, when executed on the one or more computers, to cause the one or more computers to:

generate a computationally-efficient representation of a large input dataset, comprising:

generate a reduced set of elements that contains fewer elements than the ground set of elements by removing elements from the ground set of elements based on a defined probability; and

generate the computationally-efficient representation by, for each element in the reduced set of elements:

determine whether the element appears in more than a threshold number of the plurality of sets; and

when the element appears in more than the threshold number of the plurality of sets, remove the element from sets in the plurality of sets until the element appears in only the threshold number of the plurality of sets;

apply the coverage algorithm to the computationally-efficient representation of the large input dataset to identify a subset of the plurality of sets; and

provide data identifying the subset of the plurality of sets in response to the received request.

20. One or more non-transitory computer-readable storage mediums comprising instructions stored thereon that are executable by a processing device and upon such execution cause the processing device to perform operations of:

generating a computationally-efficient representation of a large input dataset, comprising:

generating a reduced set of elements that contains fewer elements than the ground set of elements by removing elements from the ground set of elements based on a defined probability; and

generating the computationally-efficient representation by, for each element in the reduced set of elements:

determining whether the element appears in more than a threshold number of the plurality of sets; and

when the element appears in more than the threshold number of the plurality of sets, removing the element from sets in the plurality of sets until the element appears in only the threshold number of the plurality of sets;

applying the coverage algorithm to the computationally-efficient representation of the large input dataset to identify a subset of the plurality of sets; and

providing data identifying the subset of the plurality of sets in response to the received request.