Document ranking based on semantic distance between terms in a document

• US 8,606,778 B1
• Filed: 10/20/2011
• Issued: 12/10/2013
• Est. Priority Date: 03/31/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Harik, Georges R, Henzinger, Monika H
• Primary Examiner(s): Shmatov, Alexey
• Application Number:
  US13/277,843
• Time in Patent Office: 782 Days
• Field of Search: 707/755, 707/750, 707/999.1, 707/729
• US Class Current: 707/729
• CPC Class Codes: G06F 16/34 Browsing; Visualisation therefor
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Techniques are disclosed that locate implicitly defined semantic structures in a document, such as, for example, implicitly defined lists in an HTML document. The semantic structures can be used in the calculation of distance values between terms in the documents. The distance values may be used, for example, in the generation of ranking scores that indicate a relevance level of the document to a search query.

Claims

1. A method comprising:

identifying, by one or more processors, a document based on two or more search terms;

forming, by one or more processors, a tree structure based on the document, the tree structure including a plurality of items;

analyzing, by the one or more processors, a repetition of one or more tags in the tree structure;

determining, by the one or more processors and based on analyzing the repetition of the one or more tags, that the plurality of items are associated with a list, in the tree structure,

the list not being defined by a list tag,

the list including a header, and

each item, of the plurality of items associated with the list, including a plurality of words that describe the item associated with the list;

annotating, by the one or more processors, the tree structure to indicate that the list is present;

determining, by the one or more processors, a metric associated with the two or more search terms in a first manner when the two or more search terms appear in a single item of the plurality of items associated with the list;

determining, by the one or more processors, the metric associated with the two or more search terms in a second manner when;

a first search term, of the two or more search terms, appears in a first item of the plurality of items associated with the list, and

a second search term, of the two or more search terms, appears in a second item of the plurality of items associated with the list,

the first manner being different than the second manner;

determining, by the one or more processors, the metric associated with the two or more search terms in a third manner when;

the first search term appears in the header, and

the second search term appears in an item of the plurality of items associated with the list,

the third manner being different than the first manner and the second manner;

determining, by the one or more processors, a score for the document based on the metric associated with the two or more search terms; and

ranking, by the one or more processors and based on the score, the document with respect to at least one other document.

2. The method of claim 1, where the tree structure includes a hierarchical tag markup structure of HyperText Markup Language (HTML) code.

3. The method of claim 2, where the one or more tags include a line break tag and a bold tag, the line break tag and the bold tag being repeated for each item, of the plurality of items, in the HTML code.

4. The method of claim 1, where the one or more tags include at least one of:

a divide tag that divides the document into one or more sections and specifies one or more alignments for the one or more sections;

a font tag that specifies a font size for at least a portion of text of the document;

a line break tag that specifies one or more line breaks in the document;

or

a bold tag that specifies bold font text for at least a portion of the text of the document.

5. The method of claim 1, where analyzing the repetition of one or more tags in the tree structure further comprises:

analyzing sets of two or more tags that are repeated.

6. The method of claim 1, further comprising:

using the tree structure to detect at least one of;

one or more headings,

the one or more headings including the heading, or

one or more titles.

7. The method of claim 1, further comprising:

determining an existence of text below one of the header or a title of the tree structure; and

determining, based on determining the existence of the text, that the text belongs to the header or the title.

8. A system comprising:

one or more server devices to;

identify a document based on two or more search terms;

form a tree structure based on the document,

the tree structure including a plurality of items;

analyze a repetition of one or more tags in the tree structure;

determine, based on analyzing the repetition of the one or more tags, that the plurality of items are associated with a list, in the tree structure,

the list not being defined by a list tag,

the list including a header, and

each item, of the plurality of items associated with the list, including plurality of words that describe the item associated with the list;

annotate the tree structure to indicate that the list is present;

determine a metric associated with the two or more search terms in a first manner when the two or more search terms appear in a single item of the plurality of items associated with the list;

determine the metric associated with the two or more search terms in a second manner when;

a first search term, of the two or more search terms, appears in a first item of the plurality of items associated with the list, and

a second search term, of the two or more search terms, appears in a second item of the plurality of items associated with the list,

the first manner being different than the second manner;

determine the metric associated with the two or more search terms in a third manner when;

