Presentation of search results based on document structure

• US 20060074907A1
• Filed: 09/27/2004
• Published: 04/06/2006
• Est. Priority Date: 09/27/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Singhal, Amitabh K., Ratnakar, Viresh, O'Sullivan, Joseph Kieran, Lifantsev, Maxim
• Granted Patent: US 9,031,898 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/80 of semi-structured data, e.g. markup language structured data such as SGML, XML or HTML content-based retrieval of web data G06F16/95
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/103 Formatting, i.e. changing of presentation of documents automatic justification G06F40/189; automatic line break hyphenation G06F40/191
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]

Abstract

A system identifies a document relating to a search term, where the document includes a set of structural elements. The system determines a distribution of occurrences of the search term in the document, identifies one of the structural elements based on the distribution of occurrences of the search term in the document, and presents information associated with the identified structural element.

Claims

1. A method, comprising:

identifying a document relating to a search term, the document comprising a plurality of structural elements;

determining a distribution of occurrences of the search term in the document;

identifying one of the structural elements based on the distribution of occurrences of the search term in the document; and

presenting information associated with the identified structural element.

2. The method of claim 1, wherein the identifying a document comprises:

searching a corpus of documents to identify the document relating to the search term.

3. The method of claim 1, wherein the document comprises one of a book, a web site, a newspaper, an article, or a patent.

4. The method of claim 1, wherein the determining a distribution of occurrences of the search term in the document comprises:

searching a content of the document to identify occurrences of the search term with regard to the structural elements of the document.

5. The method of claim 4, wherein the identifying one of the structural elements comprises:

grouping the occurrences of the search term into clusters based on a physical proximity of the occurrences of the search term, and

determining a smallest one of the structural elements encompassing each of the clusters.

6. The method of claim 1, wherein the identifying one of the structural elements comprises:

grouping occurrences of the search term in the document into clusters based on a physical proximity of the occurrences of the search term, and

determining a smallest one of the structural elements encompassing each of the clusters.

7. The method of claim 6, wherein the presenting information comprises:

generating a search result based on information associated with the smallest one of the structural elements.

8. The method of claim 6, further comprising:

providing a threshold that specifies how close in physical proximity two occurrences of the search term have to be to be clustered; and

wherein the grouping occurrences of the search term into clusters is based on the threshold.

9. The method of claim 8, wherein the threshold is proportional to a number of pages in the document.

10. The method of claim 6, wherein the grouping occurrences of the search term into clusters favors a cluster that lies within one of the structural elements over a cluster that lies within multiple ones of the structural elements.

11. The method of claim 1, wherein the document is a book and the structural elements comprise the book, a set of chapters of the book, and a set of pages of the book.

12. The method of claim 1, wherein the structural elements comprise the document, a set of parts of the document, and a set of pages of the document;

and

wherein the information related to the identified structural element is a title page of the document when the document is the identified structural element.

13. The method of claim 1, wherein the structural elements comprise the document, a set of parts of the document, and a set of pages of the document;

and

wherein the information related to the identified structural element is a first page of the part when the part is the identified structural element.

14. The method of claim 1, wherein the structural elements comprise the document, a set of parts of the document, and a set of pages of the document;

and

wherein the information related to the identified structural element is the page of the document when the page is the identified structural element.

15. The method of claim 1, wherein the information associated with the identified structural element includes a portion of the document that includes an occurrence of the search term.

16. The method of claim 1, wherein the information associated with the identified structural element includes a portion of the document that does not include an occurrence of the search term.

17. The method of claim 1, wherein the presenting information associated with the identified structural element comprises:

visually distinguishing the search term in the information associated with the identified structural element.

18. The method of claim 1, wherein the structural elements comprise the document, a set of parts of the document, and a set of pages of the document;

and

wherein the identifying one of the structural elements comprises;

identifying a tree representation of the document, where the pages of the document correspond to leaf nodes, the parts of the document correspond to higher level nodes, and the document corresponds to a root node,

assigning scores to the leaf nodes based on whether the leaf nodes contain occurrences of the search term,

determining scores for the higher level nodes based on the scores of associated ones of the leaf nodes, and

determining a score for the root node based on the scores of the higher level nodes.

19. The method of claim 18, wherein the identifying one of the structural elements further comprises:

setting a threshold,

selecting one of the leaf nodes that contains an occurrence of the search term as a potential result,

selecting one of the higher level nodes as a potential result when the score of the one higher level node is greater than the threshold, and

selecting the root node as a potential result when the score of the root node is greater than the threshold.

20. The method of claim 19, wherein the identifying one of the structural elements further comprises:

removing selection of a leaf node associated with a higher level node when the higher level node is selected as a potential result, and

removing selection of the leaf nodes and the higher level nodes when the root node is selected as a potential result.

21. The method of claim 20, wherein the identifying one of the structural elements further comprises:

identifying the selected leaf node, higher level node, or root node as the identified structural element.

22. The method of claim 18, wherein the assigning scores to the leaf nodes comprises:

assigning a score of 0 to a leaf node that contains no occurrence of the search term, and assigning a score of 1 to a leaf node that contains an occurrence of the search term.

23. The method of claim 18, wherein the assigning scores to the leaf nodes comprises:

assigning a score of 0 to a leaf node that contains no occurrence of the search term, and

assigning, to a leaf node that contains an occurrence of the search term, a score that is a function of an importance of the occurrence of the search term.

24. A system, comprising:

