Comparing values of a bounded domain

• US 8,176,407 B2
• Filed: 03/02/2010
• Issued: 05/08/2012
• Est. Priority Date: 03/02/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dickinson, Grant
• Primary Examiner(s): Ton, David
• Application Number:
  US12/715,402
• Publication Number:
  US 20110219289A1
• Time in Patent Office: 798 Days
• Field of Search: 707/204, 707/101, 707/2, 707/780, 715/501.1, 714/819
• US Class Current: 714/819
• CPC Class Codes: G06F 11/07 Responding to the occurrence of a fault, e.g. fault tolerance
• CPC Class Codes: G06F 16/2468 Fuzzy queries
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

Methods, systems, and computer-readable media to compare values of a bounded domain are disclosed. A particular method includes, for each value in a bounded domain, determining a corresponding set of allowable errors associated with the value. The sets of allowable errors are stored at a memory. The method includes determining a comparison score between a first value of the bounded domain and a second value of the bounded domain based on a comparison of a first set of allowable errors corresponding to the first value and a second set of allowable errors corresponding to the second value.

Claims

1. A computer-implemented method, comprising:

for each value in a bounded domain, determining a corresponding set of allowable errors associated with the value;

storing the sets of allowable errors at a memory; and

determining a comparison score between a first value of the bounded domain and a second value of the bounded domain based on a comparison of a first set of allowable errors corresponding to the first value and a second set of allowable errors corresponding to the second value.

2. The computer-implemented method of claim 1, wherein the corresponding set of allowable errors includes a typographical error, a range error, a transposition error, a transliteration error, or any combination thereof.

3. The computer-implemented method of claim 1, wherein the bounded domain is one of a finite numeric domain, a date domain, a finite color spectrum domain, a list domain, and an enumerated set domain.

4. The computer-implemented method of claim 1, wherein each allowable error in a particular set of allowable errors is within the bounded domain.

5. The computer-implemented method of claim 1, wherein storing a particular set of allowable errors comprises storing a bitmask that is representative of the particular set at the memory.

6. The computer-implemented method of claim 1, wherein the bitmask is represented by one of a 32-bit unsigned integer, a 64-bit unsigned integer, a 128-bit unsigned integer, and a globally unique identifier (GUID).

7. The computer-implemented method of claim 6, wherein storing the particular set of allowable errors further comprises storing a count of logical true bits of the bitmask at the memory.

8. The computer-implemented method of claim 7, wherein determining the comparison score comprises:

retrieving a first bitmask and a first count corresponding to the first value from the memory;

retrieving a second bitmask and a second count corresponding to the second value from the memory; and

determining a similarity score based on the first bitmask and the second bitmask.

9. The computer-implemented method of claim 8, wherein determining the similarity score based on the first bitmask and the second bitmask comprises:

calculating a logical intersection of the first bitmask and the second bitmask;

determining a third count representative of a number of logical true bits of the logical intersection;

calculating a logical union of the first bitmask and the second bitmask;

determining a fourth count representative of a number of logical true bits of the logical union; and

calculating a quotient of the third count and the fourth count.

10. The computer-implemented method of claim 9, wherein determining the fourth count comprises subtracting the third count from a sum of the first count and the second count.

11. The computer-implemented method of claim 1, wherein the memory comprises random access memory (RAM) at a computer system, disk-based storage at a computer system, or any combination thereof.

12. The computer-implemented method of claim 11, wherein the comparison score is determined during a run-time of the computer system and wherein the sets of allowable errors are stored prior to the run-time of the computer system.

13. The computer-implemented method of claim 1, wherein the sets of allowable errors are stored as one of constants at a software program and immutable data.

14. The computer-implemented method of claim 1, further comprising separating a particular value of the bounded domain into a plurality of ngrams and determining a corresponding set of allowable errors for each of the plurality of ngrams.

15. The computer-implemented method of claim 1, wherein the sets of allowable errors are computed in linear time with respect to a size of the bounded domain and wherein the comparison score is computed in constant time with respect to the size of the bounded domain.

16. The computer-implemented method of claim 1, further comprising:

when the comparison score is less than a similarity threshold, outputting an indication that the first value and the second value are dissimilar; and

when the comparison score is greater than or equal to the similarity threshold, outputting an indication that the first value and the second value are similar.

17. A computer system, comprising:

a processor; and

a memory coupled to the processor, the memory storing instructions, that when executed by the processor, cause execution of fuzzy matching logic comprising;

a computation component configured to, for each of a plurality of values in a bounded domain;

determine a set of allowable errors for the value; and

store the set of allowable errors at the memory; and

a run-time comparison component configured to determine a comparison score between a first value and a second value in the bounded domain based on a first set of allowable errors corresponding to the first value and a second set of allowable errors corresponding to the second value.

18. The computer system of claim 17, wherein the fuzzy matching logic is integrated into a user interface, a word processing application, a spreadsheet application, a database application, a dynamically linked library (DLL), or any combination thereof.

19. A computer-readable medium comprising instructions, that when executed by a computer, cause the computer to:

for each value in a bounded domain, determine a corresponding set of allowable errors associated with the value;

performing a hashing operation on the sets of allowable errors, wherein performing the hashing operation on a particular set of allowable errors results in a bitmask that is representative of the particular set and a count of logical true bits of the bitmask;

store the bitmasks and counts in a statically allocated portion of memory;

receive a first value within the bounded domain and a second value within the bounded domain;

retrieve a first bitmask and a first count corresponding to the first value and a second bitmask and a second count corresponding to the second value from the memory; and

determine a Jaccard score of the first bitmask and the second bitmask.

20. The computer-readable medium of claim 19, wherein the bounded domain is an ordered domain.