Document ranking based on semantic distance between terms in a document

• US 8,060,501 B1
• Filed: 03/23/2010
• Issued: 11/15/2011
• 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): Betit, Jacob F
• Application Number:
  US12/729,763
• Time in Patent Office: 602 Days
• Field of Search: 707/724, 707/729
• US Class Current: 707/724
• 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:

receiving, by one or more processors, a document that includes first, second, third, and fourth terms;

identifying, by the one or more processors, that a list is present within the document, where the list includes a plurality of items;

determining, by the one or more processors, that the first and second terms appear in the list;

determining, by the one or more processors, in response to determining that the first and second terms appear in the list, a distance value between the first and second terms within the list, where the distance value is determined based on at least one of a plurality of rules that is associated with particular locations, in the list, of the first and second terms, where determining the distance value includes;

determining, by the one or more processors, that the first term appears in one of the plurality of items of the list and the second term appears in a different one of the plurality of items of the list, and

generating, by the one or more processors, the distance value based on the first term appearing in the one of the plurality of items of the list and the second term appearing in the different one of the plurality of items of the list, where the distance value, relative to a particular distance value of the third and fourth terms of the list, indicates that the first and second terms are farther apart from each other than the third and fourth terms, where the third and fourth terms appear in a same one of the plurality of items of the list;

generating, by the one or more processors, a ranking score for the document based on the distance value; and

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

2. The method of claim 1, where the document includes fifth and sixth terms and the method further comprises:

determining that the fifth and sixth terms appear in the document outside of any list; and

generating another distance value between the fifth and sixth terms without using the plurality of rules.

3. The method of claim 2, where the other distance value is determined based on a number of terms between the fifth and sixth terms.

4. The method of claim 1, where the the method further comprises:

determining that both of the third and fourth terms appear in the same one of the plurality of items of the list, and

generating the particular distance value between the third and fourth terms using another one of the plurality of rules.

5. The method of claim 1, further comprising:

determining that a fifth term appears in one of the plurality of items of the list and a sixth term appears in a header of the list, and

generating another distance value based on the fifth term appearing in the one of the plurality of items of the list and the sixth term appearing in the header of the list, where the another distance value, relative to a particular distance value of the fifth and sixth terms, indicates that the fifth and sixth terms are equally distant to seventh and eighth terms, where the seventh term appears in a different one of the plurality of items of the list and the eighth term appears in the header of the list.

9. The method of claim 1, where identifying that the list is present within the document further comprises:

identifying a list that is implicitly defined within the document.

10. The method of claim 9, where identifying the list that is implicitly defined within the document comprises:

parsing the document into a tree structure based on a markup language used to create the document;

identifying repeating sets of markup language elements in the tree structure; and

annotating the document to indicate the presence of the implicit list.

6. A method comprising:

receiving, by one or more processors, a document that includes first, second, third, and fourth terms;

identifying, by the one or more processors, that a list is present within the document, where the list includes a plurality of items;

determining, by the one or more processors, that the first and second terms appear in the list;

determining, by the one or more processors, in response to determining that the first and second terms appear in the list, a distance value between the first and second terms within the list, where the distance value is determined based on at least one of a plurality of rules that is associated with particular locations, in the list, of the first and second terms, where determining the distance value includes;

determining, by the one or more processors, that the first term appears in one of the plurality of items of the list and the second term appears in a different one of the plurality of items of the list, and

generating, by the one or more processors, the distance value based on the first term appearing in the one of the plurality of items of the list and the second term appearing in the different one of the plurality of items of the list, where the distance value, relative to a particular distance value of the third and fourth terms, indicates that the first and second terms are farther apart from each other than the third and fourth terms, where the third term appears in one of the plurality of items of the list and the fourth term appears in a header of the list;

generating, by the one or more processors, a ranking score for the document based on the distance value; and

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

7. The method of claim 6, where identifying that the list is present within the document further comprises:

identifying a list that is explicitly defined, within the document, by at least one predefined list identifier.

8. The method of claim 7, where the at least one predefined list identifier includes hyper-text markup language tags.

20. The method of claim 6, further comprising:

determining that a fifth term appears in one of the plurality of items of the list and a sixth term appears in a header of the list, and

generating another distance value based on the fifth term appearing in the one of the plurality of items of the list and the sixth term appearing in the header of the list, where the distance value, relative to a particular distance value of the fifth and sixth terms, indicates that the fifth and sixth terms are equally distant to seventh and eighth terms, where the seventh term appears in a different one of the plurality of items of the list and the eighth term appears in the header of the list.

11. A system comprising:

one or more processors to;

receive a document that includes first, second, third, and fourth terms,

identify that a list is present within the document, where the list includes a plurality of items,

determine that first and second terms appear in the list,

determine, in response to determining that the first and second terms appear in the list, a distance value between the first and second terms in the list, where the distance value is determined based on at least one of a plurality of rules that is associated with particular locations, in the list, of the first and second terms, where, when determining the distance value, the one or more processors are to;

determine that the first term appears in one of the plurality of items of the list and the second term appears in a different one of the plurality of items of the list, and

