Retrieval of structured documents

• US 20040133557A1
• Filed: 01/06/2003
• Published: 07/08/2004
• Est. Priority Date: 01/06/2003
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Cui, Hang, Wen, Ji-Rong
• Granted Patent: US 7,111,000 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/3341 using boolean model
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

This disclosure relates to performing a query for a search term of a database containing a plurality of structured documents. Those structured documents that do not include the search term are ferreted or filtered out during an initial search. Matched structured documents which are those structured documents that do contain the search term are evaluated by ranking the individual elements based on how well each individual element matches the search term, and indicating to the user the ranking of the individual elements wherein the individual elements can be accessed by the user.

Claims

1. A method, comprising:

performing a query for a search term of a database containing a plurality of structured documents;

ferreting out those structured documents that do not include the search term;

evaluating elements of matched structured documents which are those structured documents that do contain the search term by;

ranking the individual elements based on how well each individual element matches the search term, and

indicating to the user the ranking of the individual elements wherein the individual elements can be accessed by the user.

2. The method of claim 1, wherein the indicating to the user includes displaying a hierarchical structure of the matched document to the user the structure.

3. The method of claim 2, wherein the displaying the hierarchical structure includes providing a hierarchical tree that displays the structure of the structured document.

4. The method of claim 1, further comprising scaling the individual ranked elements based on the granularities of the document.

5. The method of claim 1, wherein the ranking of the individual number is indicated using a number of graphic indicators.

6. The method of claim 5, wherein the number of graphic indicator includes a number of asterisks.

7. The method of claim 1, further comprising weighting individual elements includes an entropy measure.

8. The method of claim 1:

wherein the ferreting out those structured documents includes determining all elements containing at least one query term;

wherein the ranking the individual elements includes ranking the paths, in which

$\ln <br><br>\frac{N}{n_i}$

is the inverse document frequency (IDF) value of query term t_i, which represents the query term'"'"'s weight, and Q is the number of query terms in a query, using the calculation;

$\mathrm{Rank}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left({\mathrm{Path}}_p\right)=\underset{i=1}{\overset{Q}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Weight}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(t_i,E_j\right)\times <br><br>\ln <br><br>\frac{N}{n_i};<br><br>$

and

returning elements corresponding to the ranked paths in a descending order.

9. The method of claim 8, further comprising displaying the elements that have the closest match.

10. The method of claim 8, wherein the ranking the individual elements includes ranking those paths, in which

11. The method of claim 8:

further comprising;

weighting the elements, wherein the weighting includes, for each paragraph element, in which Weight(t_i,P_j) stands for the weight of the term t_i in the paragraph P_j, “

tf(t_i,P_j)”

is the term frequency of t_i in this paragraph, N denotes the number of documents in the corpus, and n_i represents the number of documents containing the term t_i, calculating the terms'"'"' weight according to the calculation;

12. A method, comprising:

ranking structured elements within a structured document, the structured document includes a document element or root element, at least one section element, and at least one paragraph elements, the ranking including;

for each paragraph element, in which Weight(t_i,P_j) stands for the weight of the term t_i in the paragraph P_j, “

t_f(t_i,P_j)”

is the term frequency of t_i in this paragraph, N denotes the number of documents in the corpus, and n_i represents the number of documents containing the term t_i, calculating the terms'"'"' weight according to the calculation;

$\text{Weight}<br><br>\left(t_i,\text{\hspace{1em}<br><br>}<br><br>P_j\right)=\ln <br><br>\left(1+\mathrm{tf}<br><br>\left(t_i,\text{\hspace{1em}<br><br>}<br><br>P_j\right)\right)\times <br><br>\ln <br><br>\frac{N}{n_i};<br><br>$

for any section element E_j at the upper levels following a bottom-up fashion, in which “

I(ti,Ej)”

is the entropy measure of the term t_i in element E_j, wherein if Weight(t_i,E_j)≧

average(E_j)+std_dev(E_j), the term t_i is selected as an index term of the element E_j and all sub-elements of E_j would eliminate t_i from their index term list, where “

average (E_j)”

denotes the arithmetic average of all terms'"'"' weights in the element E_j, and std_dev(E_j) denotes the standard deviation of these weights, calculating term weights using the calculation ^{Weight(t_i, E_j)=ln(1+tf(t_i,E_j}))×

I(t^_i,E_j);

repeating the calculating the term weights using the calculation ^{Weight(t_i, E_j)=ln(1+tf(t_i,E_j}))×

