Computer-based method for finding similar objects using a taxonomy

• US 7,533,096 B2
• Filed: 07/12/2006
• Issued: 05/12/2009
• Est. Priority Date: 07/12/2006
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Deng, Yu, Schwarz, Peter, Rice, Julia Elizabeth
• Primary Examiner(s): Vital; Pierre M
• Assistant Examiner(s): Rahman; Sabana
• Application Number:
  US11/457,069
• Publication Number:
  US 20080027929A1
• Time in Patent Office: 1,035 Days
• Field of Search: 707/6
• US Class Current: 1/1
• 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,

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), and

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 a corpus  

contains L, and 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)},$

and said inclusion probability is given by;

p_i(L)=p(L  

Terms(Anc(o))).

2. 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.

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

4. 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 objects, with said more than one candidate objects being ranked in order of similarity.

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

6. An article of manufacture comprising a computer storage medium storing computer executable instructions for 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),

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 a corpus  

contains L, and 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)},$

and said inclusion probability is given by;

p_i(L)=p(L  

Terms(Anc(o))).

7. 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, and 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 a corpus  

contains L, and 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)},$

and said inclusion probability is given by;

p_i(L)=p(L  

Terms(Anc(o))).

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

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

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

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

12. An article of manufacture comprising a computer storage medium storing computer executable instructions for 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 and 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 a corpus  

contains L, and 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)},$

and said inclusion probability is given by;

p_i(L)=p(L  

Terms(Anc(o))).