means for obtaining a document relating to a search term, the document comprising a plurality of structural elements;

means for identifying a distribution of occurrences of the search term in the document with regard to the structural elements;

means for associating each of the occurrences of the search term with one of the structural elements based on the distribution of occurrences of the search term in the document; and

means for presenting information relating to the structural element associated with one of the occurrences of the search term.

25. A system, comprising:

a memory to store a corpus of documents, at least some of the documents comprising a plurality of structural elements; and

a processor to;

receive a search query that includes a search term,

identify a document in the corpus of documents that is relevant to the search term,

determine occurrences of the search term in the document based on the structural elements,

select one of the structural elements based on the occurrences of the search term in the document, and

provide information associated with the selected structural element as a result of the search query.

26. A method, comprising:

identifying a document that is relevant to a search term, the document comprising a plurality of structural elements;

determining occurrences of the search term in the document;

grouping the occurrences of the search term into clusters based on physical proximity of the occurrences of the search term;

determining one of the structural elements encompassing each of the clusters; and

providing information related to the determined structural elements.

27. The method of claim 26, further comprising:

providing a threshold that specifies how close in physical proximity two occurrences of the search term have to be to be clustered; and

wherein the grouping the occurrences of the search term into clusters is based on the threshold.

28. The method of claim 27, wherein the threshold is proportional to a number of pages in the document.

29. The method of claim 26, wherein the grouping the occurrences of the search term into clusters favors a cluster that lies within one of the structural elements over a cluster that lies within multiple ones of the structural elements.

30. A system, comprising:

means for identifying a document that is relevant to a search term, the document comprising a plurality of structural elements;

means for identifying occurrences of the search term in the document;

means for grouping the occurrences of the search term into clusters based on a threshold that specifies how close in physical proximity two occurrences of the search term have to be to be clustered;

means for determining a smallest one of the structural elements encompassing each of the clusters; and

means for presenting information related to the smallest structural elements.

31. A method, comprising:

identifying a document that is relevant to a search term, the document comprising a plurality of structural elements, where the structural elements comprise the document, a set of parts of the document, and a set of pages of the document;

identifying a tree representation of the document, where the pages of the document correspond to leaf nodes, the parts of the document correspond to higher level nodes, and the document corresponds to a root node;

assigning scores to the leaf nodes based on whether the leaf nodes contain occurrences of the search term;

determining scores for the higher level nodes based on the scores of associated ones of the leaf nodes;

determining a score for the root node based on the scores of the higher level nodes;

selecting one of the leaf nodes, one of the higher level nodes, or the root node, as a selected node, based on the scores; and

providing information relating to the selected node.

32. The method of claim 31, further comprising:

providing a threshold; and

wherein the selecting one of the leaf nodes, one of the higher level nodes, or the root node comprises;

selecting one of the leaf nodes that contains an occurrence of the search term as a potential result,

selecting one of the higher level nodes as a potential result when the score of the one higher level node is greater than the threshold, and

selecting the root node as a potential result when the score of the root node is greater than the threshold.

33. The method of claim 32, wherein the threshold is set based on whether the threshold is associated with the leaf nodes, the higher level nodes, or the root node.

34. The method of claim 32, wherein the threshold is set based on a number of pages associated with one of the leaf nodes, one of the higher level nodes, or the root node.

35. The method of claim 32, wherein the selecting one of the leaf nodes, one of the higher level nodes, or the root node further comprises:

removing selection of a leaf node associated with a higher level node when the higher level node is selected as a potential result, and

removing selection of the leaf nodes and the higher level nodes when the root node is selected as a potential result.

36. The method of claim 31, wherein the assigning scores to the leaf nodes comprises:

assigning a score of 0 to a leaf node that contains no occurrence of the search term, and

assigning a score of 1 to a leaf node that contains an occurrence of the search term.

37. The method of claim 31, wherein the assigning scores to the leaf nodes comprises:

assigning a score of 0 to a leaf node that contains no occurrence of the search term, and

assigning, to a leaf node that contains an occurrence of the search term, a score that is a function of an importance of the occurrence of the search term.

38. The method of claim 31, wherein the information related to the selected node is a title page of the document when the document is the selected node.

39. The method of claim 31, wherein the information related to the selected node is a first page of the part when the part is the selected node.

40. The method of claim 31, wherein the information related to the selected node is the page of the document when the page is the selected node.

41. A system, comprising:

means for identifying a document that is relevant to a search term;

means for identifying a tree representation of the document, where pages of the document correspond to leaf nodes, parts of the document correspond to higher level nodes, and the document corresponds to a root node;

means for assigning scores to the leaf nodes based on whether the leaf nodes contain occurrences of the search term;

means for determining scores for the higher level nodes based on the scores of associated ones of the leaf nodes;

means for determining a score for the root node based on the scores of the higher level nodes;

means for providing a threshold;

means for selecting one of the leaf nodes, one of the higher level nodes, or the root node, as a selected node, based on the scores and the threshold; and

means for providing information relating to the selected node.

42. A computer-readable medium containing computer-executable instructions, comprising:

instructions for determining that a document is relevant to a search term, the document comprising a plurality of structural elements;

instructions for determining occurrences of the search term in the document;

instructions for grouping the occurrences of the search term into clusters based on physical proximity of the occurrences of the search term;

instructions for determining one of the structural elements encompassing each of the clusters; and

instructions for presenting information relating to at least one the determined structural elements.