Method and apparatus for dynamic relevance ranking

• US 6,119,114 A
• Filed: 09/17/1997
• Issued: 09/12/2000
• Est. Priority Date: 09/17/1996
• Status: Expired due to Fees

• Current Assignee: Secure Computing Corporation (McAfee, LLC)
• Original Assignee: Elron Electronic Industries Ltd. (IDB Holding Corporation Limited)
• Inventors: Smadja, Frank
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/932,643
• Time in Patent Office: 1,091 Days
• Field of Search: 707/5, 707/4, 707/3, 707/103, 707/200, 707/2, 707/7, 395/650, 395/200.33, 395/200.31
• US Class Current: 1/1
• CPC Class Codes: G06F 16/337 Profile generation, learning or modification
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

The present invention provides a method and apparatus for implementing dynamic relevance ranking. The method includes the step of registering a profile. A newly received document is dynamically filtered with the profile. Registration is performed by entering the profile, and searching training data in accordance with the profile. The training data is searched by determining the relevance score of documents in the training data. The documents in the training data are ranked to form a list. The least relevant document in the list is specified.

Claims

1. In a computer system, a method for providing a user with newly-received documents having a selected range of relevance, said method comprising the computer-implemented steps of:

providing a first set of training data having plurality of training documents, said first set of training data having a first collective absolute relevance indicative of an extent to which said plurality of training documents includes preferred content;

specifying a relative relevance threshold indicative of a relevance of desired newly-received documents relative to said first collective absolute relevance;

selecting, for said first set of training data, a selected range bounded by an absolute-relevance threshold corresponding to said relative relevance threshold;

determining whether a newly-received document has an absolute-relevance score within said range, said absolute relevance score being indicative of an extent to which said newly-received document includes preferred content.

2. The method of claim 1 further comprising the step of generating a user-profile indicative of said preferred content.

3. The method of claim 1 further comprising the step of

determining, on the basis of said absolute-relevance score of said newly-received document and said first collective absolute relevance, whether to replace said first set of training data by a second set of training data formed by adding said newly-received document to said first set of training data.

4. The method of claim 3 wherein the step of determining whether to replace said first set of training data further comprises the steps of:

evaluating an absolute relevance for said newly-received document;

selecting, on the basis of said relative relevance threshold, a first training document to be a least-relevant document;

determining whether said newly-received document has a higher absolute relevance score than said least-relevant document;

if said newly-received document has a higher absolute relevance score than said least-relevant document, replacing said first set of training data with a second set of training data formed by incorporating said newly-received document into said plurality of training documents; and

selecting, on the basis of said relative-relevance threshold, a second training document from said second set of training data to be said least-relevant document, said second training document having a higher absolute relevance score than said first training document;

whereby successive newly-received documents require progressively higher absolute relevance scores to surpass said relative relevance threshold.

5. The method of claim 3 wherein said step of determining whether to replace said first set of training data comprises the step of including said newly-received document in said first set of training data to create a second set of training data having a second collective absolute relevance higher than said first collective absolute relevance.

6. The method of claim 5, wherein said step of selecting a first training document to be a least-relevant document comprises the steps of:

determining an absolute relevance score of each of said plurality of training documents in said first set of training data, each absolute relevance score being indicative of an extent to which said training document includes preferred content;

sorting said plurality of training documents in said first set of training data on the basis of their absolute relevance scores to form a sorted list; and

specifying a least relevant training document in said sorted list.

7. The method of claim 6, further comprising the steps of:

determining, on the basis of said absolute relevance score of said newly-received document and said absolute relevance scores of each of said plurality of training documents, a rank of said newly-received document relative to each of said plurality of training documents; and

inserting said newly-received document into said sorted list according to said rank.

8. The method of claim 7, further comprising the step of presenting said sorted list of relevant documents, including said newly-received document, to a user.

9. The method of claim 7, wherein said step of determining said rank comprises the step of performing a binary search on said plurality of training documents to determine a first training document and a second training document having absolute relevance scores above and below said absolute relevance score of said newly-received document.

