Method and apparatus for constructing a compact similarity structure and for using the same in analyzing document relevance

• US 20070136336A1
• Filed: 12/12/2005
• Published: 06/14/2007
• Est. Priority Date: 12/12/2005
• Status: Active Grant

• Current Assignee: Justsystems Evans Research Incorporated
• Original Assignee: Clairvoyance Corporation
• Inventors: Evans, David, Roma, Norbert, Shanahan, James
• Granted Patent: US 7,472,131 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A computer-readable medium comprises data structure for providing information about levels of similarity between pairs of N documents. The data structure comprises a plurality of entries of similarity values representing levels of similarity for a plurality of pairs of the documents. Each of the similarity values represents a level of similarity of one document of a given pair relative to the other document of the given pair. The similarity value of each entry is greater than a threshold similarity value that is greater than zero. The plurality of similarity-value entries are fewer than N²−N in number if the similarity values are asymmetric with regard to document pairing, and the plurality of similarity-value entries are fewer than $\frac{N^2-N}{2}$in number if the similarity values are symmetric with regard to document pairing. A method and apparatus for generating the data structure are described.

Claims

1. A method for constructing a data structure containing information about levels of similarity between pairs of documents of a set of documents, the method comprising:

obtaining similarity values for pairs of documents of the set of documents;

determining whether each of the similarity values is greater than or equal to a threshold similarity value; and

for each similarity value that is greater than the threshold similarity value, storing the similarity value in the data structure.

2. The method of claim 1, wherein obtaining similarity values for pairs of documents comprises:

performing multiple queries on the set of documents, each query being based upon a given document of the set of documents; and

scoring documents responsive to the queries, said scoring providing the similarity values.

3. The method of claim 2, wherein the queries produce lists of documents ranked according to similarity values, and wherein obtaining similarity values for pairs of documents comprises extracting similarity values from the lists only for those document pairs whose similarity values are greater than or equal to the threshold similarity value.

4. The method of claim 1, further comprising:

storing an entry comprising the threshold similarity value in the data structure; and

storing an entry comprising a default similarity value in the data structure.

5. The method of claim 4, wherein the default similarity value is equal to the threshold similarity value.

6. The method of claim 4, wherein the default similarity value is less than the threshold similarity value.

7. The method of claim 1, wherein the data structure comprises a plurality of entries of the similarity values, and wherein the plurality of entries of the similarity values are fewer than N²−

N in number if the similarity values are asymmetric with regard to document pairing and wherein the plurality of entries of the similarity values are fewer than

$\frac{N^2-N}{2}$

in number if the similarity values are symmetric with regard to document pairing.

8. A computer readable medium comprising processing instructions adapted to cause a processing unit to execute the method of claim 1.

9. A method for retrieving similarity values from a data structure for a set of documents, comprising:

accessing the data structure to determine whether the data structure contains an explicit entry for a similarity value for a given pair of documents;

if the data structure contains an explicit entry of the similarity value for the given pair of documents, retrieving the similarity value; and

if the data structure does not contain an explicit entry of the similarity value for the given pair of documents, retrieving a default similarity value from the data structure or from another memory location.

10. The method of claim 9, wherein the default similarity value is equal to the threshold similarity value.

11. The method of claim 9, wherein the default similarity value is less than the threshold similarity value.

12. The method of claim 9, wherein the data structure comprises a plurality of entries of the similarity values, and wherein the plurality of entries of the similarity values are fewer than N²−

N in number if the similarity values are asymmetric with regard to document pairing and wherein the plurality of entries of the similarity values are fewer than

$\frac{N^2-N}{2}$

in number if the similarity values are symmetric with regard to document pairing.

13. A computer readable medium comprising processing instructions adapted to cause a processing unit to execute the method of claim 9.

14. An apparatus for constructing a data structure containing information about levels of similarity between pairs of documents of a set of documents, comprising:

a memory; and

a processing unit coupled to the memory, wherein the processing unit is configured to execute the steps of;

obtaining similarity values for pairs of documents of the set of documents;

determining whether each of the similarity values is greater than or equal to a threshold similarity value; and

for each similarity value that is greater than the threshold similarity value, storing the similarity value in the data structure.

15. The apparatus of claim 14, wherein the processing unit is configured to obtain similarity values for pairs of documents of the set of documents by:

performing multiple queries on the set of documents, each query being based upon a given document of the set of documents; and

scoring documents responsive to the queries, said scoring providing the similarity values.

16. The apparatus of claim 15, wherein the queries produce lists of documents ranked according to similarity values, and wherein the processing unit is configured to obtain similarity values for pairs of documents by extracting similarity values from the lists only for those document pairs whose similarity values are greater than or equal to the threshold similarity value.

17. The apparatus of claim 14, wherein the data structure comprises a plurality of entries of the similarity values, and wherein the plurality of entries of the similarity values are fewer than N²−

N in number if the similarity values are asymmetric with regard to document pairing and wherein the plurality of entries of the similarity values are fewer than

$\frac{N^2-N}{2}$

in number if the similarity values are symmetric with regard to document pairing.

18. An apparatus for retrieving similarity values from a data structure for a set of documents, comprising:

a memory; and

a processing unit coupled to the memory, wherein the processing unit is configured to execute the steps of;

accessing the data structure to determine whether the data structure contains an explicit entry for a similarity value for a given pair of documents;

if the data structure contains an explicit entry of the similarity value for the given pair of documents, retrieving the similarity value; and

if the data structure does not contain an explicit entry of the similarity value for the given pair of documents, retrieving a default similarity value from the data structure or from another memory location.

19. The apparatus of claim 18, wherein the data structure comprises a plurality of entries of the similarity values, and wherein the plurality of entries of the similarity values are fewer than N²−

N in number if the similarity values are asymmetric with regard to document pairing and wherein the plurality of entries of the similarity values are fewer than

$\frac{N^2-N}{2}$

in number if the similarity values are symmetric with regard to document pairing.

20. The computer readable medium of claim 19, further comprising:

an entry comprising the threshold similarity value; and

an entry comprising a default similarity value.

21. The computer readable medium of claim 19, wherein the default similarity value is equal to the threshold similarity value.

22. The computer readable medium of claim 19, wherein the default similarity value is less than the threshold similarity value.

19-1. A computer-readable medium having stored thereon a data structure for providing information about levels of similarity between pairs of documents of a set of documents, the documents being N in number, the data structure comprising:

a plurality of entries of similarity values representing levels of similarity for a plurality of pairs of said documents, each of said similarity values representing a level of similarity of one document of a given pair relative to the other document of the given pair,

wherein the similarity value of each entry is greater than a threshold similarity value that is greater than zero, and

wherein the plurality of entries of similarity values are fewer than N²−

N in number if the similarity values are asymmetric with regard to document pairing and wherein the plurality of entries of similarity values are fewer than

$\frac{N^2-N}{2}$

in number if the similarity values are symmetric with regard to document pairing.