Method and apparatus for comparing scores in a vector space retrieval process

• US 7,356,604 B1
• Filed: 04/18/2000
• Issued: 04/08/2008
• Est. Priority Date: 04/18/2000
• Status: Expired due to Fees

• Current Assignee: Justsystems Evans Research Incorporated
• Original Assignee: Claritech Corporation
• Inventors: Roma, Norbert
• Primary Examiner(s): Cardone; Jason D
• Assistant Examiner(s): Pollack; Melvin H
• Application Number:
  US09/551,014
• Time in Patent Office: 2,912 Days
• Field of Search: 709/231, 709/219, 707/3, 707/6
• US Class Current: 709/231
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

The delivery ratio of r (which is a fraction between 0 and 1) partitions a stream of documents into a section of top scoring r-fraction of documents and the remainder. This way a set of successively bigger delivery ratios, r₁, r₂, r₃, . . . sections the stream into tiers. Any given document is assigned to a tier according to how many delivery ratio thresholds it matched or surpassed and how many it failed to reach. This creates a scoring structure which reflects the specificity of the document with respect to a profile in terms of density of relevant documents in the stream. In other words, a document in the k^th tier is such that it failed to be classified in the top r_k ratio of the stream (thus r_k fraction of the stream is more relevant to the given profile than the document under consideration). At the same time this document was classified as being in the top r_k−1 part of the stream. Thus this mechanism defines a score (let'"'"'s call it σ) for a document depending on how it compares to other documents in the stream when scored against a given profile.

Claims

1. A method for analyzing documents from a data source, comprising:

analyzing a reference corpus using a profile to determine reference corpus document scores indicative of content of documents in the reference corpus relative to the profile;

identifying a particular reference corpus document score that corresponds to a particular delivery ratio of documents of the reference corpus based on the analysis of the reference corpus;

assigning threshold scores to a multiplicity N of score threshold levels such that the particular reference corpus document score is assigned to be a threshold score for a given one of the N score threshold levels;

analyzing a data source using the profile and determining raw document scores for documents from the data source relative to the profile based upon the analysis of the data source;

comparing the raw document scores to the threshold scores of the N score threshold levels;

assigning normalized document scores to documents of the data source based on the comparison of the raw document scores to the threshold scores of the N score threshold levels as indicators of document relevancy to the profile; and

selecting a document based upon its normalized document score.

2. The method of claim 1, comprising assigning a tag to the document if the normalized document score of the document satisfies a relevance threshold, the tag being descriptive of content associated with the profile.

3. The method of claim 1, wherein the N score threshold levels correspond to N delivery ratios according to an exponential scaling function.

4. The method of claim 3, wherein the exponential scaling function is given by:

$r_k=\frac{1-a^{-k}}{1-a^{-\left(n+1\right)}}$

wherein k is an index for the score threshold levels and corresponds to an integerε

(0, n), n corresponds to an integer≧

1, aε

(1, ∞

), and r_k corresponds to a delivery ratio.

5. The method of claim 1, wherein the N score threshold levels correspond to N delivery ratios according to a power law function.

6. The method of claim 5, wherein the power law function is given by:

r_k=(k/(n+1))^(1/s) wherein k is an index for the score threshold levels, n corresponds to an integer≧

1 and sε

(1, ∞

).

7. The method of claim 1, wherein the data source comprises a data stream.

8. A method for analyzing documents from a data source, comprising:

analyzing a reference corpus using a first profile and a second profile to determine reference corpus document scores indicative of content of documents in the reference corpus relative to the first and second profiles;

identifying a first reference corpus document score that corresponds to a first delivery ratio of documents of the reference corpus based on the analysis of the reference corpus using the first profile;

identifying a second reference corpus document score that corresponds to a second delivery ratio of documents of the reference corpus based on the analysis of the reference corpus using the second profile;

for the first profile, assigning first threshold scores to a multiplicity N of score threshold levels such that the first reference corpus document score is assigned to be a threshold score for a given one of the N score threshold levels;

for the second profile, assigning second threshold scores to the N score threshold levels such that the second reference corpus document score is assigned to be a threshold score for the given one of the N score threshold levels;

analyzing a data source using the first and second profiles and determining first and second raw document scores for documents from the data source relative to the first and second profiles, respectively, based upon the analysis of the data source;

comparing the first and second raw document scores generated from the analyses of the data source to the respective first and second threshold scores of the N score threshold levels;

assigning first normalized document scores to documents of the data source based on the comparison of the first raw document scores to the first threshold scores of the N score threshold levels as indicators of document relevancy to the first profile;

assigning second normalized document scores to the documents of the data source based on the comparison of the second raw document scores to the second threshold scores of the N score threshold levels as indicators of document relevancy to the second profile; and

classifying a given document of the data source as being relevant to at least one of the first profile and the second profile if at least one of the first normalized document score and the second normalized document score of the given document, respectively, satisfy a relevance threshold.

9. The method of claim 8, comprising selecting the given document for transmission over a communications network.

10. The method of claim 8, wherein the N score threshold levels correspond to N delivery ratios according to an exponential scaling function.

11. The method of claim 10, wherein the exponential scaling function is given by:

$r_k=\frac{1-a^{-k}}{1-a^{-\left(n+1\right)}}$

wherein k is an index for the score threshold levels and corresponds to an integer ε

(0, n), n corresponds to an integer≧

1, aε

(1, ∞

), and r_k corresponds to a delivery ratio.

12. The method of claim 8, wherein the N score threshold levels correspond to N delivery ratios according to a power law function.

13. The method of claim 12, wherein the power law function is given by:

r_k=(k/(n+1))^(1/s) wherein k is an index for the score threshold levels, n corresponds to an integer≧

1 and sε

(1, ∞

).

14. The method of claim 8, comprising:

assigning a first tag to the given document if the first normalized score satisfies a first relevance threshold and assigning a second tag to the given document if the second normalized score satisfies a second relevance threshold; and

ranking the first and second tags according to relevance to the given document based upon the first normalized score and the second normalized score, the first and second tags being descriptive of content of the first and second profiles, respectively.

15. The method of claim 8, wherein the data source comprises a data stream.

16. A system for analyzing documents from a data source, comprising:

a memory; and

a processing system coupled to the memory,

wherein the processing system is configured to;

analyze a reference corpus using a profile to determine reference corpus document scores indicative of content of documents in the reference corpus relative to the profile;

identify a particular reference corpus document score that corresponds to a particular delivery ratio of documents of the reference corpus based on the analysis of the reference corpus;

assign threshold scores to a multiplicity N of score threshold levels such that the particular reference corpus document score is assigned to be a threshold score for a given one of the N score threshold levels;

analyze a data source using the profile and determine raw document scores for documents from the data source relative to the profile based upon the analysis of the data source;

compare the raw document scores to the threshold scores of the N score threshold levels;

assign normalized document scores to documents of the data source based on the comparison of the raw document scores to the threshold scores of the N score threshold levels as indicators of document relevancy to the profile; and

select a document based upon its normalized document score.

17. The system of claim 16, the processing system being configured to assign a tag to the document if the normalized document score of the document satisfies a relevance threshold, the tag being descriptive of content associated with the profile.

18. The system of claim 16, wherein the N score threshold levels correspond to N delivery ratios according to an exponential scaling function.

19. The system of claim 18, wherein the exponential scaling function is given by:

$r_k=\frac{1-a^{-k}}{1-a^{-\left(n+1\right)}}$

wherein k is an index for the score threshold levels and corresponds to an integerε

(0, n), n corresponds to an integer≧

1, aε

(1, ∞

), and r_k corresponds to a delivery ratio.

20. The system of claim 16, wherein the N score threshold levels correspond to N delivery ratios according to a power law function.

21. The system of claim 20, wherein the power law function is given by:

r_k=(k/(n+1))^(1/s) wherein k is an index for the score threshold levels, n corresponds to an integer≧

1 and sε

(1, ∞

).

22. The method of claim 16, wherein the data source comprises a data stream.

23. A system for analyzing documents from a data source, comprising:

a memory; and

a processing system coupled to the memory,

wherein the processing system is configured to;

analyze a reference corpus using a first profile and a second profile to determine reference corpus document scores indicative of content of documents in the reference corpus relative to the first and second profiles;

identify a first reference corpus document score that corresponds to a first delivery ratio of documents of the reference corpus based on the analysis of the reference corpus using the first profile;

identify a second reference corpus document score that corresponds to a second delivery ratio of documents of the reference corpus based on the analysis of the reference corpus using the second profile;

for the first profile, assign first threshold scores to a multiplicity N of score threshold levels such that the first reference corpus document score is assigned to be a threshold score for a given one of the N score threshold levels;

for the second profile, assign second threshold scores to the N score threshold levels such that the second reference corpus document score is assigned to be a threshold score for the given one of the N score threshold levels;

analyze a data source using the first and second profiles and determine first and second raw document scores for documents from the data source relative to the first and second profiles, respectively, based upon the analysis of the data source;

compare the first and second raw document scores generated from the analyses of the data source to the respective first and second threshold scores of the N score threshold levels;

assign first normalized document scores to documents of the data source based on the comparison of the first raw document scores to the first threshold scores of the N score threshold levels as indicators of document relevancy to the first profile;

assign second normalized document scores to the documents of the data source based on the comparison of the second raw document scores to the second threshold scores of the N score threshold levels as indicators of document relevancy to the second profile; and

classify a given document of the data source as being relevant to at least one of the first profile and the second profile if at least one of the first normalized document score and the second normalized document score of the given document, respectively, satisfy a relevance threshold.

24. The system of claim 23, wherein the processing system is configured to select the given document for transmission over a communications network.

25. The system of claim 23, wherein the N score threshold levels correspond to N delivery ratios according to an exponential scaling function.

26. The system of claim 25, wherein the exponential scaling function is given by:

$r_k=\frac{1-a^{-k}}{1-a^{-\left(n+1\right)}}$

wherein k is an index for the score threshold levels and corresponds to an integerε

(0, n), n corresponds to an integer≧

1, aε

(1, ∞

), and r_k corresponds to a delivery ratio.

27. The system of claim 23, wherein the N score threshold levels correspond to N delivery ratios according to a power law function.

28. The system of claim 27, wherein the power law function is given by:

r_k=(k/(n+1))^(1/s) wherein k is an index for the score threshold levels, n corresponds to an integer≧

1 and sε

(1, ∞

).

29. The system of claim 23, the processing system being configured to:

assign a first tag to the given document if the first normalized score satisfies a first relevance threshold and assign a second tag to the given document if the second normalized score satisfies a second relevance threshold; and

rank the first and second tags according to relevance to the given document based upon the first normalized score and the second normalized score, the first and second tags being descriptive of content of the first and second profiles, respectively.

30. The system of claim 23, wherein the data source comprises a data stream.

31. An article of manufacture comprising a computer readable medium having embodied therein computer readable program code for analyzing documents, the computer readable program code being adapted to cause a processing system to:

analyze a reference corpus using a profile to determine reference corpus document scores indicative of content of documents in the reference corpus relative to the profile;

identify a particular reference corpus document score that corresponds to a particular delivery ratio of documents of the reference corpus based on the analysis of the reference corpus;

assign threshold scores to a multiplicity N of score threshold levels such that the particular reference corpus document score is assigned to be a threshold score for a given one of the N score threshold levels;

analyze a data source using the profile and determine raw document scores for documents from the data source relative to the profile based upon the analysis of the data source;

compare the raw document scores to the threshold scores of the N score threshold levels;

assign normalized document scores to documents of the data source based on the comparison of the raw document scores to the threshold scores of the N score threshold levels as indicators of document relevancy to the profile; and

select a document based upon its normalized document score.

32. The article of claim 31, wherein computer readable program codes is adapted to cause the processing system to assign a tag to the document if the normalized document score of the document satisfies a relevance threshold, the tag being descriptive of content associated with the profile.

33. The article of claim 31, wherein the N score threshold levels correspond to N delivery ratios according to an exponential scaling function.

34. The article of claim 33, wherein the exponential scaling function is given by:

$r_k=\frac{1-a^{-k}}{1-a^{-\left(n+1\right)}}$

wherein k is an index for the score threshold levels and corresponds to an integerε

(0, n), n corresponds to an integer≧

1, aε

(1, ∞

), and r_k corresponds to a delivery ratio.

35. The article of claim 31, wherein the N score threshold levels correspond to N delivery ratios according to a power law function.

36. The article of claim 35, wherein the power law function is given by:

r_k=(k/(n+1))^(1/s) wherein k is an index for the score threshold levels, n corresponds to an integer≧

1 and sε

(1, ∞

).

37. The method of claim 31, wherein the data source comprises a data stream.

38. An article of manufacture comprising a computer readable medium having embodied therein computer readable program code for analyzing documents, the computer readable program code being adapted to cause a processing system to:

analyze a reference corpus using a first profile and a second profile to determine reference corpus document scores indicative of content of documents in the reference corpus relative to the first and second profiles;

identify a first reference corpus document score that corresponds to a first delivery ratio of documents of the reference corpus based on the analysis of the reference corpus using the first profile;

identify a second reference corpus document score that corresponds to a second delivery ratio of documents of the reference corpus based on the analysis of the reference corpus using the second profile;

for the first profile, assign first threshold scores to a multiplicity N of score threshold levels such that the first reference corpus document score is assigned to be a threshold score for a given one of the N score threshold levels;

for the second profile, assign second threshold scores to the N score threshold levels such that the second reference corpus document score is assigned to be a threshold score for the given one of the N score threshold levels;

analyze a data source using the first and second profiles and determine first and second raw document scores for documents from the data source relative to the first and second profiles, respectively, based upon the analysis of the data source;

compare the first and second raw document scores generated from the analyses of the data source to the respective first and second threshold scores of the N score threshold levels;

assign first normalized document scores to documents of the data source based on the comparison of the first raw document scores to the first threshold scores of the N score threshold levels as indicators of document relevancy to the first profile;

assign second normalized document scores to the documents of the data source based on the comparison of the second raw document scores to the second threshold scores of the N score threshold levels as indicators of document relevancy to the second profile; and

classify a given document of the data source as being relevant to at least one of the first profile and the second profile if at least one of the first normalized document score and the second normalized document score of the given document, respectively, satisfy a relevance threshold.

39. The article of claim 38, wherein the computer readable program code is adapted to cause the processing system to select the given document for transmission over a communications network.

40. The article of claim 38, wherein the N score threshold levels correspond to N delivery ratios according to an exponential scaling function.

41. The article of claim 40, wherein the exponential scaling function is given by:

$r_k=\frac{1-a^{-k}}{1-a^{-\left(n+1\right)}}$

wherein k is an index for the score thresholds and corresponds to an integerε

(0, n), n corresponds to an integer≧

1, aε

(1, ∞

)), and r_k corresponds to a delivery ratio.

42. The article of claim 38, wherein the N score threshold levels correspond to N delivery ratios according to a power law function.

43. The article of claim 42, wherein the power law function is given by:

r_k=(k/(n+1))^(1/s) wherein k is an index for the score thresholds, n corresponds to an integer≧

1 and sε

(1, ∞

).

44. The article of claim 38, wherein the computer readable program code is adapted to cause the processing system to:

assign a first tag to the given document if the first normalized score satisfies a first relevance threshold and assign a second tag to the given document if the second normalized score satisfies a second relevance threshold; and

rank the first and second tags according to relevance to the given document based upon the first normalized score and the second normalized score, the first and second tags being descriptive of content of the first and second profiles, respectively.

45. The article of claim 38, wherein the data source comprises a data stream.