Membership checking of digital text

• US 8,037,069 B2
• Filed: 06/03/2008
• Issued: 10/11/2011
• Est. Priority Date: 06/03/2008
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chakrabarti, Kaushik, Chaudhuri, Surajt, Ganti, Venkatesh, Xin, Dong
• Primary Examiner(s): MORRISON, JAY A
• Application Number:
  US12/132,108
• Publication Number:
  US 20090300014A1
• Time in Patent Office: 1,225 Days
• Field of Search: None
• US Class Current: 707/736
• CPC Class Codes: G06F 16/353 into predefined classes

Abstract

The described implementations relate to data analysis, such as membership checking. One technique identifies candidate matches between document sub-strings and database members utilizing signatures. The technique further verifies that the candidate matches are true matches.

Claims

1. A system, comprising:

a data structure populated with document tokens selected from signatures of documents and member tokens selected from database members, the data structure including entries identifying co-occurrences of the document tokens and the member tokens;

a filter component configured to identify individual documents that cannot match individual database members using the co-occurrences identified in the data structure;

a verification component configured to receive a remainder of the documents and to verify whether sub-strings of the remainder of the documents match the individual database members; and

at least one computing device configured to execute one or more of the filter component or the verification component.

2. The system of claim 1, wherein the data structure comprises a summary structure constructed from the database members during a build phase.

3. The system of claim 1, wherein the data structure comprises a summary structure pre-populated with token-signature pairs of the database members and wherein relatively less definitive member tokens are eliminated to decrease an overall size of the summary structure.

4. The system of claim 3, wherein the relatively less definitive member tokens are high frequency member tokens.

5. The system of claim 3, wherein the filter component is configured to ascertain a local memory allocation for the summary structure and to eliminate sufficient numbers of the relatively less definitive member tokens such that the summary structure can be stored in the local memory allocation.

6. The system of claim 1, wherein the data structure comprises an inverted signature-based hashtable.

7. The system of claim 1, wherein the filter component employs a similarity function to prune individual sub-strings that have similarity values with the individual database members below a predetermined threshold.

8. The system of claim 1, wherein the verification component employs fuzzy matching to verify the sub-strings.

9. A method comprising:

populating a data structure with document tokens selected from signatures of documents and member tokens selected from database members, the data structure including entries identifying co-occurrences of the document tokens and the member tokens;

identifying individual documents that cannot match individual database members using the co-occurrences identified in the data structure;

receiving a remainder of the documents; and

verifying whether sub-strings of the remainder of the documents match the individual database members.

10. The method of claim 9, wherein the data structure comprises a summary structure, the method further comprising pre-populating the summary structure with token-signature pairs of the database members and wherein relatively less definitive member tokens are eliminated to decrease an overall size of the summary structure.

11. The method of claim 10, wherein the relatively less definitive member tokens are high frequency member tokens.

12. The method of claim 10, further comprising ascertaining a local memory allocation for the summary structure and eliminating sufficient numbers of the relatively less definitive member tokens such that the summary structure can be stored in the local memory allocation.

13. The method of claim 9, wherein the data structure comprises an inverted signature-based hashtable.

14. The method of claim 9, wherein the identifying comprises employing a similarity function to prune individual sub-strings that have similarity values with the individual database members below a predetermined threshold.

15. A computer-readable storage media having instructions stored thereon that when executed by a computing device cause the computing device to perform acts, comprising:

populating a data structure with document tokens selected from signatures of documents and member tokens selected from database members, the data structure including entries identifying co-occurrences of the document tokens and the member tokens;

identifying individual documents that cannot match individual database members using the co-occurrences identified in the data structure;

receiving a remainder of the documents; and

verifying whether sub-strings of the remainder of the documents match the individual database members.

16. The computer-readable storage media of claim 15, wherein the data structure comprises a summary structure, the acts further comprising pre-populating the summary structure with token-signature pairs of the database members and wherein relatively less definitive member tokens are eliminated to decrease an overall size of the summary structure.

17. The computer-readable storage media of claim 16, wherein the relatively less definitive member tokens are high frequency member tokens.

18. The computer-readable storage media of claim 16, the acts further comprising ascertaining a local memory allocation for the summary structure and eliminating sufficient numbers of the relatively less definitive member tokens such that the summary structure can be stored in the local memory allocation.

19. The computer-readable storage media of claim 15, wherein the data structure comprises an inverted signature-based hashtable.

20. The computer-readable storage media of claim 15, wherein the identifying comprises employing a similarity function to prune individual sub-strings that have similarity values with the individual database members below a predetermined threshold.