SYSTEM AND METHOD FOR FILTERING DOCUMENTS

• US 20120330938A1
• Filed: 10/05/2011
• Published: 12/27/2012
• Est. Priority Date: 06/22/2011
• Status: Active Grant

• Current Assignee: Rogers Communications Inc.
• Original Assignee: Rogers Communications Inc.
• Inventors: LEE, Hyun Chul, BRAZIUNAS, Darius, CVET, Michael
• Granted Patent: US 8,898,151 B2
• Time in Patent Office: Days
• US Class Current: 707/723
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9536 Search customisation based on social or collaborative filtering

Abstract

A method and document separation system for separating a set of related documents is described. In one aspect, the method comprises: determining, on a document selection system, quality scores for a plurality of the documents in the set of related documents; obtaining a similarity score for a plurality of pairs of documents in the set of related document; and on a document selection system, obtaining a first subset of related documents which solves an optimization problem, the first subset of related documents including a portion of the document in the set of related documents, the optimization problem being a function of one or more quality scores of the documents assigned to the first subset of related documents and one or more similarity scores of pairs of documents assigned to the first subset of related documents.

Claims

1. A method of separating a set of related documents, the method comprising:

determining, on a document selection system, quality scores for a plurality of the documents in the set of related documents;

obtaining a similarity score for a plurality of pairs of documents in the set of related document; and

on the document selection system, obtaining a first subset of related documents which solves an optimization problem, the first subset of related documents being a subset of the set of related documents, the optimization problem being a function of one or more quality scores of the documents assigned to the first subset of related documents and one or more similarity scores of pairs of documents assigned to the first subset of related documents.

2. The method of claim 1, wherein the documents are micro blogs which are related by subject matter.

3. The method of claim 1, wherein the quality score for a document is determined based on the number of words or characters in that document.

4. The method of claim 1, wherein the quality score for a document is determined based on the percentage of words in that document which are listed in a dictionary.

5. The method of claim 1, wherein the quality score for a document is determined based on a language quality of that document.

6. The method of claim 1, wherein the quality score for a document is determined based on a number of subscribers associated with a content producer for that document.

7. The method of claim 1, wherein the quality score for a document is determined based on a number of times the document has been shared.

8. The method of claim 1, wherein the similarity score for a pair of documents is determined based on the number of terms which are common to both documents in the pair.

9. The method of claim 1, wherein the similarity score for a pair of documents is determined from the distance between term-frequency inverse document frequency vector representations of documents.

10. The method of claim 1, wherein the optimization problem maximizes an evaluation function and wherein the evaluation function is:

11. The method of claim 10, wherein, if a document, v, is assigned to the first subset of related documents, then:

u_v(v,A(v))=w_q⁰q(v)+w_r⁰(1−

r(v))+w_o⁰o(v),

and if a document is assigned to the second subset of related documents, then;

u_v(v,A(v))=w_q¹q(v)+w_r¹(r(v))+w_o¹o(v),

and if a first document v₁ and a second document v₂ are assigned to the same subset then;

u_E(v₁,v₂,A(v₁),A(v₂))=1−

s(v₁,v₂),

and if the first document v₁ and the second document v₂ are assigned to different subsets then;

u_E(v₁v₂,A(v₁),A(v₂))=s(v₁,v₂),

where w_q⁰ is a relevance score weight for documents in the first subset of related documents, w_q¹ is a relevance score weight for documents in the second subset of related documents, q(v) is a relevance score, w_r⁰ is a re-post score weight for documents in the first subset of related documents, w_r¹ is a re-post score weight for documents in the second subset of related documents, r(v) is a re-post score, w_o⁰ is a follower score weight for documents in the first subset of related documents, w_o¹ is a follower score weight for documents in the second subset of related documents, o(v) is a follower score and s(v₁,v₂) is a similarity score between the first document and the second document.

12. The method of claim 11, wherein obtaining a first subset of related documents which solves an optimization problem comprises:

performing a local search to identify a separation of documents into two or more subsets of related documents which represents a local optimization of the optimization problem.

13. The method of claim 12, where performing a local search comprises:

obtaining an initial separation of documents into the two or more subsets of related documents; and

iteratively swapping the set membership of a document in the first subset of related documents with a document in a second subset of related documents and determining, based on the optimization problem, whether the swap improves the optimization of the separation of documents and if not, returning the documents which were swapped back to the subset in which they were included prior to the swap.

14. The method of claim 13, wherein obtaining an initial separation of documents into the two or more subsets comprises:

separating the documents into the two or more subsets based on their quality score.

15. The method of claim 14, wherein separating the documents into the two or more subsets comprises:

