Identifying transient portions of web pages

• US 8,086,953 B1
• Filed: 12/19/2008
• Issued: 12/27/2011
• Est. Priority Date: 12/19/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gabber, Eran, Muthukrishnan, Shanmugavelayutham, Flaster, Michael, Pang, Ruoming
• Primary Examiner(s): Hong, Stephen
• Assistant Examiner(s): BLOOMQUIST, KEITH D
• Application Number:
  US12/340,343
• Time in Patent Office: 1,103 Days
• Field of Search: 715/229
• US Class Current: 715/229
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/957 Browsing optimisation, e.g. caching or content distillation
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 30/0241 Advertisements

Abstract

Systems, methods and computer readable media for identifying transient content in web pages. Transient content can be identified, for example, by parsing different versions of the same web page into tokens, and inserting fingerprints associated with the tokens into data structures. The data structures can be compared to each other to identify differences between the web pages, thereby identifying transient content associated with the web pages.

Claims

1. A method comprising:

retrieving a first version of a web page and a second version of the web page, the web page being associated with a website;

parsing the first version of the page into a first set of tokens and the second version of the web page into a second set of tokens;

inserting a first set of fingerprints associated with the first set of tokens into a first data structure, and a second set of fingerprints associated with the second set of tokens into a second data structure;

comparing the fingerprints included in the first and second data structures;

marking tokens whose associated fingerprints appear only in one data structure as transient;

identifying a path associated with every token in the web page;

identifying a subtree count comprising a number of times the path appears in other web pages associated with the website;

identifying a marked subtree count comprising a number of times the content associated with the path changes between versions of the respective web pages;

comparing the subtree count with the marked subtree count; and

determining whether the path is a transient path based upon the comparison.

2. The method of claim 1, wherein parsing comprises identifying the first set of tokens and the second set of tokens based upon the opening and closing of markup language tags or end-of-line tag in the respective versions of the web page.

3. The method of claim 2, wherein identifying the first and second sets of tokens further comprises:

pushing an opening tag onto the top of a stack;

matching a closing tag against the opening tag at the top of the stack;

popping the top entry of the stack; and

identifying the popped entry as a parent of a current token.

4. The method of claim 3, further comprising targeting advertisements on the portions of web pages which are not identified as transient portions of the said web page.

5. The method of claim 1, further comprising indexing the portions of the web page which are not identified as transient portions of said web page.

6. The method of claim 1, wherein comparing the fingerprints included in the first and second data structures comprises:

initializing a first and second bit vector, the first bit vector comprising a bit for each token in a first hash table, the second bit vector comprising a bit for each token in a second hash table;

comparing each fingerprint from the first set of fingerprints to fingerprints included in the second hash table;

if a fingerprint from the first set of fingerprints is not present in the second hash table, setting a corresponding bit in the first bit vector;

comparing each fingerprint from the second set of fingerprints to fingerprints included in the first hash table; and

if a fingerprint from the second set of fingerprints is not present in the first hash table, setting a corresponding bit in the second bit vector.

7. The method of claim 6, further comprising identifying the tokens associated with set bits in the bit vector as transient portions of the web page.

8. The method of claim 7, further extending areas of transient tokens to include the tokens associated with enclosing HTML tags.

9. The method of claim 6, further comprising:

identifying a path associated with every token in the web page;

determining whether the path associated with the web page exists on a second web page associated with the website; and

identifying the content associated with the path in the second web page as transient content based upon the determination.

10. The method of claim 1, wherein a path is identified as a transient path when the number of times that the content associated with the path between versions of the respective web pages is greater than the number of times the path appears in other web pages associated with the website.

11. The method of claim 1, wherein a path is identified as a transient path when a ratio between the number of times that the content associated with the path between versions of the respective web pages divided by the number of times the path appears in other web pages associated with the website is greater than a threshold percentage, whereby if the content associated with the path changes more than a threshold percentage the path is identified as a transient path.

12. A system comprising:

a data processing apparatus comprising one or more computers; and

a memory apparatus in data communication with the data processing apparatus and storing instructions defining modules that are executable by the data processing apparatus, the modules comprising;

a retrieval module operable to retrieve at least two versions of a web page associated with a website;

a parser operable to parse the versions of the web page into sets of tokens being associated with a respective version of the web page;

a data structure generator operable to generate data structures for the versions of the web pages, the data structures comprising an entry for each token in respective version of the web page;

a fingerprint generator operable to generate fingerprints associated with individual tokens and to insert the fingerprints into the respective data structure at a respective location associated with the token described by the respective fingerprint;

a content analysis module operable to compare the fingerprints associated with respective portions the data structures, and to identify transient content associated with the web page based upon the comparison; and

a path analysis module operable to identify a path associated with the tokens marked as transient within the web page, a subtree count comprising a number of times the path appears in other web pages associated with the website, and a marked subtree count comprising a number of times the content associated with the path changes between versions of the respective web pages, wherein the path analysis module compares the subtree count with the marked subtree count and determines whether the path is a transient path based upon the comparison.

13. The system of claim 12, further comprising an indexer operable to index those portions of the web page which are not identified as transient content included within said web page.

14. The system of claim 12, further comprising an advertisement targeting module operable to target advertisements on those portions of the web page which are not identified as transient content in the said web page.

15. The system of claim 12, wherein the content analysis module is operable to initialize a first bit vector and second bit vector, the first bit vector comprising a bit for each token in the first data structure, the second bit vector comprising a bit for each token in the second data structure and to compare each fingerprint from the first set of fingerprints to fingerprints included in the second data structure, whereby:

if a fingerprint from the first set of fingerprints is not present in the second data structure, the analysis module is operable to set a corresponding bit in the first bit vector; and

if a fingerprint from the second set of fingerprints is not present in the first data structure, the analysis module is operable to set a corresponding bit in the second bit vector; and

if the bit associated with a selected token is set, the analysis module is operable to mark the selected token as transient.

16. The system of claim 15, wherein the content analysis module is further operable to extend areas of transient tokens to include the takes tokens associated with enclosing HTML tags.

17. The system of claim 12, wherein the path is identified as a transient path when a ratio between a number of times the content associated with the path changed between versions of the respective web pages divided by a number of times the path appears in other web pages associated with the website is greater than a threshold percentage, whereby if the content associated with the path varies more than a threshold percentage the path is identified as a transient path.

18. One or more non-transitory computer readable media having software program code operable to identify transient content, comprising modules operable to:

retrieve a first version of a web page and a second version of the web page, the web page being associated with a website;

parse the first version of the page into a first set of tokens and the second version of the web page into a second set of tokens;

insert a first set of fingerprints associated with the first set of tokens into a first data structure, and a second set of fingerprints associated with the second set of tokens into a second data structure;

compare the fingerprints included in the first and second data structures;

mark the tokens whose associated fingerprints appear only in one data structure as transient;

identify a path associated with every token in the web page;

identify a subtree count comprising a number of times the path appears in other web pages associated with the website;

identify a marked subtree count comprising a number of times the content associated with the path changes between versions of the respective web pages;

compare the subtree count with the marked subtree count; and

determine whether the path is a transient path based upon the comparison.

19. The computer readable media of claim 18, wherein the software program code further comprises modules operable to generate an index of the web pages associated with the website and remove from the index any transient portions of the web pages associated with the website and transient paths associated with the website.

20. The computer readable media of claim 18, wherein the software program further comprises modules operable to target advertisements on the content of web pages associated with the web site, such that the advertisements are targeted only on the portions of the content that not marked as transient.