Inferring hierarchical descriptions of a set of documents

• US 20030167163A1
• Filed: 07/31/2002
• Published: 09/04/2003
• Est. Priority Date: 02/22/2002
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Research Institute, Inc. (NEC Corporation)
• Inventors: Lawrence, Stephen R., Pennock, David M., Glover, Eric J.
• Granted Patent: US 7,165,024 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9558 Details of hyperlinks; Management of linked annotations

Abstract

A method automatically determines groups of words or phrases that are descriptive names of a small set of documents, as well as infers concepts in the small set of documents that are more general and more specific than the descriptive names, without any prior knowledge of the hierarchy or the concepts, in a language independent manner. The descriptive names and the concepts may not even be explicitly contained in the documents. The primary application of the invention is for searching of the World Wide Web, but the invention is not limited solely to use with the World Wide Web and may be applied to any set of documents. Classes of features are identified in order to promote understanding of a set of documents. Preferably, there are three classes of features. “Self” features or terms describe the cluster as a whole. “Parent” features or terms describe more general concepts. “Child” features or terms describe specializations of the cluster. The self features can be used as a recommended name for a cluster, while parents and children can be used to place the clusters in the space of a larger collection. Parent features suggest a more general concept, while children features suggest concepts that describe a specialization of the self feature(s). Automatic discovery of parent, self and child features is useful for several purposes including automatic labeling of web directories and improving information retrieval.

Claims

1. A method of inferring hierarchical descriptions of a set of documents comprising the steps of:

providing a first histogram of features from a positive set of documents;

providing a second histogram of features from a collection set of documents; and

determining whether each feature is a self feature, a parent feature or a child feature based on the fraction of the documents in the positive set containing the feature and the fraction of the documents in the collection set containing the feature.

2. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 1, further comprising the steps of setting a histogram threshold and removing features which are below the threshold in both the first histogram and the second histogram.

3. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 1, further comprising ranking the features by order of occurrences in the positive set of documents.

4. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 1, wherein a document comprises image data.

5. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 1, wherein a document comprises text data.

6. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 5, wherein the text data is in a language other than English.

7. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 1, wherein a document comprises audio data.

8. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 1, wherein a document comprises multimedia data.

9. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 1, wherein said determining is performed using Predict Parents, Children and Selfs Algorithm.

10. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 9, further comprising the steps of setting a histogram threshold and removing features which are below the threshold in both the first histogram and the second histogram.

11. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 9, further comprising ranking the features by order of occurrences in the positive set of documents.

12. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 9, wherein a document comprises image data.

13. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 9, wherein a document comprises text data.

14. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 13, wherein the text data is in a language other than English.

15. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 9, wherein a document comprises audio data.

16. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 9, wherein a document comprises multimedia data.

17. A method of inferring hierarchical descriptions of a set of documents comprising web pages comprising the steps of:

obtaining a first set of URLs comprising a positive set of documents;

obtaining a second set of URLs comprising a collection set of documents;

determining in-bound links for each URL in the first set of URLs and for each URL the second set of URLs;

creating a virtual document for each URL in the positive set of documents and a virtual document for each URL in the collection set of documents;

providing a first histogram of features from the virtual documents associated with the first set of URLs;

providing a second histogram of features from the virtual documents associated with the second set of URLs; and

determining whether each feature is a self feature, a parent feature or a child feature based on the fraction of the virtual documents associated with the positive set of documents containing the feature and the fraction of the virtual documents associated with the collection set of documents containing the feature.

18. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 17, further comprising the steps of setting a histogram threshold and removing features which are below the threshold in both the first histogram and the second histogram.

19. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 17, further comprising ranking the features by order of occurrences in the positive set of documents.

20. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 17, wherein a URL points to a page that contains image data.

21. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 17, wherein a URL points to a page that contains text data.

22. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 21, wherein the text data is in a language other than English.

23. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 17, wherein a URL points to a page that contains audio data.

24. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 17, wherein a URL points to a page that contains multimedia data.

25. A method of inferring hierarchical descriptions of a set of documents comprising web pages as set forth in claim 17, wherein said determining whether each feature is a self feature, a parent feature or a child feature is performed using Predict Parents, Children and Selfs Algorithm.

26. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 25, further comprising the steps of setting a histogram threshold and removing features which are below the threshold in both the first histogram and the second histogram.

27. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 25, further comprising ranking the features by order of occurrences in the positive set of documents.

28. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 25, wherein a URL points to a page that contains image data.

29. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 25, wherein a URL points to a page that contains text data.

30. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 29, wherein the text data is in a language other than English.

31. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 25, wherein a URL points to a page that contains audio data.

32. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 25, wherein a URL points to a page that contains multimedia data.

33. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents comprising the steps of:

submitting a search query to an information retrieval system;

retrieving a first set of documents from the information retrieval system responsive to the search query;

providing a second set of documents;

determining in-bound links for each retrieved document in the first set documents and for each documents in the second set of documents;

creating a virtual document for each document in the first set of documents and for each document in the second set of documents;

creating a first histogram of features in the virtual documents associated with the first set of documents;

creating a second histogram of features in the virtual documents associated with the second set of documents;

determining whether each feature is a self feature, a parent feature or a child feature based on the fraction of the virtual documents associated with the positive set of documents containing the feature and the fraction of the virtual documents associated with the collection set of documents containing the feature; and