I(t^_i,E_j) until the root element (i.e., the document element) is reached;

obtaining paths for all evaluated candidate elements, and assign query terms'"'"' weight for elements to paths respectively;

ranking paths in which

$\ln <br><br>\frac{N}{n_i}$

is the inverse document frequency (IDF) value of query term t_i, which represents the query term'"'"'s weight and Q is the number of query terms in a query, using the calculation;

$\text{Rank}<br><br>\left({\text{Path}}_p\right)=\underset{i=1}{\overset{Q}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{Weight}<br><br>\left(t_i,\text{\hspace{1em}<br><br>}<br><br>E_j\right)\times <br><br>\ln <br><br>\frac{N}{n_i};<br><br>$

and

returning elements corresponding to the ranked paths in a descending order.

13. The method of claim 12, further comprising indicating to the user the ranking of the individual elements wherein the individual elements can be accessed by the user.

14. The method of claim 13, wherein the indicating to the user includes displaying a hierarchical structure of the matched document to the user the structure.

15. The method of claim 14, wherein the displaying the hierarchical structure includes providing a hierarchical tree that displays the structure of the structured document.

16. The method of claim 12, wherein the ranking of the individual elements is indicated numerically.

17. The method of claim 12, wherein the ranking of the individual number is indicated by providing a number of graphic indicators.

18. The method of claim 17, wherein the number of graphic indicator includes a number of asterisks.

19. The method of claim 12, further comprising weighting individual elements, wherein the weighting individual elements includes an entropy measure.

20. A method, comprising:

obtaining paths for all elements, and assigning query terms'"'"' weight for the paths; and

ranking paths, in which where

$\ln <br><br>\frac{N}{n_i}$

is the inverse document frequency (IDF) value of query term t_i, which represents the query term'"'"'s weight, and Q is the number of query terms in a query, using the calculation;

$\text{Rank}<br><br>\left({\text{Path}}_p\right)=\underset{i=1}{\overset{Q}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{Weight}<br><br>\left(t_i,\text{\hspace{1em}<br><br>}<br><br>E_j\right)\times <br><br>\ln <br><br>\frac{N}{n_i}.$

21. The method according to claim 20, further comprising returning elements corresponding to the ranked paths in a descending order.

22. The method of claim 21, further comprising indicating to the user the ranking of the individual elements wherein the individual elements can be accessed by the user.

23. The method of claim 22, wherein the indicating to the user includes displaying a hierarchical structure of the matched document to the user the structure.

24. The method of claim 23, wherein the displaying the hierarchical structure includes providing a hierarchical tree that displays the structure of the structured document.

25. The method of claim 20, wherein the ranking of the individual elements is indicated numerically.

26. The method of claim 20, wherein the ranking of the individual number is indicated by providing a number of graphic indicators.

27. The method of claim 26, wherein the number of graphic indicator includes a number of asterisks.

28. The method of claim 20, wherein the weighting candidate elements includes an entropy measure.

29. The method of claim 20, wherein the structured document is written in extensible markup language (XML).

30. A computer readable medium having computer executable instructions that when executed by a general process computer is capable of performing a method, the method comprising:

performing a query for a search term of a database containing a plurality of structured documents;

filtering out those structured documents that do not include the search term; and

evaluating matched structured documents which are those structured documents that do contain the search term by ranking the individual elements based on how well each individual element matches the search term.

31. The computer readable medium which performs the method of claim 30, including indicating to the user the ranking of the individual elements wherein the individual elements can be accessed by the user.

32. The computer readable medium which performs the method of claim 31, wherein the indicating to the user includes displaying a hierarchical structure of the matched document to the user the structure.

33. The computer readable medium which performs the method of claim 32, wherein the displaying the hierarchical structure includes providing a hierarchical tree that displays the structure of the structured document.

34. The computer readable medium which performs the method of claim 30, wherein the ranking of the individual elements is indicated numerically.

35. The computer readable medium which performs the method of claim 30, wherein the elements of the structured document are scaled depending on a granularities of the structured document.

36. The computer readable medium which performs the method of claim 30, wherein the ranking is indicated using a number of asterisks.

37. The computer readable medium which performs the method of claim 30, wherein the weighting individual elements includes an entropy measure.

38. The computer readable medium which performs the method of claim 30:

wherein the filtering out those structured documents includes determining all elements containing at least one query term;

wherein the ranking the individual elements includes ranking the paths, in which

$\ln <br><br>\frac{N}{n_i}$

is the inverse document frequency (IDF) value of query term t_i, which represents the query term'"'"'s weight, and Q is the number of query terms in a query, using the calculation;

$\text{Rank}<br><br>\left({\text{Path}}_p\right)=\underset{i=1}{\overset{Q}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{Weight}<br><br>\left(t_i,\text{\hspace{1em}<br><br>}<br><br>E_j\right)\times <br><br>\ln <br><br>\frac{N}{n_i};<br><br>$

returning elements corresponding to the ranked paths in a descending order.

39. The computer readable medium which performs the method of claim 30, further including ranking the individual elements, in which

40. A method for retrieving a portion of at least one document from a plurality of documents, comprising:

performing a query for a search term on a plurality of the documents;

setting the threshold of the weight of each element to be retrieved;

determining which one of the thresholded documents exceed the threshold; and

ranking the individual elements that exceed the threshold.

41. The method of claim 40, further comprising indicating to a user the ranking of the individual elements that exceed the threshold wherein the individual elements can be accessed by the user.

42. A method of displaying to a user the relevancy of the element of a document, comprising:

querying the document for a search term;

ranking the relevancy of the element for the search term;

returning to the user certain relevant portion of the document; and

indicating to the user the relevance of the returned portion of the document to the entire document.

43. The method of claim 42, wherein the document includes a plurality of elements that are arranged hierarchically.

44. The method of claim 42, further comprising ranking the relevancy of different ones of the plurality of elements within the document in response to the relevancy of different ones of the elements.

45. The method of claim 44, wherein the indicating to the user the relevance of the element is performed in response to the ranking the relevance of the different ones of the plurality of elements.

46. The method of claim 45, wherein the indicating includes displaying the relevance of the element to the user.

47. The method of claim 43, including displaying the context of the element relative to other ones of the elements within the document.

48. The method of claim 43, wherein the relevance of the element is indicated to the user using the path of the element within the document.

49. A method of displaying to a user the relevancy of the element of a document, comprising:

querying the document for a search term;

weighting the relevancy of the element for the search term; and

displaying a path structure of the document, the path structure indicates the relevance of the element to other elements in the document.

50. A computer readable medium having computer executable instructions that when executed by a general process computer is capable of performing a method, the method comprising:

querying a document including a plurality of paths, each one of the plurality of paths indicating certain elements that are being queried a search term;

weighting the relevancy of different ones of the paths for the search term;

ranking different ones of the paths in response to the weighted different ones of the paths; and

displaying a path structure of the plurality of elements within the document, the path structure indicates the relevance of different ones of the paths within the document.

51. A method, comprising:

querying a document having a plurality of elements for a search term;

ranking different ones of the elements in response to the weighted different ones of the elements; and

scaling the elements of the structured document.

52. The method of claim 51, further comprising displaying a path structure of the plurality of elements within the document, the path structure indicates the relevance of different ones of the elements within the document.

53. The method of claim 51:

wherein the weighting the relevancy of different ones of the elements includes determining all elements containing at least one query term;

weighting the relevancy of different ones of the elements includes obtaining paths for all evaluated candidate elements, and assign query terms'"'"' weight for elements to paths respectively;

wherein the ranking different ones of the elements includes ranking the paths, in which where

$\ln <br><br>\text{\hspace{1em}<br><br>}<br><br>\frac{N}{n_i}$

is the inverse document frequency (IDF) value of query term t_i, which represents the query term'"'"'s weight, and Q is the number of query terms in a query, using the calculation;

$\mathrm{Rank}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left({\mathrm{Path}}_p\right)=\underset{i=1}{\overset{Q}{\sum <br><br>}}<br><br>\mathrm{Weight}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(t_i,E_j\right)\times <br><br>\ln <br><br>\text{\hspace{1em}<br><br>}<br><br>\frac{N}{n_i};<br><br>$

and

returning elements corresponding to the ranked paths in an order based on the ranking.

54. The method of claim 51, wherein the ranking different ones of the elements includes ranking those paths, in which

55. A method to be used prior to ranking different paths in a hierarchical index, comprising:

querying a document having a plurality of elements for a search term, different ones of the plurality of elements are arranged in the different paths; and

weighting the relevancy of different ones of the paths based on the search term.

56. The method of claim 55, further comprising scaling the number of the different ones of the paths.

57. The method of claim 55, further comprising displaying text associated with different ones of the paths to the users.

58. The method of claim 57, further comprising indicating the context of the displayed text relative to other portions of the document.