Large scale item representation matching

• US 7,818,278 B2
• Filed: 06/14/2007
• Issued: 10/19/2010
• Est. Priority Date: 06/14/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Suponau, Dima, Yu, Wei, Padovitz, Amir J., Bilenko, Mikhail
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): Fernandez Rivas; Omar F
• Application Number:
  US11/763,200
• Publication Number:
  US 20080313111A1
• Time in Patent Office: 1,223 Days
• Field of Search: 706/8, 706/45, 706/46, 706/48, 706/52, 706/55, 706/62, 707/1, 707/2, 707/6
• US Class Current: 706/52
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/2468 Fuzzy queries
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches
• CPC Class Codes: Y10S 707/917 Text

Abstract

A two-phase process quickly and accurately identifies representations of the same items within a collection of item representations. In the first phase, referred to as a “blocking phase,” frequency information indicating the frequency with which terms appear within the collection of item representations is used to quickly identify “candidate pairs” (i.e., pairs of item representations that have a relatively high probability of matching). The blocking phase results in a reduced subset of the data for further analysis during the second phase. In the second phase, referred to as a “matching phase,” the candidate pairs are analyzed using fuzzy matching functions to accurately identify “matching pairs” (i.e., representations of the same items).

Claims

1. A computerized method for matching item representations within a collection of item representations, the method comprising:

determining candidate pairs of item representations based on frequency information indicative of the frequency at which terms appear in the collection of item representations, wherein the frequency information comprises an IDF score determined for each term based on the respective term'"'"'s frequency of use within the collection of item representations, and wherein determining candidate pairs comprises determining an aggregate IDF score for pairs of item representations by adding the IDF scores for terms shared by each pair of item representations and comparing the aggregate IDF score for each pair of item representations against a threshold to determine if each pair of item representations qualifies as a candidate pair; and

matching item representations by analyzing the candidate pairs using one or more fuzzy matching functions.

2. The computerized method of claim 1, wherein the item representations comprise citations of publications.

3. The computerized method of claim 1, wherein the terms appearing in the collection of item representations comprises at least one of individual words and phrases.

4. The computerized method of claim 1, wherein determining candidate pairs comprises sorting terms from a target item representation based on IDF score;

and iterating through the sorted terms in a manner such that at each iteration;

(1) an aggregate IDF score is determined based on whether a current term and previously iterated terms are shared between the target item representation and a second item representation and (2) the aggregate IDF score is compared against a threshold to determine if the target item representation and second item representation comprise a candidate pair.

5. The computerized method of claim 4, wherein determining candidate pairs further comprises, at each iteration, predicting whether it is possible for the target item representation and second item representation to be identified as a candidate pair by assuming remaining terms from the target item representation are shared by the second item representation.

6. The computerized method of claim 1, wherein matching item representations comprises identifying different segments within the item representations and applying fuzzy matching functions suitable for each of the different segments.

7. The computerized method of claim 6, wherein matching item representations further comprises employing a decision tree classifier to combine results from the fuzzy matching algorithms.

8. One or more computer-readable storage media embodying computer-useable instructions for performing a method of matching item representations from a collection of item representations, the method comprising:

extracting terms from the collection of item representation;

determining frequency information indicative of the frequency with which the terms appear within the collection of item representations, wherein the frequency information comprises an IDF score calculated for each term;

generating an inverted index mapping the terms to the item representations in which the terms appear, wherein the inverted index further includes the frequency information for the terms;

determining one or more candidate pairs of item representations using the inverted index based on terms shared between item representations and frequency information associated with the terms by determining aggregate IDF scores for pairs of item representations based on terms shared between each pair of item representations and comparing the aggregate IDF scores against a threshold; and

identifying one or more matching pairs of item representations by analyzing the candidate pairs using one or more fuzzy matching algorithms.

9. The one or more computer-readable storage media of claim 8, wherein the item representations comprise citations of publications.

10. The one or more computer-readable storage media of claim 8, wherein the terms comprises at least one of individual words and phrases.

11. The one or more computer-readable storage media of claim 8, wherein determining one or more candidate pairs comprises:

sorting terms from a target item representation based on the IDF score for each term; and

analyzing whether a second item representation and the target item representation comprise a candidate pair by iterating through the sorted terms and determining at each iteration whether the target item representation and second item representation are a candidate pair and whether further iterations are necessary.

12. The one or more computer-readable storage media of claim 8, wherein identifying one or more matching pairs comprises:

identifying different segments within the item representations;

determining a suitable fuzzy matching function for each of the different segments;

applying the fuzzy matching functions; and

employing a decision tree classifier to combine the results of the fuzzy matching functions to identify the one or more matching pairs.

13. A computerized system including one or more computer-readable media embodying software components for matching item representations from a collection of item representations, the software components comprising:

a blocking component that identifies candidate pairs of item representations based on frequency information associated with terms shared between the candidate pairs, wherein the blocking component identifies candidate pairs of item representations by determining aggregate IDF scores based on the frequency information associated with terms shared between pairs of item representations and comparing the aggregated IDF scores against a threshold; and

a matching component that identifies matching pairs of item representations by analyzing the candidate pairs using one or more fuzzy matching algorithms.

14. The computerized system of claim 13, wherein the matching component identifies matching pairs by identifying different segments within the item representations and applying fuzzy matching functions suitable to the different segments and employing a decision tree classifier to combine the results of the fuzzy matching functions to identify matching pairs.