10. The method of claim 9, wherein said sorted list includes a most relevant document having an absolute relevance score higher than said absolute relevance scores of all other training documents in said sorted list and a least relevant document having an absolute relevance score lower than said absolute relevance scores of all other training documents in said sorted list, and wherein said step of performing a binary search comprises the step of comparing said absolute relevance score of said newly-received document with a statistical average of said absolute relevance scores of said most relevant document and said least relevant document.

11. The method of claim 10, wherein said comparing step comprises the step of comparing said absolute relevance score of said newly-received document with an absolute relevance score proximate to said statistical average of said absolute relevance scores of said most relevant document and said least relevant document.

12. A computer-readable medium having, encoded thereon, software for providing a user with newly-received documents having a selected range of relevance, said software comprising instructions for executing the steps of:

providing a first set of training data having plurality of training documents, said first set of training data having a first collective absolute relevance indicative of an extent to which said plurality of training documents includes preferred content;

specifying a relative relevance threshold indicative of a relevance of desired newly-received documents relative to said first collective absolute relevance;

selecting, for said first set of training data, a selected range bounded by an absolute-relevance threshold corresponding to said relative relevance threshold;

determining whether a newly-received document has an absolute-relevance score within said range, said absolute relevance score being indicative of an extent to which said newly-received document includes preferred content.

13. The computer-readable medium of claim 12 wherein said instructions further comprise instructions for executing the step of generating a user-profile indicative of said preferred content.

14. The computer-readable medium of claim 12 wherein said instructions further comprise instructions for executing the step of

determining, on the basis of said absolute-relevance score of said newly-received document and said first collective absolute relevance, whether to replace said first set of training data by a second set of training data formed by adding said newly-received document to said first set of training data.

15. The computer-readable medium of claim 14 wherein said instructions for executing said step of determining whether to replace said first set of training data comprise instructions for executing the step of including said newly-received document in said first set of training data to create a second set of training data having a second collective absolute relevance higher than said first collective absolute relevance.

16. The computer-readable medium of claim 14 wherein said instructions for executing said step of determining whether to replace said first set of training data further comprise instructions for executing the steps of:

evaluating an absolute relevance for said newly-received document;

selecting, on the basis of said relative relevance threshold, a first training document to be a least-relevant document;

determining whether said newly-received document has a higher absolute relevance score than said least-relevant document;

if said newly-received document has a higher absolute relevance score than said least-relevant document, replacing said first set of training data with a second set of training data formed by incorporating said newly-received document into said plurality of training documents; and

selecting, on the basis of said relative-relevance threshold, a second training document from said second set of training data to be said least-relevant document, said second training document having a higher absolute relevance score than said first training document;

whereby successive newly-received documents require progressively higher absolute relevance scores to surpass said relative relevance threshold.

17. The computer-readable medium of claim 16, wherein said instructions for executing the step of selecting a first training document to be a least-relevant document comprise instructions for executing the steps of:

determining an absolute relevance score of each of said plurality of training documents in said first set of training data, each absolute relevance score being indicative of an extent to which said training document includes preferred content;

sorting said plurality of training documents in said first set of training data on the basis of their absolute relevance scores to form a sorted list; and

specifying a least relevant training document in said sorted list.

18. The computer-readable medium of claim 17, wherein said sorted list includes a most relevant document having an absolute relevance score higher than said absolute relevance scores of all other training documents in said sorted list and a least relevant document having an absolute relevance score lower than said absolute relevance scores of all other training documents in said sorted list, and wherein said step of performing a binary search comprises the step of comparing said absolute relevance score of said newly-received document with a statistical average of said absolute relevance scores of said most relevant document and said least relevant document.

19. The computer-readable medium of claim 18, wherein said instructions for executing said comparing step comprise instructions for executing the step of comparing said absolute relevance score of said newly-received document with an absolute relevance score proximate to said statistical average of said absolute relevance scores of said most relevant document and said least relevant document.

20. The computer-readable medium of claim 17, wherein said software further comprises instructions for executing the steps of:

