SYSTEM AND METHOD FOR MEASURING THE QUALITY OF DOCUMENT SETS

• US 20090006383A1
• Filed: 06/25/2008
• Published: 01/01/2009
• Est. Priority Date: 06/26/2007
• Status: Active Grant

• Current Assignee: Oracle OTC Subsidiary LLC (Oracle Corporation)
• Original Assignee: Endeca Technologies Incorporated (Oracle Corporation)
• Inventors: Tunkelang, Daniel, Zelevinsky, Vladimir, Wang, Joyce Jeanpin
• Granted Patent: US 8,024,327 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/3331 Query processing

Abstract

Systems and methods are described that calculate the interestingness of a set of one or more records in a database, either absolutely (i.e., compared to an overall collection of records) or relative to some other set of records. In one embodiment, the measure is a relative entropy value that has been normalized. Various applications of the measure are described in the context of an information retrieval system. These applications include, for example, guiding query interpretation, guiding view selection and summarization, intelligent ranges, event detection, concept triggers and interpreting user actions, hierarchy discovery, and adaptive data mining.

Claims

1. A method for measuring the distinctiveness of a set, the method comprising acts of:

analyzing the set to obtain a statistical distribution of at least one identifying characteristic within the set;

generating a measurement of distinctiveness for the set based on the statistical distribution of the at least one identifying characteristic; and

normalizing the measurement of the distinctiveness of the set.

2. The method according to claim 1, wherein the set comprises at least one document, wherein the at least one document further comprises a unit of storage of digital data.

3. The method according to claim 2, wherein the at least one document further includes at least one of a data record within a database, textual information, non-textual information, audio files, video files, streaming data, a defined entity, and metadata.

4. The method according to claim 1, wherein the act of normalizing further comprises an act of calculating a mean for an expected statistical distribution of the at least one identifying characteristic.

5. The method according to claim 1, wherein the act of normalizing further comprises an act of calculating a standard deviation of an expected statistical distribution of the at least one identifying characteristic.

6. The method according to claim 1, further comprising the acts of:

determining an expected statistical distribution of the at least one identifying characteristic;

generating at least one comparison set; and

determining a statistical distribution of at least one identifying characteristic for the comparison set.

7. The method according to claim 6, wherein the act of generating at least one comparison set includes an act of generating a randomly selected set from a larger group of set members.

8. The method according to claim 7, wherein the size of the at least one comparison set is approximately the same as the size of the measured set.

9. The method according to claim 1, further comprising an act of calculating a percentile ranking, wherein the acts of normalization occurs using a percentile ranking.

10. The method according to claim 1, wherein the at least one identifying characteristic comprises at least one of at least a portion of:

textual information within a document;

metadata associated with a document;

contextual information associated with a document;

non-textual information associated with a document;

record information with a database;

information associated with a composite entity; and

information derivable from a document.

11. The method according to claim 1, further comprising an act of calculating a statistical distribution for each one of at least one of the identifying characteristic.

12. The method according to claim 1, wherein the statistical distribution is determined for multiple dimensions.

13. The method according to claim 1, further comprising an act of determining at least one value associated with at least one set member.

14. The method according to claim 13, wherein the statistical distribution of at least one identifying characteristic is based on a plurality of the at least one values associated with at least one set member, and wherein the plurality of the at least one values comprise a relation.

15. The method according to claim 1, wherein the at least one identifying characteristic comprises at least one facet in a faceted information space.

16. The method according to claim 1, further comprising an act of generating a representation of the set, wherein the representation of the set is adapted to statistical manipulation.

17. The method according to claim 1, wherein the act of analyzing the set to obtain a statistical distribution further comprises an act of approximating the distribution.

18. The method according to claim 17, wherein the act of approximating the distribution includes an act of employing sampling to calculate the statistical distribution for a set of documents.

19. The method according to claim 17, wherein the act of approximating the distribution includes at least one of the acts of permitting modification of the set without recalculating the distribution, examining similar sets for similar distributions, and using previously analyzed sets to generate a statistical distribution, determining a maximal resolution, and determining a minimum threshold about zero.

20. The method according to claim 1, further comprising an act of assigning a weight value associated with at least one set member.

21. The method according to claim 20, wherein the act of generating a measurement of the distinctiveness for the set includes an act of accounting for the weight value associated with at least one set member.

22. The method according to claim 20, wherein the weight value comprises a relevance score and the method further comprises an act of determining if the relevance score exceeds a threshold.

23. The method according to claim 20, wherein the weight value comprises a relevance score and the method further comprises acts of:

modeling a distribution of relevance scores for relevant documents and a distribution of scores for less relevant documents; and

computing a separation between the modeled distributions.

24. The method according to claim 1, further comprising an act of smoothing the statistical distribution of the at least one identifying characteristic within the set.

25. The method according to claim 1, further comprising an act of calculating the measurement of distinctiveness with at least one function of relative entropy, Kullback-Leibler divergence, Euclidean distance, Manhattan distance, Hellinger distance, diversity difference, cosine difference, Jaccard distance, Jenson-Shannon divergence, and skew divergence.

