MEMBERSHIP CHECKING OF DIGITAL TEXT

• US 20090300014A1
• Filed: 06/03/2008
• Published: 12/03/2009
• Est. Priority Date: 06/03/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ganti, Venkatesh, Xin, Dong, Chakrabarti, Kaushik, Chaudhuri, Surajt
• Granted Patent: US 8,037,069 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 filter component configured to obtain a set of document sub-strings and to prune individual sub-strings from the set that cannot match database members; and

,

a verification component configured to receive a remainder of the set and to verify whether individual remaining sub-strings match individual database members.

2. The system of claim 1, wherein the filter component comprises a summary structure that can be constructed from the database members during a build phase.

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

4. The system of claim 3, wherein the less definitive tokens are high frequency 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 tokens that the summary structure can be stored in the allocated memory.

6. The system of claim 1, wherein the filter component comprises an inverted signature hashtable.

7. The system of claim 1, wherein the filter component employs a similarity function such that the pruned individual sub-strings have a similarity value with an individual database member that is below a predetermined threshold.

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

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

generating a summary structure relating to signatures of document sub-strings and database members; and

,

identifying instances where at least a certain number of token-signature pairs co-occur in an individual document sub-string and in an individual database member.

10. The computer-readable storage media of claim 9, wherein the generating a summary structure comprises obtaining token-signature pairs of the database members and eliminating some of the tokens of the database members to reduce an overall size of the summary structure.

11. The computer-readable storage media of claim 10, wherein the eliminating comprises eliminating individual tokens that have relatively low specificity to an individual database member.

12. The computer-readable storage media of claim 10, wherein the eliminating comprises eliminating individual tokens that occur with relatively high frequency in multiple database members.

13. The computer-readable storage media of claim 9, wherein the generating a summary structure comprises generating an inverted signature-based hashtable that compares token-signature pairs of the document sub-strings to token-signature pairs of the database members via a two-dimensional array.

14. The computer-readable storage media of claim 9, wherein the identifying includes generating token signature pairs for document sub-strings and checking whether a certain fraction of the token-signature pairs are present in an inverted signature-based hash table.

15. The computer-readable storage media of claim 9, wherein the identifying instances is achieved without merging lists of database member ids for each token in the document sub-string.

16. The computer-readable storage media of claim 9, further comprising employing a similarity function that determines whether similarity between individual document sub-strings and individual database members exceeds a predetermined value.

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

identifying candidate matches between document sub-strings and database members utilizing signatures; and

, verifying that the candidate matches are true matches.

18. The computer-readable storage media of claim 17, wherein the candidate identifying is achieved by looking up a relatively small number of token-signature pairs in a hash table.

19. The computer-readable storage media of claim 17, wherein the signatures are derived from the document sub-strings and wherein the identifying comprises comparing tokens of the signatures to tokens of the database members in a two-dimensional array.

20. The computer-readable storage media of claim 17, wherein the verifying also utilizes the signatures.