Whole page personalization with cyclic dependencies

Patent metadata

Field	Value
Publication number	US-11609964-B2
Application number	US-202017073202-A
Country	US
Kind code	B2
Filing date	Oct 16, 2020
Priority date	Jan 31, 2017
Publication date	Mar 21, 2023
Grant date	Mar 21, 2023

Abstract

A system including one or more processors and one or more non-transitory computer-readable media storing computing instructions configured to run on the one or more processors and perform: modeling a webpage as a random field, wherein the random field comprises an undirected graph comprising nodes and edges; identifying a cyclic dependency in the undirected graph, wherein the cyclic dependency involves at least three of the nodes; breaking one or more of the edges of the undirected graph that connects the at least three of the nodes in the cyclic dependency; determining a probability of the webpage having exceeded a predetermined threshold based on compatibility functions of the edges, as updated; and sending instructions to display the webpage based at least in part on the probability of the webpage having exceeded the predetermined threshold. Other embodiments are described.

First claim

What is claimed is:

1. A system comprising:
one or more processors; and
one or more non-transitory computer-readable media storing computing instructions, when run on the one or more processors, cause the one or more processors to perform:
modeling a webpage as a random field, wherein the random field comprises an undirected graph comprising nodes and edges;
identifying a cyclic dependency in the undirected graph wherein the cyclic dependency involves at least three of the nodes;
processing one or more inferences over the cyclic dependency for each of the at least three of the nodes; and
iterating processing the one or more inferences over the cyclic dependency for each pair of the nodes of the at least three of the nodes;

breaking one or more of the edges of the undirected graph that connects the at least three of the nodes in the cyclic dependency;
after breaking the one or more of the edges, determining a probability of the webpage having exceeded a predetermined threshold based on compatibility functions of the edges; and
sending instructions to display the webpage based at least in part on the probability of the webpage having exceeded the predetermined threshold.

2. The system of claim 1 , wherein the cyclic dependency in the undirected graph comprises a set of nodes that influence more than one of the at least three of the nodes in the undirected graph, wherein a first node influences both a second node and a third node, and wherein the third node influences both the first node and the second node, and wherein the set of nodes comprise the first, second, and third nodes, and wherein the nodes comprise the set of nodes.

3. The system of claim 1 , wherein: further configured to perform:
each node of the at least three of the nodes in the cyclic dependency is set to be dependent on a previous node for a single iteration of the one or more inferences; and
iterating processing the one or more inferences further comprises, after an initial iteration is processed, repeating a new iteration cycle for multiple iterations to process the one or more inferences over the cyclic dependency.

4. The system of claim 3 , wherein the computing instructions, when run on the one or more processors, further cause the one or more processors to perform:
selecting a configuration of a pair of the nodes when the configuration of the pair of the nodes converges before a number of the iterations conducted for the each pair of the nodes exceeds a predetermined number of the iterations.

5. The system of claim 3 , wherein the computing instructions, when run on the one or more processors, further cause the one or more processors to perform:
selecting a configuration of a latest one of the iterations when the iterations do not result in convergence before a number of the iterations conducted for the each pair of the nodes exceeds a predetermined number of the iterations.

6. The system of claim 1 , wherein breaking the one or more of the edges of the undirected graph comprises:
breaking the one or more edges of the undirected graph connecting a pair of the nodes of the at least three of the nodes representing content located below a fold of the webpage.

7. The system of claim 1 , wherein the computing instructions, when run on the one or more processors, further cause the one or more processors to perform:
detecting a dead lock configuration between a first zone of a first node adjacent to a second zone of a second node in the undirected graph, wherein the first zone and the second zone are incompatible zones, and wherein the nodes comprise the first and second nodes.

8. The system of claim 7 , wherein the computing instructions, when run on the one or more processors, further cause the one or more processors to perform, upon detection of the dead lock configuration:
initiating a random restart of an initial node selection based on at least a weighted random sampling of the nodes in the undirected graph.

9. The system of claim 7 , wherein the computing instructions, when run on the one or more processors, further cause the one or more processors to perform, upon detection of the dead lock configuration:
retrieving one or more historical dead lock configurations from a memory;
breaking the dead lock configuration by resetting a probability node of the dead lock configuration based on the one or more historical dead lock configurations; and
initiating a random restart of an initial node selection of the one or more historical dead lock configurations.

10. The system of claim 7 , wherein the computing instructions, when run on the one or more processors, further cause the one or more processors to perform, upon detection of the dead lock configuration:
exploring the first zone of the first node in the undirected graph for other zones of the first node; and
breaking the dead lock configuration by exploiting one or more of the other zones of the first node, wherein the one or more of the other zones are compatible zones between the first node and the second node.

11. The system of claim 1 , wherein the compatibility functions quantify compatibility of the edges based on one or more goodness functions of pairs of the nodes.

12. A method being implemented via execution of computing instructions configured to run on one or more processors and stored at one or more non-transitory computer-readable media, the method comprising:
modeling a webpage as a random field, wherein the random field comprises an undirected graph comprising nodes and edges;
identifying a cyclic dependency in the undirected graph wherein the cyclic dependency involves at least three of the nodes;
processing one or more inferences over the cyclic dependency for each of the at least three of the nodes; and
iterating processing the one or more inferences over the cyclic dependency for each pair of the nodes of the at least three of the nodes;

breaking one or more of the edges of the undirected graph that connects the at least three of the nodes in the cyclic dependency;
after breaking the one or more of the edges, determining a probability of the webpage having exceeded a predetermined threshold based on compatibility functions of the edges; and
sending instructions to display the webpage based at least in part on the probability of the webpage having exceeded the predetermined threshold.

13. The method of claim 12 , wherein the cyclic dependency in the undirected graph comprises a set of nodes that influence more than one of the at least three of the nodes in the undirected graph, wherein a first node influences both a second node and a third node, and wherein the third node influences both the first node and the second node, and wherein the set of nodes comprise the first, second, and third nodes, and wherein the nodes comprise the set of nodes.

14. The method of claim 12 , wherein:
each node of the at least three of the nodes in the cyclic dependency is set to be dependent on a previous node for a single iteration of the one or more inferences; and
iterating processing the one or more inferences further comprises, after an initial iteration is processed, repeating a new iteration cycle for multiple iterations to process the one or more inferences over the cyclic dependency.

15. The method of claim 14 , further comprising:
selecting a configuration of a pair of the nodes when the configuration of the pair of the nodes converges before a number of the iterations conducted for the each pair of the nodes exceeds a predetermined number of the iterations.

16. The method of claim 14 , further comprising:
selecting a conf

Assignees

• Walmart Apollo Llc

Inventors

• Achan Kannan
• Korpeoglu Evren
• Manoharan Shirpaa

Classifications

• G06F16/958

  Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking · CPC title

• G06Q30/0277

  Online advertisement · CPC title

• G06F16/9577 Primary

  Optimising the visualization of content, e.g. distillation of HTML documents · CPC title

• G06Q30/00

  Commerce · CPC title

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title