Frequent markup techniques for use in native advertisement placement
View Patent ↗Techniques are provided that include obtaining a Document Object Model of an HTML document, such as a web page of a publisher. Elements of the Document Object Model may be identified that are associated with native advertisement placement candidate containers. Based at least in part on analysis associated with the Document Object Model, and utilizing at least some of the identified elements, one or more native advertisement placement candidate containers may be determined. Some techniques may utilize, in the analysis, construction and utilization of a suffix tree of a string of tags comprising all tags in the Document Object Model. Some techniques may utilize, in the analysis, a node flattening technique in connection with the Document Object Model.
1. A system comprising one or more processors and a non-transitory storage medium comprising program logic for execution by the one or more processors, the program logic comprising:
a native advertisement placement engine that:
obtains a Document Object Model of an HTML document;
identifies Document Object Model elements, of the Document Object Model, associated with native advertisement placement candidate containers;
identifies, with the Document Object Model, HTML tag sequences that include at least L tags, where L is a specified number, repeat at least R times, where R is a specified number, and all correspond to a single element of the Document Object Model;
constructs a suffix tree of a string of tags comprising all tags in the Document Object Model;
performs a traversal of the suffix tree, beginning with a root node, and computes, for each node that is non-root and non-leaf, a number of leaf nodes of the each node;
analyzes the Document Object Model by performing a recursion of the suffix tree and pruning the recursion when the number of leaf nodes of the each node is less than R; and
based at least in part on the analysis associated with the Document Object Model, and utilizing at least some of the identified elements, determines, within the Document Object Model, one or more native advertisement placement candidate containers.
2. The system of claim 1 , wherein the HTML document is a web page.
3. The system of claim 1 , wherein suffix trees are utilized in identifying the HTML tag sequences.
4. The system of claim 3 , wherein computation utilizing suffix trees affords linear computational complexity in identification of tag sequences.
5. The system of claim 3 , wherein identifying Document Object Model elements, of the Document Object Model and associated with native advertisement placement candidate containers, comprises constructing a suffix tree of a string of tags comprising all tags in the Document Object Model.
6. The system of claim 1 , wherein L and R are parameters that are tuned at least in part to optimize system performance.
7. The system of claim 1 , comprising utilizing a node flattening technique in identifying HTML tag sequences.
8. The system of claim 1 , wherein the identified candidate containers relate to content with which native advertisements may be associated.
9. The system of claim 1 , wherein the identified candidate containers relate to locations or relative locations on the web page for native advertisement placement.
10. The system of claim 1 , comprising filtering determined candidate containers based on one or more parameters associated with at least one of (1) candidate containers and (2) native advertisements to be associated with candidate containers.
11. The system of claim 1 , comprising filtering determined candidate containers based on at least one of (1) candidate container size, (2) size of a meta-container associated with multiple candidate containers, (3) number of element types included within a candidate container, (4) anticipated display location of native advertisements associated with candidate containers, and (5) topology of the Document Object Model.
12. A method comprising:
obtaining a Document Object Model of a web page;
identifying Document Object Model elements, of the Document Object Model, associated with native advertisement placement candidate containers, comprising:
identifying, with the Document Object Model, HTML tag sequences that include at least L tags, where L is a specified number, repeat at least R times, where R is a specified number, and all correspond to a single element of the Document Object Model:
constructing a suffix tree of a string of tags comprising all tags in the Document Object Model;
performing a traversal of the suffix tree, beginning with a root node, and computing, for each node that is non-root and non-leaf, a number of leaf nodes of the each node;
analyzing the Document Object Model by performing a recursion of the suffix tree and pruning the recursion when the number of leaf nodes of the each node is less than R; and
based at least in part on the analysis relating to the Document Object Model, and utilizing at least some of the identified elements, determining, within the Document Object Model, one or more native advertisement placement candidate containers.
13. The method of claim 12 , wherein L and R are parameters that are tuned at least in part to optimize native advertisement placement performance.
14. The method of claim 12 , wherein identifying the HTML tag sequences comprises computation utilizing a Document Object Model node flattening technique.
15. The method of claim 12 , wherein the analysis comprises constructing and utilizing a suffix tree of a string of tags comprising all tags in the Document Object Model.
16. The method of claim 12 , comprising filtering determined candidate containers based on one or more parameters associated with at least one of (1) candidate containers and (2) native advertisements to be associated with candidate containers.
17. The method of claim 12 , comprising filtering determined candidate containers based on at least one of (1) candidate container size, (2) size of a meta-container associated with multiple candidate containers, (3) number of element types included within a candidate container, (4) anticipated display location of native advertisements associated with candidate containers, and (5) topology of the Document Object Model.
18. A non-transitory computer readable storage medium or media tangibly storing computer program logic capable of being executed by a computer processor, the program logic comprising:
native advertisement placement engine logic for:
obtaining a Document Object Model of a web page;
identifying Document Object Model elements, of the Document Object Model, associated with native advertisement placement candidate containers, comprising:
identifying, with the Document Object Model, HTML tag sequences that include at least L tags, where L is a specified number, repeat at least R times, where R is a specified number, and all correspond to a single element of the Document Object Model;
constructing a suffix tree of a string of tags comprising all tags in the Document Object Model;
performing a traversal of the suffix tree, beginning with a root node, and computing, for each node that is non-root and non-leaf, a number of leaf nodes of the each node;
analyzing the Document Object Model by performing a recursion of the suffix tree and pruning the recursion when the number of leaf nodes of the each node is less than R; and
based at least in part on the analysis relating to the Document Object Model, and utilizing at least some of the identified elements, determining, within the Document Object Model, one or more native advertisement placement candidate containers.