System and method for measuring the quality of document sets

• US 8,005,643 B2
• Filed: 06/25/2008
• Issued: 08/23/2011
• 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
• Primary Examiner(s): Le; John H
• Application Number:
  US12/146,161
• Publication Number:
  US 20090006382A1
• Time in Patent Office: 1,154 Days
• Field of Search: 702/57, 702 66- 67, 702/71, 702/84, 702179-181, 702/189, 707758-759, 707769-771, 715/229, 715/723
• US Class Current: 702/179
• 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 computer implemented method for measuring the distinctiveness of a result generated from a collection of electronically stored information, wherein the result is comprised of elements associated with the electronically stored collection of information, the method comprising:

accessing, by a computer system, a result generated from a collection of information;

establishing, automatically, by the computer system at least one identifying characteristic within the result;

analyzing, by the computer system, the result to automatically obtain a statistical distribution of the at least one identifying characteristic within the result;

generating, by the computer system, a measurement of distinctiveness for the result based on the statistical distribution of the at least one identifying characteristic within the result; and

comparing, by the computer system, the statistical distribution of the at least one identifying characteristic within the result against a baseline statistical distribution of the at least one identifying characteristic.

2. The method according to claim 1, further comprising an act of determining a baseline statistical distribution of the at least one identifying characteristic within the collection of information.

3. The method according to claim 2, further comprising an act of incorporating a weight value into the measurement of distinctiveness.

4. The method according to claim 2, further comprising an act of smoothing the statistical distribution of the at least one identifying characteristic.

5. The method according to claim 1, further comprising an act of predetermining the baseline statistical distribution of the at least one identifying characteristic.

6. The method according to claim 5, wherein the act of predetermining the baseline statistical distribution includes generating at least one random result within the collection of information.

7. The method according to claim 5, further comprising the acts of:

storing the baseline statistical distribution; and

retrieving the baseline statistical distribution for comparison.

8. The method according to claim 1, wherein the baseline statistical distribution further comprises a measurement of distinctiveness based on at least one identifying characteristic.

9. The method according to claim 1, further comprising an act of dynamically generating the baseline statistical distribution.

10. The method according to claim 9, wherein the act of dynamically generating the baseline statistical distribution includes generating at least one random result within the collection of information.

11. The method according to claim 10, wherein the act of generating the at least one random result is based on at least one of a size of the result set, a concentration of relevance of the result set, and a topicality of the result set.

12. The method according to claim 9, wherein the dynamically generated baseline distribution is adapted from previous execution of the act of analyzing the result to obtain a statistical distribution of at least one identifying characteristic within the result.

13. The method according to claim 1, wherein the collection of information comprises a collection of at least one document, and wherein the at least one document further comprises a unit of storage of digital data.

14. The method according to claim 13, wherein the at least one document further comprises at least one of a data record, within a database, textual information, non-textual information, audio, video, streaming data, a defined entity, a programmatically defined entity, metadata, and information derived from a document.

15. The method according to claim 1, wherein the result is generated from at least one of a query run against the collection of information, navigation within the collection of information, a search performed on the collection of information, a filter against the collection of information, a ranking operation, and a data mining operation performed on the collection of information.

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

17. The method according to claim 16, wherein the representation of the collection of information is used to determine the baseline statistical distribution.

18. The method according to claim 1, wherein the baseline distribution is determined by approximating a statistical distribution for at least one identifying characteristic within the collection of information.

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

20. The method according to claim 19, wherein the representation of the result is used to determine the statistical distribution.

21. The method according to claim 1, wherein the statistical distribution is determined by approximating a statistical distribution for at least one identifying characteristic within the result.

22. The method according to claim 21, wherein the act of approximating the statistical distribution includes at least one of the acts of permitting modification of the result without recalculating the distribution, examining similar results, and using previous analysis of at least one result to generate the statistical distribution.

23. The method according to claim 1, wherein the act of generating the measurement of distinctiveness further comprises an act of assigning a weight value to at least one member of the collection of information.

24. The method according to claim 1, further comprising an act of incorporating a weight value into the measurement of distinctiveness.

25. The method according to claim 1, wherein a 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.

26. The method according to claim 1, wherein the act of generating a 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 1, wherein the baseline statistical distribution is determined from a statistical distribution of the at least one identifying characteristic in another set composed of at least one element from the collection of information.

28. The method according to claim 27, wherein another set comprises at least one distinct element from the result.

29. A computer implemented method, operative in an information retrieval system, for improving a user'"'"'s interaction with data stored and accessible from the system, comprising:

relating, by the computer system, a first and second sets of items in the information retrieval system to generate a salience measure, wherein the act of relating includes acts of;