26. The method according to claim 1, wherein the act of generating the measurement of distinctiveness further comprising acts of:

determining a similarity measure; and

inverting the sense of the similarity measure.

27. The method according to claim 26, wherein the similarity measure is calculated using at least one of Pearson correlation coefficient, Dice coefficient, overlap coefficient, and Lin similarity.

28. In an information retrieval system, a computer-implemented method for information processing, comprising:

analyzing a set of documents to obtain a statistical distribution based on values associated with the set of documents, the set of documents having a given size;

computing a value of a function that measures distinctiveness of the obtained statistical distribution relative to a baseline statistical distribution;

normalizing the value relative to a distribution of values of the function over a space of document sets, wherein each document set in the space has a size that is comparable to the given size; and

outputting a response derived from the normalized value.

29. The method as described in claim 28 wherein the set of documents is obtained as result of a query to the information retrieval system.

30. The method as described in claim 28, wherein the information retrieval system implements a Boolean retrieval model.

31. A computer-readable medium having computer-readable instructions stored thereon that define instructions that, as a result of being executed by a computer, instruct the computer to perform a method for measuring the distinctiveness of a set, the method comprising the acts of:

analyzing the set to obtain a statistical distribution of at least one identifying characteristic within the set;

generating a measurement of distinctiveness for the set based on the statistical distribution of the at least one identifying characteristic; and

normalizing the measurement of the distinctiveness of the set.

32. A system for measuring the distinctiveness of a set, the system comprising:

an analysis component adapted to obtain a statistical distribution of at least one identifying characteristic within a set;

a measurement component adapted to generate a measurement of distinctiveness for the set based on the statistical distribution of the at least one identifying characteristic; and

a normalization component adapted to normalize the statistical distribution of the at least one identifying characteristic of the measured set.

33. The system according to claim 32, wherein the set comprises at least one document, wherein the at least one document further comprises a unit of storage of digital data.

34. The system according to claim 32, wherein the normalization component is further adapted to calculate a mean for an expected statistical distribution of the at least one identifying characteristic.

35. The system according to claim 32, wherein the normalization component is further adapted to calculate a standard deviation for an expected statistical distribution of the at least one identifying characteristic.

36. The system according to claim 32, wherein the analysis component is further adapted to determine an expected statistical distribution of the at least one identifying characteristic for the set.

37. The system according to claim 36, further comprising a generation component adapted to generate at least one comparison set;

and wherein the analysis component is further adapted to determine a statistical distribution of at least one identifying characteristic for the comparison set.

38. The system according to claim 37, wherein the measurement component is further adapted to generate a measure of distinctiveness for the at least one comparison set.

39. The system according to claim 37, wherein the size of the at least one comparison set is approximately the same as the size of the measured set.

40. The system according to claim 32, wherein the at least one identifying characteristic comprises at least one of at least a portion of:

textual information within a document;

metadata associated with a document;

contextual information associated with a document;

non-textual information associated with a document;

record information with a database;

information associated with a composite entity; and

information derivable from a document.

41. The system according to claim 32, wherein the analysis component is further adapted to calculate a statistical distribution for each one of at least one of the identifying characteristics.

42. The system according to claim 32, wherein the statistical distribution is determined for multiple dimensions.

43. The system according to claim 32, further comprising a correlation component adapted to generate at least one value associated with at least one set member.

44. The system according to claim 32, wherein the at least one identifying characteristic comprises at least one facet in a faceted information space.

45. The system according to claim 32, further comprising an approximation component adapted to generate a representation of the set, wherein the representation of the set is adapted to statistical manipulation.

46. The system according to claim 32, wherein the analysis component is further adapted to approximate the distribution.

47. The system according to claim 46, wherein the analysis component is further adapted to sample the set to calculate the statistical distribution for a set of documents.

48. The system according to claim 32, further comprising a weighting component adapted to assign a weight value associated with at least one set member.

49. The system according to claim 48, wherein the measurement component is further adapted to account for the weight value associated with at least one set member in the measurement of distinctiveness.

50. The system according to claim 48, wherein the weight value comprises a relevance score, and the weighting component is further adapted to determine if the relevance score exceeds a threshold.

51. The system according to claim 32, further comprising a smoothing component adapted to smoothing the statistical distribution of the at least one identifying characteristic within the set.

52. The system according to claim 32, wherein the measurement component is further adapted to calculate the measurement of distinctiveness with at least one function of relative entropy, Kullback-Leibler divergence, Euclidean distance, Manhattan distance, Hellinger distance, diversity difference, cosine difference, Jaccard distance, Jenson-Shannon divergence, and skew divergence.

53. The system according to claim 32, wherein the measurement component is further adapted to determine a similarity measure, and invert a sense of the similarity measure.

54. A method for comparing the distinctiveness of a plurality of sets within a collection of information, the method comprising the acts of:

sampling, randomly, at least one set;

determining a statistical distribution of at least one identifying characteristic associated with elements of the at least one set;

generating a relative measurement of distinctiveness based on the statistical distributions of the at least one identifying characteristic associated with the elements of the at least one set and another set.

55. The method according to claim 54, wherein the act of sampling occurs against a result returned from the collection of information.

56. The method according to claim 54, wherein the act of sampling occurs against the collection of information.

57. The method according to claim 54, wherein at least one of the plurality of sets is a result produced by interaction with the collection of information.

58. The method according to claim 54, wherein the act of sampling, randomly, the at least one set further comprises an act of generating a sampled set of substantially same size as the another set.

59. The method according to claim 54, wherein the at least one set comprises at least one document, wherein the at least one document further comprises a unit of storage of digital data.

60. The method according to claim 54, wherein the at least one identifying characteristic comprises at least one of at least a portion of:

textual information within a document;

metadata associated with a document;

contextual information associated with a document;

non-textual information associated with a document;

record information with a database;

information associated with a composite entity; and

information derivable from a document.

61. The method according to claim 54, further comprising an act of calculating a statistical distribution for each one of at least one of the identifying characteristic.

62. The method according to claim 54, wherein the statistical distribution is determined against multiple dimensions.

63. The method according to claim 62, further comprising an act of determining at least one value associated with at least one set member.

64. The method according to claim 54, wherein the at least one identifying characteristic comprises at least one facet associated with a document.

65. The method according to claim 54, further comprising an act of generating a representation of the sampled set, wherein the representation of the sampled set is adapted to statistical manipulation.

66. The method according to claim 54, further comprising an act of assigning a weight value associated with at least one set member.

67. The method according to claim 54, wherein the measurement of distinctiveness is determined from at least one function of:

relative entropy, Kullback-Leibler divergence, Euclidean distance, Manhattan distance, Hellinger distance, diversity difference, cosine difference, Jaccard distance, Jenson-Shannon divergence, and skew divergence.

68. The method according to claim 54, wherein the act of generating the measurement of distinctiveness further comprising acts of:

determining a similarity measure; and

inverting the sense of the similarity measure.

69. A computer-readable medium having computer-readable instructions stored thereon that define instructions that, as a result of being executed by a computer, instruct the computer to perform a method for comparing the distinctiveness of a plurality of sets generated through interaction with a collection of information, the method comprising the acts of:

sampling, randomly, at least one set;

determining a statistical distribution of at least one identifying characteristic associated with elements of the at least one set;

generating a relative measurement of distinctiveness based on the statistical distributions of the at least one identifying characteristic associated with the elements of the at least one set and another set.

71. The system according to claim 69, wherein the sampling component samples against a result returned from the collection of information in response to interaction with a collection of information.

72. The system according to claim 69, wherein the act of sampling occurs against the collection of information.

73. The system according to claim 69, wherein at least one of the plurality of sets is a result produced by interaction with the collection of information.

74. The system according to claim 69, wherein the sampling component is further adapted to generate a sampled set of substantially same size as the another set.

75. The system according to claim 69, wherein the at least one set comprises at least one document, wherein the at least one document further comprises a unit of storage of digital data.

76. The system according to claim 69, wherein the at least one identifying characteristic comprises at least one of at least a portion of:

textual information within a document;

metadata associated with a document;

contextual information associated with a document;

non-textual information associated with a document;

record information with a database;

information associated with a composite entity; and

information derivable from a document.

77. The system according to claim 69, wherein the analysis component is further adapted to determine the statistical distribution against a plurality of identifying characteristics.

78. The system according to claim 69, further comprising a relation component adapted to determine at least one value associated with at least one set member.

79. The system according to claim 69, wherein the at least one identifying characteristic comprises at least one facet associated with a document.

80. The system according to claim 69, further comprising a representation component adapted to generate a representation of the sampled set adapted to statistical manipulation.

81. The system according to claim 69, further comprising a weighting component adapted to assign a weight value to at least one set member.

82. The system according to claim 81, wherein the weighting component is further adapted to maintain the associated weight value.

83. The system according to claim 69, wherein the measurement component is further adapted to determine the measurement of distinctiveness from at least one function of:

relative entropy, Kullback-Leibler divergence, Euclidean distance, Manhattan distance, Hellinger distance, diversity difference, cosine difference, Jaccard distance, Jenson-Shannon divergence, and skew divergence.

84. The system according to claim 69, wherein the measurement component is further adapted to determine a similarity measure, and invert the sense of the similarity measure.

70. A system for comparing the distinctiveness of a plurality of sets generated through interaction with a collection of information, the system comprising:

a sampling component adapted to randomly sample at least one set;

an analysis component adapted to determine a statistical distribution of at least one identifying characteristic associated with elements of the at least one set;

a measurement component adapted to determine a relative measurement of distinctiveness based on the statistical distributions of the at least one identifying characteristic associated with the elements of the at least one set and another set.