System and method for measuring the quality of document sets

• US 8,051,073 B2
• Filed: 06/25/2008
• Issued: 11/01/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): Breene; John E
• Assistant Examiner(s): PHILLIPS, III, ALBERT M
• Application Number:
  US12/146,225
• Publication Number:
  US 20090006384A1
• Time in Patent Office: 1,224 Days
• Field of Search: 707/723, 707/722, 707/759
• US Class Current: 707/722
• 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 improving interaction with a collection of information, the method comprising:

providing an interface wherein interaction with the collection of information occurs through the interface;

generating, by a computer system, a set of results based, at least in part, on a first interpretation of the interaction with the collection of information, wherein the set of results includes a plurality of results, and the set of results having a set size;

evaluating, by the computer system, the set of results using a measure of the distinctiveness of the set of results;

generating, by the computer system, at least one candidate set having a plurality of results and a candidate set size, based at least in part, on a second interpretation of the interaction with the collection of information;

comparing, by the computer system, the measure of distinctiveness of the set of results against a measure of distinctiveness of the at least one candidate set;

generating a second result for the interaction with the collection of information from at least the set of results and the at least one candidate set based on the comparison of the measures of distinctiveness; and

outputting, by the computer system, the second result in response to the act of comparing.

2. The method according to claim 1, wherein the act of evaluating the set of results further comprises using a normalized measurement of distinctiveness that accounts for a set size of a measured set.

3. The method according to claim 1, wherein the act of evaluating the set of results further comprises the act of generating a first sampled set.

4. The method according to claim 3, further comprising the acts of:

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

determining the measure of distinctiveness relative to the statistical distributions for the sampled set.

5. The method according to claim 1, further comprising an act of determining the measure of distinctiveness from a statistical distribution of at least one identifying characteristic in the set of results against a baseline statistical distribution.

6. The method according to claim 1, further comprising an act of approximating a statistical distribution of at least one identifying characteristic within the set of results.

7. The method according to claim 1, wherein the act of generating the at least one candidate set further comprises an act of modifying a query against the collection of information.

8. The method according to claim 7, further comprising an act of outputting the modified query.

9. The method according to claim 7, wherein the act of evaluating the set of results comprises acts of:

determining at least one identifying characteristic for the set of results; and

determining the contribution of the at least one identifying characteristic to the measure of distinctiveness.

10. The method according to claim 9, further comprising an act of establishing a threshold contribution to the measure of distinctiveness.

11. The method according to claim 9, wherein the act of modifying the query comprises reformulating the query based on the contribution of the at least one identifying characteristic.

12. The method according to claim 1, wherein the act of generating at least one candidate set further comprises an act of interpreting at least one component of the interaction.

13. The method of according to claim 12, wherein the act of interpreting the at least one component of the interaction includes and an of generating at least one candidate query.

14. The method of according to claim 13, further comprising an act of executing each of the candidate queries to produce at least one additional candidate set.

15. The method according to claim 12, further comprising an act of receiving a selection of output interpretations.

16. The method according to claim 1, further comprising an act of identifying similar candidate sets based on the act of comparing the measure of distinctiveness.

17. The method according to claim 16, further comprising an act of clustering the similar candidates by a measure of distinctiveness among the similar candidates.

18. The method according to claim 17, further comprising acts of:

outputting at least one cluster of similar candidates; and

receiving a selection of the at least one cluster.

19. The method according to claim 1, wherein the act of outputting the result in response to the act of comparing includes outputting at least one suggestion to improve a query based on the comparison of distinctiveness.

20. The method according to claim 1, wherein the act of outputting includes outputting a candidate query.

21. The method according to claim 1, wherein the act of outputting includes outputting a representation of the set of results and a representation of the at least one candidate set, and the method further comprises an act of receiving a selection of at least one of the representation of the set of results and the representation of the at least one candidate set.

22. The method according to claim 1, wherein the at least one candidate set is generated by an act of generating at least one superset of results as the at least one candidate set.

23. The method according to claim 22, wherein the act of comparing further comprises an act of identifying at least one interesting superset based on the distinctiveness measures.

24. The method according to claim 22, further comprising acts of:

outputting at least one cluster of a plurality of supersets; and

receiving a selection of the at least one cluster.

25. The method according to claim 1, wherein the interaction comprises navigation through the collection of information.

26. The method according to claim 25, further comprising an act of outputting the at least one candidate set in response to navigation of the collection of information.

27. The method according to claim 25, further comprising an act of identifying navigation options in response to comparing the measure of distinctiveness.

28. The method according to claim 27, wherein the act of identifying navigation options includes providing at least one of a visual cue, textual cue, auditory cue, and display within a graphical display.

29. 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 for improving interaction with a collection of information, the method comprising the acts of:

providing an interface wherein interaction with the collection of information occurs through the interface;

generating a set of results based, at least in part, on a first interpretation of the interaction with the collection of information, wherein the set of results includes a plurality of results, and the set of results having a set size;

evaluating the set of results using a measure of the distinctiveness of the set of results;

generating at least one candidate set, having a plurality of results and a candidate set size, based at least in part, on a second interpretation of the interaction with the collection of information;

comparing the measure of distinctiveness of the set of results against a measure of distinctiveness of the at least one candidate set, wherein the act of comparing includes generating a second result for the interaction with the collection of information from at least the set of results and the at least one candidate set; and

outputting the second result in response to the act of comparing.

30. A system for improving interaction with a collection of information, the system comprising:

at least one processor operatively connected to a memory, wherein the system is configured to execute system components, and the system further comprises;

an I/O engine adapted to output at least a portion of an interactive display, wherein the I/O engine is further adapted to output at least one option in response to the comparison made by an analysis engine;

a data retrieval engine adapted to generate a set of results, having a plurality of results and a set size, based, at least in part, on a first interpretation of an interaction with the collection of information;

an analysis engine adapted to evaluate the set of results using a measure of distinctiveness, wherein the analysis engine is further adapted to compare the measure of distinctiveness for the set of results against a measure of distinctiveness of a candidate set; and

a generation engine adapted to generate at least one candidate set, having a plurality of results and a candidate set size, based, at least in part, on a second interpretation of the interaction with the collection of information, wherein the generation engine is further configured to generate a second result for the interaction with the collection of information from at least the set of results and the at least one candidate set based on the compared measures of distinctiveness.

31. The system according to claim 30, wherein the analysis engine is further adapted to use a normalized measurement of distinctiveness that accounts for a set size of a measured set.

32. The system according to claim 30, wherein the analysis engine is further adapted to determine the measurement of distinctiveness from a statistical distribution of at least one identifying characteristic in the set of results against a baseline statistical distribution.

33. The system according to claim 30, wherein the analysis engine further comprises an approximation engine adapted to approximate a statistical distribution of at least one identifying characteristic within the set of results.

34. The system according to claim 30, wherein the analysis engine is further adapted to generate at least one additional candidate set.

35. The system according to claim 34, wherein the analysis engine is further adapted to modify a query against the collection of information.

36. The system according to claim 35, wherein the I/O engine is further adapted to output the modified query.

37. The system according to claim 34, wherein analysis engine is further adapted to:

determine at least one identifying characteristic; and

determine the contribution of the at least one identifying characteristic to the measure of distinctiveness.

38. The system according to claim 37, further comprising a management engine adapted to store a threshold contribution.

39. The system according to claim 37, further comprising a reformulation engine adapted to reformulate the query based on the contribution of the at least one identifying characteristic.

40. The system according to claim 39, wherein the reformulation engine is further adapted to repeat the reformulation of the query for each identifying characteristic.

41. The system according to claim 30, wherein the generation engine is further adapted to interpret at least one component of the interaction.

42. The method of according to claim 41, wherein generation engine is further adapted to generate at least one candidate query.

43. The system according to claim 41, wherein the I/O engine is further adapted to receiving a selection of output interpretations.

44. The system according to claim 30, wherein the analysis engine is further adapted to identify similar candidate sets based on the act of comparing the measure of distinctiveness.

45. The system according to claim 44, wherein the analysis engine is further adapted to cluster the similar candidates by a measure of distinctiveness among the similar candidates.

46. The system according to claim 45, wherein the I/O engine is further adapted to:

output at least one cluster of similar candidates; and

receive a selection of the at least one cluster.

47. The system according to claim 30, wherein the I/O engine is further adapted to output at least one suggestion to improve a query based on the comparison of distinctiveness score.

48. The system according to claim 30, wherein the I/O engine is further adapted to output a representation of the set of results and a representation of the at least one candidate set.

49. The system according to claim 48, wherein the I/O engine is further adapted to receive a selection of one of the representation of the set of results and the representation of the at least one candidate set.

50. The system according to claim 30, wherein generation engine is further adapted to generate at least one superset of results as the at least one candidate set.

51. The system according to claim 50, wherein the I/O engine is further adapted to output at least one cluster of the at least one superset of results and receive a selection of the at least one cluster.

52. The system according to claim 30, wherein the I/O engine is further adapted to accept navigation through the collection of information.

53. The system according to claim 52, wherein the I/O engine is further adapted to output the at least one candidate set in response to navigation of the collection of information.

54. The system according to claim 52, wherein the I/O engine is further adapted to identify navigation options in response to comparing the measure of distinctiveness.

55. The system according to claim 54, wherein the I/O engine is further adapted to provide at least one of a visual cue, textual cue, auditory cue, and display within a graphical display.