the first search term appears in the header, and

the second search term appears in an item of the plurality of items associated with the list,

the third manner being different than the first manner and the second manner;

determine a score for the document based on the metric associated with the two or more search terms; and

rank, based on the score, the document with respect to at least one other document.

9. The system of claim 8, where the tree structure includes a hierarchical tag markup structure of HyperText Markup Language (HTML) code.

10. The system of claim 9, where the one or more tags include a line break tag and a bold tag, the line break tag and the bold tag being repeated for each item, of the plurality of items, in the HTML code.

11. The system of claim 8, where the one or more tags include at least one of:

a divide tag that divides the document into one or more sections and specifies one or more alignments for the one or more sections;

a font tag that specifies a font size for at least a portion of text of the document;

a line break tag that specifies one or more line breaks in the document;

or

a bold tag that specifies bold font text for at least a portion of the text of the document.

12. The system of claim 8, where, when analyzing the repetition of one or more tags in the tree structure, the one or more server devices are further to:

analyze sets of two or more tags that are repeated.

13. The system of claim 8, where the one or more server devices are further to:

use the tree structure to detect at least one of;

one or more headings,

the one or more headings including the heading, or

one or more titles.

14. The system of claim 8, where the one or more server devices are further to:

determine an existence of text below one of the header or a title of the tree structure; and

determine, based on determining the existence of the text, that the text belongs to the header or the title.

15. A non-transitory computer-readable medium for storing instructions, the instructions comprising:

one or more instructions which, when executed by at least one processor, cause the at least one processor to identify a document based on two or more search terms,

one or more instructions which, when executed by the at least one processor, cause the at least one processor to form a tree structure based on the document,

the tree structure including a plurality of items;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to analyze a repetition of one or more tags in the tree structure;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to determine, based on analyzing the repetition of the one or more tags, that the plurality of items are associated with a list, in the tree structure,

the list not being defined by a list tag,

the list including a header, and

each item, of the plurality of items associated with the list, including a plurality of words that describe the item associated with the list;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to annotate the tree structure to indicate that the list is present;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to determine a metric associated with the two or more search terms in a first manner when the two or more search terms appear in a single item of the plurality of items associated with the list;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to determine the metric associated with the two or more search terms in a second manner when;

a first search term, of the two or more search terms, appears in a first item of the plurality of items associated with the list, and

a second search term, of the two or more search terms, appears in a second item of the plurality of items associated with the list,

the first manner being different than the second manner;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to determine the metric associated with the two or more search terms in a third manner when;

the first search term appears in the header, and

the second search term appears in an item of the plurality of items associated with the list,

the third manner being different than the first manner and the second manner;

one or more instructions which, when executed by the at least one processor, cause the at least one processor to determine a score for the document based on the metric associated with the two or more search terms; and

one or more instructions which, when executed by the at least one processor, cause the at least one processor to rank, based on the score, the document with respect to at least one other document.

16. The non-transitory computer-readable medium of claim 15, where the tree structure includes a hierarchical tag markup structure of HyperText Markup Language (HTML) code.

17. The non-transitory computer-readable medium of claim 16, where the one or more tags include a line break tag and a bold tag, the line break tag and the bold tag being repeated for each item, of the plurality of items, in the HTML code.

18. The non-transitory computer-readable medium of claim 15, where the one or more tags include at least one of:

a divide tag that divides the document into one or more sections and specifies one or more alignments for the one or more sections;

a font tag that specifies a font size for at least a portion of text of the document;

a line break tag that specifies one or more line breaks in the document;

or

a bold tag that specifies bold font text for at least a portion of the text of the document.

19. The non-transitory computer-readable medium of claim 15, where the one or more instructions which, when executed by the at least one processor, cause the at least one processor to analyze a repetition of one or more tags in the tree structure include:

one or more instructions which, when executed by the at least one processor, cause the at least one processor to analyze sets of two or more tags that are repeated.

20. The non-transitory computer-readable medium of claim 15, where the instructions comprise:

one or more instructions which, when executed by the at least one processor, cause the at least one processor to determine an existence of text below one of the header or a title of the tree structure; and

one or more instructions which, when executed by the at least one processor, cause the at least one processor to determine, based on determining the existence of the text, that the text belongs to the header or the title.