Whole page personalization with cyclic dependencies

Patent metadata

Field	Value
Publication number	US-2021034687-A1
Application number	US-202017073202-A
Country	US
Kind code	A1
Filing date	Oct 16, 2020
Priority date	Jan 31, 2017
Publication date	Feb 4, 2021
Grant date	—

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 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;
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.

3 . The system of claim 1 , wherein the computing instructions are further configured to perform:
upon identifying the cyclic dependency in the undirected graph, processing one or more inferences over the cyclic dependency for each of the at least three of the nodes; and conducting iterations of processing the one or more inferences over the cyclic dependency for each pair of nodes of the at least three of the nodes.

4 . The system of claim 3 , wherein the computing instructions are further configured to perform:
selecting a configuration of a pair of nodes when the configuration converges before a number of the iterations conducted for the each pair of nodes exceeds a predetermined number of iterations.

5 . The system of claim 3 , wherein the computing instructions are further configured 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 nodes exceeds a predetermined number of 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 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 are further configured to run on the one or more processors and 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.

8 . The system of claim 7 , wherein the computing instructions are further configured 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 are further configured 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 are further configured 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 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; 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.

14 . The method of claim 12 , further comprising:
upon identifying the cyclic dependency in the undirected graph, processing one or more inferences over the cyclic dependency for each of the at least three of the nodes; and conducting iterations of processing the one or more inferences over the cyclic dependency for each pair of nodes of the at least three of the nodes.

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

16 . The method of claim 14 , further comprising:
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 nodes exceeds a predetermined number of iterations.

17 . The method of claim 12 , 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 nodes of the at least three of the nodes representing content located below a fold of the webpage.

18 . The method of claim 12 , further comprising:
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.

19 . The method of claim 18 , further comprising, 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.

20 . The method of claim 18 , further comprising, upon detection of the deadlock configuration:
retrieving one or more historical dead lock configurations from a memory; breaking the dead lock configuration by res

Assignees

• Walmart Apollo Llc

Inventors

• Achan Kannan
• Korpeoglu Evren
• Manoharan Shirpaa

Classifications

• G06F16/9577 Primary

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

• G06F16/9024 Primary

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

• G06F16/958

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

• G06Q10/067

  Enterprise or organisation modelling · CPC title

• G06Q30/0241

  Advertisements · CPC title