changing the search query responsive to the classification of a feature.

34. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 33, further comprising the steps of setting a histogram threshold and removing features which are below the threshold in both the first histogram and the second histogram.

35. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 33, further comprising ranking the features by order of occurrences in the first set of documents.

36. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 33, wherein the search query is changed to a parent feature to broaden the search scope.

37. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 33, wherein the search query is changed to a child feature to narrow the search scope.

38. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 33, wherein a document comprises image data.

39. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 33, wherein a document comprises text data.

40. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 39, wherein the text data is in a language other than English.

41. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 33, wherein a document comprises audio data.

42. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 33, wherein a document comprises multimedia data.

43. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 33, wherein said determining whether each feature is a self feature, a parent feature or a child feature is performed using Predict Parents, Children and Selfs Algorithm.

44. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 43, further comprising the steps of setting a histogram threshold and removing features below the threshold in both the first histogram and the second histogram.

45. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 43, further comprising ranking the features by order of occurrences in the first set of documents.

46. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 43, wherein the search query is changed to a parent feature to broaden the search scope.

47. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 43, wherein the search query is changed to a child feature to narrow the search scope.

48. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 43, wherein a document comprises image data.

49. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 43, wherein a document comprises text data.

50. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 49, wherein the text data is in a language other than English.

51. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 43, wherein a document comprises audio data.

52. A method of searching an information retrieval system using inferential hierarchical descriptions of a set of documents as set forth in claim 43, wherein a document comprises multimedia data.

53. A method of labeling a document directory using inferential descriptions of sets of documents comprising the steps of:

(a) providing a hierarchy of sets of documents;

(b) providing a collection set of documents;

(c) determining in-bound links for each document in a set of documents in the hierarchy and for each document in the collection set of documents;

(d) creating a virtual document for each document in the set of documents in the hierarchy and for each document in the collection set of documents;

(e) creating a first histogram of features from the virtual documents associated with the set of documents in the hierarchy;

(f) creating a second histogram of features from the virtual documents associated with the collection set of documents;

(g) determining whether each feature is a self feature, a parent feature or a child feature based on the fraction of the virtual documents associated with the set of documents in the hierarchy containing the feature and the fraction of virtual documents associated with the collection set of documents containing the feature;

(h) repeating steps (c) to (g) for each set of documents in the hierarchy of sets of documents; and

(i) labeling the hierarchy of sets of documents responsive to the determining of each feature.

54. A method of labeling a document directory using inferential descriptions of sets of documents as set forth in claim 53, wherein said determining whether each feature is a self feature, a parent feature or a child feature is performed using Predict Parents, Children, and Selfs Algorithm.

55. A method of labeling a document directory using inferential descriptions of sets of documents comprising the steps of:

(a) providing a hierarchy of sets of documents;

(b) providing a collection set of documents;

(c) creating a first histogram of features from each set of documents in the hierarchy;

(d) creating a second histogram of features from the collection set of documents;

(e) determining whether each feature is a self feature, a parent feature or a child feature based on the fraction of documents associated with the set of documents in the hierarchy containing the feature and the fraction of documents associated with the collection set of documents containing the feature;

(f) repeating steps (c) to (e) for each set of documents in the hierarchy of sets of documents; and

(g) labeling the hierarchy of sets of documents responsive to the determining of each feature.

56. A method of labeling a document directory using inferential descriptions of sets of documents as set forth in claim 55, wherein said determining whether each feature is a self feature, a parent feature or a child feature is performed using Predict Parents, Children, and Selfs Algorithm.

57. A method of inferring hierarchical descriptions of a set of documents comprising the steps of:

obtaining a first set of documents comprising a positive set of documents;

obtaining a second set of documents comprising a collection set of documents;

determining in-bound links for each document in the first set of documents and for each document in the second set of documents;

creating a virtual document for each document in the positive set of documents and a virtual document for each document in the collection set of documents;

providing a first histogram of features from the virtual documents associated with the first set of documents;

providing a second histogram of features from the virtual documents associated with the second set of documents; and

determining whether each feature is a self feature, a parent feature or a child feature based on the fraction of the virtual documents associated with the positive set of documents containing the feature and the fraction of the virtual documents associated with the collection set of documents containing the feature.

58. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 57, further comprising the steps of setting a histogram threshold and removing features which are below the threshold in both the first histogram and the second histogram.

59. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 57, further comprising ranking the features by order of occurrences in the positive set of documents.

60. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 57, wherein a document contains image data.

61. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 57, wherein a document contains text data.

62. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 61, wherein the text data is in a language other than English.

63. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 57, wherein a document contains audio data.

64. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 57, wherein a document contains multimedia data.

65. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 57, wherein said determining whether each feature is a self feature, a parent feature or a child feature is performed using Predict Parents, Children and Selfs Algorithm.

66. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 65, further comprising the steps of setting a histogram threshold and removing features which are below the threshold in both the first histogram and the second histogram.

67. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 65, further comprising ranking the features by order of occurrences in the positive set of documents.

68. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 65, wherein a document contains image data.

69. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 65, wherein a document contains text data.

70. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 69, wherein the text data is in a language other than English.

71. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 65, wherein a document contains audio data.

72. A method of inferring hierarchical descriptions of a set of documents as set forth in claim 65, wherein a document contains multimedia data.