Bundling online content fragments for presentation based on content-specific metrics and inter-content constraints

1. A method performed by one or more processing devices for bundling, based on content-specific metrics and inter-content constraints, content fragments for presentation as online content, the method comprising:

computing, for candidate content fragments, a set of minimum contribution values based on a set of content-specific metrics and a set of maximum contribution values based on the set of content-specific metrics;

selecting, based on the sets of minimum and maximum contribution values, a subset of the candidate content fragments;

identifying values associated with the subset of the candidate content fragments, the values comprising a respective value of a reward for each candidate content fragment;

optimizing, subject to an inter-content constraint, a bundle-selection function of the values associated with the subset of the candidate content fragments to select a bundle of online content fragments from the subset of the candidate content fragments;

generating a customized web page comprising the bundle of online content fragments, wherein generating the customized web page comprises:

dividing the customized web page into a grid comprising grid sections;

identifying pairs of online content fragments in the bundle of online content fragments;

computing a respective conflict weight for each pair of online content fragments in the pairs, wherein the respective conflict weight of each pair indicates a degree of similarity or difference between online content fragments in the pair;

constructing a first conflict graph comprising (i) nodes representing the online content fragments in the bundle of online content fragments and (ii) edges representing the respective conflict weights for the pairs of online content fragments, wherein each edge of the first conflict graph has a weight corresponding to the respective conflict weight of the pair of online content fragments represented by adjacent nodes of the edge;

constructing a second conflict graph based on the first conflict graph, wherein the second conflict graph comprises the nodes and a subset of the edges, wherein the subset of the edges comprises those of the edges having respective weights exceeding a threshold; and

arranging the bundle of online content fragments in a grid section, of the grid sections of the customized web page, by solving a knapsack problem, wherein solving the knapsack problem comprises excluding at least one online content fragment per pair from each pair of online content fragments representing nodes that are adjacent in the second conflict graph; and

causing display of the customized web page via a user device to enable the user device to interact with the bundle of online content fragment arranged in the grid section of the customized web page.

2. The method of claim 1 , wherein the inter-content constraint comprises a threshold amount of similarity or diversity among the subset of the candidate content fragments, wherein the method further comprises computing a similarity or diversity among a pair of candidate content fragments from a Euclidean distance between a pair of vector representations corresponding to the pair of candidate content fragments.

3. The method of claim 1 , wherein the bundle-selection function comprises an objective function having a first term corresponding to the set of content-specific metrics and a second term corresponding to (i) a reward associated with the inter-content constraint or (ii) a penalty associated with the inter-content constraint, wherein applying the bundle-selection function comprises maximizing the bundle-selection function using values of the set of content-specific metrics for the bundle of online content fragments and values of the inter-content constraint for the bundle of online content fragments.

4. The method of claim 1 , wherein generating the customized web page further comprises:

updating the second conflict graph by removing a subset of nodes corresponding to the grid section; and

arranging the bundle of online content fragments in an additional grid section of the grid sections based on the second conflict graph as updated.

5. The method of claim 1 , wherein arranging the bundle of online content fragments in the grid section further comprises arranging distributing a subset of the bundle of online content fragments in the grid section such that a Steinberg inequality is satisfied, the Steinberg inequality having the subset of the bundle of online content fragments as input rectangles and the grid section as an input grid.

6. The method of claim 1 , wherein the set of content-specific metrics comprises one or more of a specified interaction with an online service, an amount of time that a user accesses the online service, and an amount of revenue generated by the user accessing an online service.

7. The method of claim 1 , wherein solving the knapsack problem includes consideration of a dimension constraint imposed by the grid section.

8. A system comprising:

a processing device; and

a non-transitory computer-readable medium communicatively coupled to the processing device, wherein the processing device is configured to execute program code stored in the non-transitory computer-readable medium and thereby perform operations comprising:

computing, for candidate content fragments, respective minimum contribution values based on a set of content-specific metrics and respective maximum contribution values based on the set of content-specific metrics,

selecting, based on the sets of minimum and maximum contribution values, a subset of the candidate content fragments;

identifying values associated with the subset of the candidate content fragments, the values comprising a respective value of a reward for each candidate content fragment;

optimizing, subject to an inter-content constraint, a bundle-selection function of the values associated with the subset of the candidate content fragments to select a bundle of online content fragments from the subset of the candidate content fragments;

generating a customized web page comprising the bundle of online content fragments, wherein generating the customized web page comprises:

dividing the customized web page into a grid comprising grid sections;

identifying pairs of online content fragments in the bundle of online content fragments;

computing a respective conflict weight for each pair of online content fragments in the pairs, wherein the respective conflict weight of each pair indicates a degree of similarity or difference between online content fragments in the pair;

constructing a first conflict graph comprising (i) nodes representing the online content fragments in the bundle of online content fragments and (ii) edges representing the respective conflict weights for the pairs of online content fragments, wherein each edge of the first conflict graph has a weight corresponding to the respective conflict weight of the pair of online content fragments represented by adjacent nodes of the edge;

constructing a second conflict graph based on the first conflict graph, wherein the second conflict graph comprises the nodes and a subset of the edges, wherein the subset of the edges comprises those of the edges having respective weights exceeding a threshold; and