identifying, automatically by the computer system, at least one identifying characteristic within the first and second sets of items, and

calculating a statistical distribution of the at least one identifying characteristic to generate the salience measure; and

using, by the computer system, the salience measure to guide a subsequent user interaction with the information retrieval system, wherein the act of using the salience measure includes acts of;

generating, by the computer system, at least one refinement to present to the user during the user'"'"'s interaction with the data stored in the system, and

presenting the at least one refinement in a user interface on a host computer system accessed by the user.

30. The method as described in claim 29, wherein the first and second sets of items share a given characteristic.

31. The method as described in claim 30 wherein the given characteristic is set size.

32. The method as described in claim 30, wherein the given characteristic is concentration of relevance.

33. The method as described in claim 30 wherein the subsequent user interaction with the information retrieval system is one of:

guiding query interpretation, guiding view selection and summarization, intelligent ranges, event detection, concept triggers and interpreting user actions, hierarchy discovery, and adaptive data mining.

34. The method as described in claim 29, wherein the subsequent user interaction with the information retrieval system includes an act of guiding query interpretation.

35. A non transitory 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 measuring the distinctiveness of a result generated from a collection of information, wherein the result is comprised of elements associated with the collection of information, the method comprising the acts of:

accessing a result generated from a collection of information;

establishing, automatically, at least one identifying characteristic within the result;

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

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

comparing, by the computer system, the statistical distribution of the at least one identifying characteristic within the result against a baseline statistical distribution of the at least one identifying characteristic.

36. A system for measuring the distinctiveness of a result generated from a collection of information, wherein the result is comprised of elements associated with the collection of information, the system comprising:

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

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

a comparison component adapted to compare the measured statistical distribution against a baseline statistical distribution, wherein the comparison component is further adapted to determine that the compared statistical distribution exceeds a threshold for distinctiveness.

37. The system according to claim 36, wherein the measurement component is further adapted to determine a baseline statistical distribution for the collection of information for at least one identifying characteristic within the collection of information.

38. The system according to claim 36, further comprising a storage component adapted to store the baseline statistical distribution.

39. The system according to claim 38, further comprising a generation component adapted to generate a random result from the collection of information, and wherein the measurement component is further adapted to generate a baseline measurement from the at least one random result.

40. The system according to claim 38, further comprising an act of incorporating a weight value associated with the at least one identifying characteristic.

41. The system according to claim 38, further comprising an act of smoothing the statistical distribution of the at least one identifying characteristic.

42. The system according to claim 38, wherein a 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.

43. The system according to claim 36, wherein the baseline statistical distribution further comprises a measurement of distinctiveness based on at least one identifying characteristic.

44. The system according to claim 36, further comprising an act of dynamically generating the baseline statistical distribution.

45. The system according to claim 44, further comprising an act of generating the at least one random result based on the result, wherein the act of generating the at least one random result is based on at least one of a size of the result set, a concentration of relevance of the result set, and a topicality of the result set.

46. The system according to claim 44, wherein the dynamically generated baseline distribution is adapted from previous execution of the act of analyzing the result to obtain a statistical distribution of at least one identifying characteristic within the result.

47. The system according to claim 36, further comprising an act of generating at least one random result based on the size of the result.

48. The system according to claim 36, wherein the collection of information comprises a collection of at least one document, and wherein the at least one document further comprises a unit of storage of digital data.

49. The system according to claim 36, wherein the result is generated from at least one of a query run against the collection of information, navigation within the collection of information, a search performed on the collection of information, a filter on elements of the collection of information, a ranking of elements of the collection of information, and a data mining operation performed on the collection of information.

50. The system according to claim 36, further comprising an act of generating a representation of the collection of information, wherein the representation of the collection of information is adapted to statistical manipulation.

51. The system according to claim 36, wherein the baseline distribution is determined by approximating a statistical distribution for at least one identifying characteristic with the collection of information.

52. The system according to claim 36, further comprising an act of generating a representation of the result, wherein the representation of the result is adapted to statistical manipulation.

53. The system according to claim 36, wherein the statistical distribution is determined by approximating a statistical distribution for at least one identifying characteristic within the result.

54. The system according to claim 36, wherein the act of generating the measurement of distinctiveness further comprises an act of assigning a weight value to at least one member of the result.

55. The system according to claim 36, further comprising an act of incorporating a weight value associated with at least member of the collection of information into the act of determining the baseline statistical distribution.

56. The system according to claim 36, further comprising an act of incorporating a weight value associated with the at least one identifying characteristic.

57. The system according to claim 36, wherein the act of generating a measurement of distinctiveness further comprises acts of:

determining a similarity measure; and

inverting the sense of the similarity measure.