Presentation of search results based on document structure

• US 9,031,898 B2
• Filed: 09/27/2004
• Issued: 05/12/2015
• 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, Lifantsev, Maxim, O'Sullivan, Joseph Kieran
• Primary Examiner(s): Wong, Leslie
• Application Number:
  US10/949,708
• Publication Number:
  US 20060074907A1
• Time in Patent Office: 3,879 Days
• Field of Search: 715/205
• US Class Current: 707/3
• 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 performed by one or more server devices, the method comprising:

identifying, by a processor of the one or more server devices, a document relating to a search term,

the document comprising structural elements;

locating, by a processor of the one or more server devices, occurrences of the search term in the document;

grouping, by a processor of the one or more server devices, the occurrences of the search term into at least one cluster,

the grouping being based on relative locations of the occurrences of the search term, and

the grouping favoring a cluster that lies within a particular structural element, of the structural elements, over a cluster that lies within multiple structural elements of the structural elements;

identifying, by a processor of the one or more server devices, a structural element, of the structural elements, encompassing the at least one cluster; and

providing, by a processor of the one or more server devices and for presentation, information associated with the identified structural element.

2. The method of claim 1, where, when identifying the document, the method includes:

searching a corpus of documents to identify the document.

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

4. The method of claim 1, where, when locating the occurrences of the search term in the document, the method includes:

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, where, when identifying the structural element, the method includes:

determining, with respect to each of the structural elements, a smallest structural element, of the structural elements, encompassing each of the clusters.

6. The method of claim 1, where, when identifying the structural element, the method includes:

determining, with respect to each of the structural elements, a smallest structural element, of the structural elements, encompassing each of the clusters.

7. The method of claim 6, where, when providing, for presentation, the information associated with the identified structural element, the method includes:

generating a search result based on information associated with the smallest structural element.

8. The method of claim 1, further comprising:

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

where, when grouping the occurrences of the search term into the at least one cluster, the method includes;

grouping the occurrences of the search term into the at least one cluster based on the threshold.

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

10. The method of claim 1, where

the document is a book, and

the structural elements comprise at least one of:

the book,

a set of chapters of the book, or

a set of pages of the book.

11. The method of claim 1, where

the structural elements comprise the document, a set of parts of the document, and a set of pages of the document, and

the information associated with the identified structural element is a title page of the document.

12. The method of claim 1, where

the structural elements comprise the document, a set of parts of the document, and a set of pages of the document, and

the information associated with the identified structural element is a first page of the document.

13. The method of claim 1, where

the structural elements comprise the document, a set of parts of the document, and a set of pages of the document, and

the information associated with the identified structural element is a page of the document.

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

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

16. The method of claim 1, where, when providing, for presentation, the information associated with the identified structural element, the method includes:

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

17. A computer-implemented system comprising:

one or more devices to;

obtain a document relating to a search term, the document comprising structural elements;

identify occurrences of the search term in the document with regard to the structural elements;

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

a first cluster, of the clusters, that lies within a particular structural element, of the structural elements, being favored over a second cluster, of the clusters, that lies within multiple structural elements of the structural elements;

identify a structural element, of the structural elements, encompassing each of the clusters; and

provide, for presentation, information relating to the identified structural element.

18. The computer-implemented system of claim 17, where the one or more devices are further to:

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

19. The computer-implemented system of claim 17, where the one or more devices are further to:

determine a smallest structural element, of the structural elements, encompassing each of the clusters.

20. The computer-implemented system of claim 17, where

the one or more devices, when identifying the structural element, are further to:

determine, with respect to each of the structural elements, a smallest structural element, of the structural elements, encompassing each of the clusters, and

the one or more devices, when providing, for presentation, the information relating to the identified structural element, are further to;

generate a search result based on information associated with the smallest structural element.

21. The computer-implemented system of claim 17, where

the one or more devices are further to:

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

the one or more devices, when grouping the occurrences of the search term into clusters, are further to;

group the occurrences of the search term into clusters based on the threshold.

22. A device comprising:

a memory to store a corpus of documents,

at least one document, of the corpus of documents, comprising 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, the at least one document including the document;

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

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

a first cluster, of the clusters, that lies within a particular structural element, of the structural elements, being favored over a second cluster, of the clusters, that lies within multiple structural elements of the structural elements;

identify a structural element, of the structural elements, encompassing each of the clusters; and

provide, for presentation, information associated with the identified structural element.

23. The device of claim 22, where the processor is further to:

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

24. The device of claim 23, where the processor is further to:

determine a smallest structural element, of the structural elements, encompassing each of the clusters.

25. The device of claim 22, where

the processor, when identifying the structural element, is further to:

determine, with respect to each of the structural elements, a smallest structural element, of the structural elements, encompassing each of the clusters, and

