COMPUTER-BASED METHOD FOR FINDING SIMILAR OBJECTS USING A TAXONOMY

• US 20080027929A1
• Filed: 07/12/2006
• Published: 01/31/2008
• Est. Priority Date: 07/12/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: SCHWARZ, PETER, DENG, YU, RICE, JULIA ELIZABETH
• Granted Patent: US 7,533,096 B2
• Time in Patent Office: Days
• US Class Current: 707/6
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A generalized axiomatic definition of information-theoretic similarity is provided for taxonomies that are structured as directed acyclic graph form which multiple terns may be used to describe an object. The definition is adaptable in the presence of ambiguity, as introduced by an evolving taxonomy or classifiers with imperfect knowledge, and two new similarity measures are introduced based on the definitions. A pragmatic implementation is also provided for similarity measures that arc tightly integrated with an object-relational database and scales to large taxonomies and large datasets.

Claims

1. A computer-based method of finding similar items labeled in a taxonomy comprising the steps of:

determining a label L_A representing a set of concepts that a target object T and a candidate object C have in common, said target object T and candidate object C part of a taxonomy structure as acyclic graphs wherein at least one child class has multiple parents;

determining information content I(L_A) of label L_A representing said set of common concepts;

combining individual information content I(L_T) and I(L_C), where I(L_T) and I(L_C) represent individual information content of labels of target object and candidate object, respectively, and

finding similarity between said target object and said candidate object in said taxonomy as a function of I(L_A) and I(L_T)+I(L_C).

2. A computer-based method of finding similar items labeled in a taxonomy, as per claim 1, wherein said similarity between said target object T and said candidate object C is found based on the following mathematical function:

$\mathrm{sim}<br><br>\left(T,C\right)=\frac{2<br><br>I<br><br>\left(L_A\right)}{I<br><br>\left(L_T\right)+I<br><br>\left(L_C\right)}.$

3. A computer-based method of finding similar items labeled in taxonomy, as per claim 1, wherein said information content I(L_A), I(L_T), and I(L_C) are functions of inclusion probabilities p(L_A), p(L_T), and p(L_C), respectively, said inclusion probability of label L defined as the probability that an ancestor graph of label L of an object o chosen at random from contains L, said inclusion probability given by:

p_i(L)=p(L⊂

Terms(Anc(o))).

4. A computer-based method of finding similar items labeled in a taxonomy, as per claim 1, wherein said method is implemented in conjunction with a object relational-database.

5. A computer-based method of finding similar items labeled in a taxonomy, as per claim 1, wherein said database additionally has user-defined types and functions allowing efficient implementation of said computer-based method.

6. A computer-based method of finding similar items labeled in a taxonomy, as per claim 1, wherein said method is iteratively performed for more than one candidate object, with said more than candidate objects being ranked in order of similarity.

7. A computer-based method of finding similar items labeled in a taxonomy, as per claim 6, wherein said method further utilizes pre-computed ancestor graphs for candidate objects labels and each individual term in a taxonomy.

8. An article of manufacture comprising a computer user medium having computer readable program code embodied therein which implement a computer-based method of finding similar items labeled in a taxonomy, said medium comprising:

computer readable program code determining a label L_A representing a set of concepts that a target object T and a candidate object C have in common, said target object T and candidate object C part of a taxonomy structure as acyclic graphs wherein at least one child class has multiple parents;

computer readable program code determining information content I(L_A) of label L_A representing said set of common concepts;

computer readable program code combining individual information content I(L_T) and I(L_C), where I(L_T) and I(L_C) represent individual information content of labels of target object and candidate object, respectively, and

computer readable program code finding similarity between said target object and said candidate object in said taxonomy as a function of I(L_A) and I(L_T)+I(L_C).

9. An article of manufacture comprising a computer user medium having computer readable program code embodied therein which implement a computer-based method of finding similar items labeled in a taxonomy, as per claim 8, wherein said similarity between said target object T and said candidate object C is found based on the following mathematical function:

$\mathrm{sim}<br><br>\left(T,C\right)=\frac{2<br><br>I<br><br>\left(L_A\right)}{I<br><br>\left(L_T\right)+I<br><br>\left(L_C\right)}.$

10. A computer-based method of finding similar items labeled in a taxonomy comprising the steps of:

determining a label L_A representing a set of concepts that a target object T and a candidate object C have in common, said target object T and candidate object C part of a taxonomy structure as acyclic graphs wherein at least one child class has multiple parents;

determining information content I(L_A) of label L_A representing said set of common concepts;

combining individual information content I(L_T) and I(L_A), where I(L_T) represent information content of label of target object;

finding similarity between said target object and said candidate object in said taxonomy as a function of I(L_A) and I(L_T)+I(L_A), and

wherein said similarity is equal to 1 if and only if object C is substitutable for object T.

11. A computer-based method of finding similar items labeled in a taxonomy, as per claim 10, wherein said similarity between said target object T and said candidate object C is found based on the following mathematical function:

${\mathrm{sim}}_G<br><br>\left(T,C\right)=\frac{2<br><br>I<br><br>\left(L_A\right)}{I<br><br>\left(L_T\right)+I<br><br>\left(L_A\right)}.$

12. A computer-based method of finding similar items labeled in taxonomy, as per claim 10, wherein said information content I(L_A) and I(L_T) are functions of inclusion probabilities p(L_A) and p(L_T), respectively, said inclusion probability of label L defined as the probability that an ancestor graph of label L of an object o chosen at random from contains L, said inclusion probability given by:

p_i(L)=p(L⊂

Terms(Anc(o)))

13. A computer-based method of finding similar items labeled in a taxonomy, as per claim 10, wherein said method is implemented in conjunction with a object relational-database.

14. A computer-based method of finding similar items labeled in a taxonomy, as per claim 13, wherein said database additionally has user-defined types and functions allowing efficient implementation of said computer-based method.

15. A computer-based method of finding similar items labeled in a taxonomy, as per claim 10, wherein said method is iteratively performed for more than one candidate object, with said more than candidate objects being ranked in order of similarity.

16. A computer-based method of finding similar items labeled in a taxonomy, as per claim 15, wherein said method further utilizes pre-computed ancestor graphs for candidate objects labels and each individual term in a taxonomy.

18. An article of manufacture comprising a computer user medium having computer readable program code embodied therein which implement a computer-based method of finding similar items labeled in a taxonomy, as per claim 15, wherein said similarity between said target object T and said candidate object C is found based on the following mathematical function:

${\mathrm{sim}}_G<br><br>\left(T,C\right)=\frac{2<br><br>I<br><br>\left(L_A\right)}{I<br><br>\left(L_T\right)+I<br><br>\left(L_A\right)}.$

17. An article of manufacture comprising a computer user medium having computer readable program code embodied therein which implement a computer-based method of finding similar items labeled in a taxonomy, said medium comprising:

computer readable program code determining a label L_A representing a set of concepts that a target object T and a candidate object C have in common, said target object T and candidate object C part of a taxonomy structure as acyclic graphs wherein at least one child class has multiple parents;

computer readable program code determining information content I(L_A) of label L_A representing said set of common concepts;

computer readable program code combining individual information content I(L_T) and I(L_A), where I(L_T) represent information content of label of target object;

computer readable program code finding similarity between said target object and said candidate object in said taxonomy as a function of I(L_A) and I(L_T)+I(L_A), and

wherein said similarity is equal to 1 if and only if object C is substitutable for object T.