arranging the bundle of online content fragments in a grid section, of the grid sections of the customized web page, by solving a knapsack problem, wherein solving the knapsack problem comprises excluding at least one online content fragment per pair from each pair of online content fragments representing nodes that are adjacent in the second conflict graph; and

causing display of the customized web page via a user device to enable the user device to interact with the bundle of online content fragment arranged in the grid section of the customized web page.

9. The system of claim 8 , wherein the inter-content constraint comprises a threshold amount of similarity or diversity among the subset of the candidate content fragments, wherein the operations further comprise computing a similarity or diversity among a pair of candidate content fragments from a Euclidean distance between a pair of vector representations corresponding to the pair of candidate content fragments.

10. The system of claim 8 , wherein the bundle-selection function comprises an objective function having a first term corresponding to the set of content-specific metrics and a second term corresponding to (i) a reward associated with the inter-content constraint or (ii) a penalty associated with the inter-content constraint, wherein applying the bundle-selection function comprises maximizing the bundle-selection function using values of the set of content-specific metrics for the bundle of online content fragments and values of the inter-content constraint for the bundle of online content fragments.

11. The system of claim 8 , wherein generating the customized web page further comprises:

updating the second conflict graph by removing a subset of nodes corresponding to the grid section; and

arranging the bundle of online content fragments in an additional grid section of the grid sections based on the second conflict graph as updated.

12. The system of claim 8 , wherein arranging the bundle of online content fragments in the grid section further comprises arranging distributing a subset of the bundle of online content fragments in the grid section such that a Steinberg inequality is satisfied, the Steinberg inequality having the subset of the bundle of online content fragments as input rectangles and the grid section as an input grid.

13. The system of claim 8 , wherein the set of content-specific metrics comprises one or more of a specified interaction with an online service, an amount of time that a user accesses the online service, and an amount of revenue generated by the user accessing an online service.

14. The system of claim 8 , wherein solving the knapsack problem includes consideration of a dimension constraint imposed by the grid section.

15. A non-transitory computer-readable medium having program code that is stored thereon and that is executable by a processing device for performing operations, the operations comprising:

a step for computing, for candidate content fragments, respective minimum contribution values based on a set of content-specific metrics and respective maximum contribution values based on the set of content-specific metrics;

a step for selecting, based on the sets of minimum and maximum contribution values, a subset of the candidate content fragments;

a step for identifying values associated with the subset of the candidate content fragments, the values comprising a respective value of a reward for each candidate content fragment;

a step for optimizing, subject to an inter-content constraint, a bundle-selection function of the values associated with the subset of the candidate content fragments to select a bundle of online content fragments from the subset of the candidate content fragments;

a step for generating a customized web page comprising the bundle of online content fragments, wherein generating the customized web page comprises:

dividing the customized web page into a grid comprising grid sections;

identifying pairs of online content fragments in the bundle of online content fragments;

computing a respective conflict weight for each pair of online content fragments in the pairs, wherein the respective conflict weight of each pair indicates a degree of similarity or difference between online content fragments in the pair;

constructing a first conflict graph comprising (i) nodes representing the online content fragments in the bundle of online content fragments and (ii) edges representing the respective conflict weights for the pairs of online content fragments, wherein each edge of the first conflict graph has a weight corresponding to the respective conflict weight of the pair of online content fragments represented by adjacent nodes of the edge;

constructing a second conflict graph based on the first conflict graph, wherein the second conflict graph comprises the nodes and a subset of the edges, wherein the subset of the edges comprises those of the edges having respective weights exceeding a threshold; and

arranging the bundle of online content fragments in a grid section, of the grid sections of the customized web page, by solving a knapsack problem, wherein solving the knapsack problem comprises excluding at least one online content fragment per pair from each pair of online content fragments representing nodes that are adjacent in the second conflict graph; and

a step for causing display of the customized web page via a user device to enable the user device to interact with the bundle of online content fragments arranged in the grid section of the customized web page.

16. The non-transitory computer-readable medium of claim 15 , wherein the inter-content constraint comprises a threshold amount of similarity or diversity among the subset of the candidate content fragments, wherein the operations further comprise a step for computing a similarity or diversity among a pair of candidate content fragments from a Euclidean distance between a pair of vector representations corresponding to the pair of candidate content fragments.

17. The non-transitory computer-readable medium of claim 15 , wherein the bundle-selection function comprises an objective function having a first term corresponding to the set of content-specific metrics and a second term corresponding to (i) a reward associated with the inter-content constraint or (ii) a penalty associated with the inter-content constraint, wherein the step for applying the bundle-selection function comprises maximizing the bundle-selection function using values of the set of content-specific metrics for the bundle of online content fragments and values of the inter-content constraint for the bundle of online content fragments.

18. The non-transitory computer-readable medium of claim 15 , wherein generating the customized web page further comprises:

updating the second conflict graph by removing a subset of nodes corresponding to the grid section; and

arranging the bundle of online content fragments in an additional grid section of the grid sections based on the second conflict graph as updated.

19. The non-transitory computer-readable medium of claim 15 , wherein arranging the bundle of online content fragments in the grid section further comprises arranging distributing a subset of the bundle of online content fragments in the grid section such that a Steinberg inequality is satisfied, the Steinberg inequality having the subset of the bundle of online content fragments as input rectangles and the grid section as an input grid.

20. The non-transitory computer-readable medium of claim 15 , wherein solving the knapsack problem includes consideration of a dimension constraint imposed by the grid section.