the processor, when providing, for presentation, the information relating to the identified structural element, is further to;

generate a search result based on information associated with the smallest structural element.

26. The device of claim 22, where

the processor is further to:

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

the processor, when grouping the occurrences of the search term into clusters, is further to;

group the occurrences of the search term into clusters based on the threshold.

27. The device of claim 22, where the processor, when providing, for presentation, the information associated with the identified structural element, is further to:

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

28. A method performed by one or more server devices, the method comprising:

identifying, by a processor of the one or more server devices, a document that is relevant to a search term,

the document comprising structural elements;

determining, by a processor of the one or more server devices, occurrences of the search term in the document;

grouping, by a processor of the one or more server devices, the occurrences of the search term into clusters based on physical proximity of the occurrences of the search term,

a first cluster, of the clusters, that lies within a particular structural element, of the structural elements, being favored over a second cluster, of the clusters, that lies within multiple structural elements of the structural elements;

determining, by a processor of the one or more server devices, a smallest structure element, of the structural elements, that encompasses each of the clusters; and

providing, by a processor of the one or more server devices, information related to the determined structural element.

29. The method of claim 28, further comprising:

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

where, when grouping the occurrences of the search term into clusters, the method includes;

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

30. The method of claim 29, where the threshold is proportional to a number of pages in the document.

31. A computer-implemented system comprising:

one or more devices to;

identify a document that is relevant to a search term, the document comprising structural elements;

identify occurrences of the search term in the document;

group 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,

the threshold being proportional to a number of pages in the document;

determine a structural element, of the structural elements, encompassing each of the clusters; and

provide, for presentation, information related to the structural element.

32. The computer-implemented system of claim 31, where

the document is a book, and

the structural elements include the book, a set of chapters of the book, and a set of pages of the book.

33. A method performed by one or more server devices, the method comprising:

identifying, by a processor of the one or more server devices, a document that is relevant to a search term,

the document comprising 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, by a processor of the one or more server devices, 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, by a processor of the one or more server devices, scores to the leaf nodes based on whether the leaf nodes contain occurrences of the search term;

determining, by a processor of the one or more server devices, scores for the higher level nodes based on the scores of associated ones of the leaf nodes;

determining, by a processor of the one or more server devices, a score for the root node based on the scores of the higher level nodes;

providing, by a processor of the one or more server devices, a threshold,

where the threshold is based on at least one of;

a number of pages associated with one of the leaf nodes,

a number of pages associated with one of the higher level nodes, or

a number of pages associated with the root node;

selecting, by a processor of the one or more server devices, 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

providing, by a processor of the one or more server devices, information relating to the selected node.

34. The method of claim 33, where, when selecting one of the leaf nodes, one of the higher level nodes, or the root node, the method includes at least one of:

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;

or

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

35. The method of claim 34, where, when selecting the one of the leaf nodes, one of the higher level nodes, or the root node, the method includes:

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

removing a 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 33, where, when assigning scores to the leaf nodes, the method includes:

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 33, where, when assigning scores to the leaf nodes, the method includes:

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 33, where 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 33, where 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 33, where the information related to the selected node is the page of the document when the page is the selected node.

41. A computer-implemented system comprising:

one or more devices to;

identify a document that is relevant to a search term;

identify 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;

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

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

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

provide a threshold,

where the threshold is threshold is based on at least one of;

a number of pages associated with one of the leaf nodes,

a number of pages associated with one of the higher level nodes, or

a number of pages associated with the root node;

select 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

provide information relating to the selected node.

42. The computer-implemented system of claim 41, where the one or more devices are further to:

assign a score of 0 to a leaf node that contains no occurrences of the search term; and

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

43. The computer-implemented system of claim 41, where the one or more devices are further to:

assign a score of 0 to a leaf node that contains no occurrence of the search term; and

assign, 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.

44. A non-transitory computer-readable storage medium containing computer-executable instructions, the instructions comprising:

one or more instruction which, when executed by a processor of a device, cause the processor to;

determine that a document is relevant to a search term,

the document comprising structural elements;

determine occurrences of the search term in the document;

group the occurrences of the search term into clusters based on physical proximity of the occurrences of the search term,

a first cluster, of the clusters, that lies within a particular structural element, of the structural elements, being favored over a second cluster, of the clusters, that lies within multiple structural elements of the structural elements;

determine a structural element, of the structural elements, encompassing each of the clusters; and

provide, for presentation, information relating to the determined structural element.

45. The non-transitory computer-readable storage medium of claim 44, where

the structural elements comprise the document, a set of parts of the document, and a set of pages of the document;

and

the information related to the one of the identified structural elements is a title page of the document when the document is the one of the identified structural elements.

46. The non-transitory computer-readable storage medium of claim 44, where the information relating to at least one of the determined structural elements includes a portion of the document that includes an occurrence of the search term.