determining, on the basis of said absolute relevance score of said newly-received document and said absolute relevance scores of each of said plurality of training documents, a rank of said newly-received document relative to each of said plurality of training documents; and

inserting said newly-received document into said sorted list according to said rank.

21. The computer-readable medium of claim 20, wherein said instructions further comprise instructions for executing the step of presenting said sorted list of relevant documents, including said newly-received document, to a user.

22. The computer-readable medium of claim 20, wherein said instructions for executing said step of determining said rank comprise instructions for executing the step of performing a binary search on said plurality of training documents to determine a first training document and a second training document having absolute relevance scores above and below said absolute relevance score of said newly-received document.

23. A computer system for providing a user with newly-received documents having a selected range of relevance, said system comprising:

a computer-readable representation of a first set of training data having a plurality of training documents, said first set of training data having a first collective absolute relevance indicative of an extent to which said plurality of training documents includes preferred content;

means for specifying a relative relevance threshold indicative of a relevance of desired newly-received documents relative to said first collective absolute relevance;

selection means for selecting, for said first set of training data, a selected range bounded by an absolute-relevance threshold corresponding to said relative relevance threshold;

means for determining whether a newly-received document has an absolute-relevance score within said range, said absolute relevance score being indicative of an extent to which said newly-received document includes preferred content.

24. The system of claim 23 further comprising means for generating a user-profile indicative of said preferred content.

25. The system of claim 23 further comprising:

means for determining, on the basis of said absolute-relevance score of said newly-received document and said first collective absolute relevance, whether to replace said first set of training data by a second set of training data formed by adding said newly-received document to said first set of training data.

26. The system of claim 25 wherein said means for determining whether to replace said first set of training data comprises means for including said newly-received document in said first set of training data to create a second set of training data having a second collective absolute relevance higher than said first collective absolute relevance.

27. The system of claim 25 wherein said means for determining whether to replace said first set of training data further comprises:

relevance-evaluation means for evaluating an absolute relevance for said newly-received document;

means for selecting, on the basis of said relative relevance threshold, a first training document to be a least-relevant document;

means for determining whether said newly-received document has a higher absolute relevance score than said least-relevant document;

means for replacing said first set of training data with a second set of training data formed by incorporating said newly-received document into said plurality of training documents; and

means for selecting, on the basis of said relative-relevance threshold, a second training document from said second set of training data to be said least-relevant document, said second training document having a higher absolute relevance score than said first training document.

28. The system of claim 27, wherein said means for selecting a first training document to be a least-relevant document comprises:

scoring means for determining an absolute relevance score of each of said plurality of training documents in said first set of training data, each absolute relevance score being indicative of an extent to which said training document includes preferred content;

sorting means for sorting said plurality of training documents in said first set of training data on the basis of their absolute relevance scores to form a sorted list; and

means for specifying a least relevant training document in said sorted list.

29. The system of claim 28, further comprising:

ranking means for determining, on the basis of said absolute relevance score of said newly-received document and said absolute relevance scores of each of said plurality of training documents, a rank of said newly-received document relative to each of said plurality of training documents; and

inserting said newly-received document into said sorted list according to said rank.

30. The system of claim 29, further comprising display means for presenting said sorted list of relevant documents, including said newly-received document, to a user.

31. The system of claim 29, wherein said ranking means comprises binary search means for identifying a first training document and a second training document having absolute relevance scores above and below said absolute relevance score of said newly-received document.

32. The system of claim 31, wherein said sorted list includes a most relevant document having an absolute relevance score higher than said absolute relevance scores of all other training documents in said sorted list and a least relevant document having an absolute relevance score lower than said absolute relevance scores of all other training documents in said sorted list, and wherein said binary search means comprises comparison means for comparing said absolute relevance score of said newly-received document with a statistical average of said absolute relevance scores of said most relevant document and said least relevant document.

33. The system of claim 32, wherein said comparison means comprises means for comparing said absolute relevance score of said newly-received document with an absolute relevance score proximate to said statistical average of said absolute relevance scores of said most relevant document and said least relevant document.