generate a first distance value based on the first term appearing in the one of the plurality of items of the list and the second term appearing in the different one of the plurality of items of the list, where the first distance value, relative to a particular distance value of the third and fourth terms, indicates that the first and second terms are farther apart from each other than third and fourth terms, when the third term appears in one of the plurality of items of the list and the fourth term appears in a title of the at least one list, or

generate a second distance value based on the first term appearing in the one of the plurality of items of the list and the second term appearing in the different one of the plurality of items of the list, where the second distance value, relative to a particular distance value of the third and fourth terms, indicates that the first and second terms are farther apart from each other than the third and fourth terms, when the third and fourth terms appear in a same one of the plurality of items of the list;

generate a ranking score for the document based on the first or second distance value, and

order the document with respect to at least one other document based on the ranking score for the document.

12. The system of claim 11, where the document includes fifth and sixth terms, and the one or more processors are further to:

determine that the fifth term appears in one of the plurality of items of the list and the sixth term appears in the title of the list, and

generate another distance value between the fifth and sixth terms using another one of the plurality of rules.

13. The system of claim 11, where, when generating a ranking score for the document based on the distance value, the one or more processors are further to:

generate the ranking score for the document based on the distance value and an inverse document frequency when one of the first or second terms is identified in a list of uncommon words.

14. The system of claim 11, where, when generating a ranking score for the document based on the distance value, the one or more processors are further to:

generate the ranking score for the document based on the distance value and a predetermined quality of a web site or domain associated with the document.

15. The system of claim 11, where, when identifying that the list is present within the document, the one or more processors are further to:

analyze a corpus of documents to identify whether any lists are present within the corpus of documents, where the corpus of documents includes the document, and

annotate the document with list information when the list is identified as present within the document.

16. The system of claim 15, where, when determining that the first and second terms appear in the list, the one or more processors are further to:

compare the first and second terms to the annotated list information to determine that the first and second terms appear in the list.

17. A non-transitory computer-readable medium that stores instructions executable by at least one processor for performing a method, the computer-readable medium comprising:

instructions to receive a document that includes first, second, third, and fourth terms;

instructions to identify that an implicit list is present within the document, where the list includes a plurality of items;

instructions to determine that the first and second search terms appear in the list;

instructions to determine, in response to determining that the first and second terms appear in the list, a distance value between the first and second terms in the list, where the distance value is determined based on at least one of a plurality of rules that is associated with particular locations, in the list, of the first and second terms, where the instructions to determine the distance value include,

instructions to determine that the first term appears in one of the plurality of items of the list and the second term appears in a different one of the plurality of items of the list, and

instructions to generate a first distance value based on the first term appearing in the one of the plurality of items of the list and the second term appearing in the different one of the plurality of items of the list, where the first distance value, relative to a particular distance value of the third and fourth terms, indicates that the first and second terms are farther apart from each other than third and fourth terms, when the third term appears in one of the plurality of items of the list and the fourth term appears in a header of the at least one list, or

instructions to generate a second distance value based on the first term appearing in the one of the plurality of items of the list and the second term appearing in the different one of the plurality of items of the list, where the second distance value, relative to a particular distance value of the third and fourth terms, indicates that the first and second terms are farther apart from each other than the third and fourth terms, when the third and fourth terms appear in a same one of the plurality of items of the list;

instructions to generate, with the one or more processors, a ranking score for the document based on the first or second distance value; and

instructions to order the document with respect to at least one other document based on the ranking score for the document.

18. The computer-readable medium of claim 17, where the method further comprises:

instructions to determine that the third and fourth terms appear in the same one of the plurality of items of the list, and

instructions to generate the particular distance value between the third and fourth terms using another one of the plurality of rules.

19. The computer-readable medium of claim 17, where the method further comprises:

instructions to determine that a fifth term appears in one of the plurality of items of the list and a sixth term appears in a header of the list, and

instructions to generate another distance value based on the fifth term appearing in the one of the plurality of items of the list and the sixth terms appearing in the header of the list, where the another distance value, relative to a particular distance value of the fifth and sixth terms, indicates that fifth and sixth terms are equally distant to seventh and eighth terms, where the seventh term appears in a different one of the plurality of items of the list and the eighth term appears in a header of the list.

21. A method comprising:

receiving, by one or more processors, a document that includes first, second, third, and fourth terms;

identifying, by the one or more processors, that a semantic structure is present within the document, where the semantic structure includes a plurality of items;

determining, by the one or more processors, that the first and second terms appear in the semantic structure;

determining, by the one or more processors, in response to determining that the first and second terms appear in the semantic structure, a distance value between the first and second terms within the semantic structure, where the distance value is determined based on at least one of a plurality of rules that is associated with particular locations, in the semantic structure, of the first and second terms, where determining the distance value includes;

determining, by the one or more processors, that the first term appears in one of the plurality of items of the semantic structure and the second term appears in a different one of the plurality of items of the semantic structure, and

generating, by the one or more processors, the distance value based on the first term appearing in the one of the plurality of items of the semantic structure and the second term appearing in the different one of the plurality of items of the semantic structure, where the distance value, relative to a particular distance value of the third and fourth terms of the semantic structure, indicates that the first and second terms are farther apart from each other than the third and fourth terms, where the third and fourth terms appear in a same one of the plurality of items of the semantic structure; and

generating, by the one or more processors, a ranking score for the document based on the distance value.