placing a predetermined number of documents having higher relative quality scores in the first subset of related documents and placing documents having lower relative quality scores in a second subset of related documents.

16. The method of claim 1, wherein the optimization problem seeks to minimize the similarity between pairs of documents in the first subset of related documents and to maximize the quality of documents in the first subset of related documents.

17. A document separation system comprising:

a processor; and

a memory coupled to the processor, the memory storing processor executable instructions which, when executed by the processor cause the processor to;

determine quality scores for a plurality of the documents in the set of related documents;

obtain a similarity score for a plurality of pairs of documents in the set of related document; and

obtain a first subset of related documents which solves an optimization problem, the first subset of related documents being a subset of the set of related documents, the optimization problem being a function of one or more quality scores of the documents assigned to the first subset of related documents and one or more similarity scores of pairs of documents assigned to the first subset of related documents.

18. The method of claim 17, wherein the documents are micro blogs which are related by subject matter.

19. The document separation system of claim 17, wherein the processor executable instructions, when executed, cause the processor to determine the quality score for a document based on the number of words or characters in that document.

20. The document separation system of claim 17, wherein the processor executable instructions, when executed, cause the processor to determine the quality score for a document based on the percentage of words in that document which are listed in a dictionary.

21. The document separation system of claim 17, wherein the processor executable instructions, when executed, cause the processor to determine the quality score for a document based on a language quality of that document.

22. The document separation system of claim 17, wherein the processor executable instructions, when executed, cause the processor to determine the quality score for a document based on a number of subscribers associated with a content producer for that document.

23. The document separation system of claim 17, wherein the processor executable instructions, when executed, cause the processor to determine the quality score for a document based on a number of times the document has been shared.

24. The document separation system of claim 17, wherein the processor executable instructions, when executed, cause the processor to determine the similarity score for a pair of documents based on the number of terms which are common to both documents in the pair.

25. The document separation system of claim 17, wherein the processor executable instructions, when executed, cause the processor to determine the similarity score for a pair of documents from the distance between term-frequency inverse document frequency vector representations of documents.

26. The document separation system of claim 17, wherein the optimization problem maximizes an evaluation function and wherein the evaluation function is:

27. The document separation system of claim 26, wherein, if a document, v, is assigned to the first subset of related documents, then:

u_v(v,A(v))=w_q⁰q(v)+w_r⁰(1−

r(v))+w_o⁰o(v),

and if a document is assigned to the second subset of related documents, then;

u_v(v,A(v))=w_q¹q(v)+w_r¹(r(v))+w_o¹o(v),

and if a first document v₁ and a second document v₂ are assigned to the same subset then;

u_E(v₁,v₂,A(v₁),A(v₂))=1−

s(v₁,v₂),

and if the first document v₁ and the second document v₂ are assigned to different subsets then;

u_E(v₁,v₂,A(v₁),A(v₂))=s(v₁,v₂),

where w_q⁰ is a relevance score weight for documents in the first subset of related documents, w_q¹ is a relevance score weight for documents in the second subset of related documents, q(v) is a relevance score, w_r⁰ is a re-post score weight for documents in the first subset of related documents, w_r¹ is a re-post score weight for documents in the second subset of related documents, r(v) is a re-post score, w_o⁰ is a follower score weight for documents in the first subset of related documents, w_o¹ is a follower score weight for documents in the second subset of related documents, o(v) is a follower score and s(v₁,v₂) is a similarity score between the first document and the second document.

28. The document separation system of claim 17, wherein obtaining a first subset of related documents which solves an optimization problem comprises:

performing a local search to identify a separation of documents into two or more subsets of related documents which represents a local optimization of the optimization problem.

29. The document separation system of claim 28, where performing a local search comprises:

obtaining an initial separation of documents into the two or more subsets of related documents; and

iteratively swapping the set membership of a document in the first subset of related documents with a document in a second subset of related documents and determining, based on the optimization problem, whether the swap improves the optimization of the separation of documents and if not, returning the documents which were swapped back to the subset in which they were included prior to the swap.

30. The document separation system of claim 29, wherein obtaining an initial separation of documents into the two or more subsets comprises:

separating the documents into the two or more subsets based on their quality score.

31. The document separation system of claim 30, wherein separating the documents into the two or more subsets comprises:

placing a predetermined number of documents having higher relative quality scores in the first subset of related documents and placing documents having lower relative quality scores in a second subset of related documents.

32. The document separation system of claim 17, wherein the optimization problem seeks to minimize the similarity between pairs of documents in the first subset of related documents and to maximize the quality of documents in the first subset of related documents.