Method and system for analyzing similarity of concept sets

• US 20080195587A1
• Filed: 02/13/2007
• Published: 08/14/2008
• Est. Priority Date: 02/13/2007
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Hussami, Peter
• Granted Patent: US 7,860,855 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/367 Ontology

Abstract

A method and system are described for determining similar concept sets. An example method includes obtaining taxonomies, each including one root node and hierarchically ordered paths; receiving first and second sets each including set concepts; determining concept pairs, each including a first and second set concept; determining lengths of nondiverging intersections of first and second subpaths from the root node to first and second concept nodes, and associated lengths of first and second portions of the subpaths from a last concept node included in the nondiverging intersection to the first and second concept nodes; determining pairwise similarity values based on ratios based on associated lengths of nondiverging intersections and the associated lengths of the first and second portions; and determining a concept set similarity value based on a weighted sum of the pairwise similarity values associated with optimal selected ones of the concept pairs.

Claims

1. A system comprising:

a concept analysis engine including;

a taxonomy manager configured to obtain a set of one or more taxonomies wherein each of the taxonomies includes one root node and one or more hierarchically ordered paths, wherein each hierarchically ordered path includes the root node and a hierarchically ordered sequence of concept nodes;

a concept set engine configured to receive a first set of first set concepts and a second set of second set concepts;

a concept pair engine configured to determine a plurality of concept pairs, wherein each concept pair includes one of the first set concepts and one of the second set concepts;

a hierarchical path engine configured to determine, for each one of the concept pairs, an associated length of a nondiverging intersection of a first subpath of one of the hierarchically ordered paths from the root node of one of the taxonomies to a first concept node representing the first set concept and a second subpath of one of the hierarchically ordered paths from the root node of the one of the taxonomies to a second concept node representing the second set concept, and an associated length of a first portion of the first subpath from a last concept node included in the nondiverging intersection to the first concept node, and an associated length of a second portion of the second subpath from the last concept node included in the nondiverging intersection to the second concept node;

a concept similarity engine configured to determine pairwise similarity values associated with each of the concept pairs based on ratios based on associated lengths of nondiverging intersections determined by the hierarchical path engine and the associated lengths of the first and second portions, wherein a pairwise similarity value indicating a high similarity is determined for association with concept pairs associated with nonempty nondiverging intersections including the root node and hierarchically immediate successor nodes of the root node that are included in the first subpath and the second subpath; and

a concept set similarity engine configured to determine a concept set similarity value based on a weighted sum of the pairwise similarity values associated with optimal selected ones of the concept pairs.

2. The system of claim 1 wherein each one of the taxonomies includes one root node and one or more hierarchically ordered paths, wherein each hierarchically ordered path includes the root node and a hierarchically ordered sequence of concept nodes, wherein each of the concept nodes represents a concept, wherein the hierarchically ordered sequence includes an ordering based on a hierarchically ordered path positioning of concept nodes representing superconcepts before concept nodes representing subconcepts of associated superconcepts based on a concept hierarchy.

3. The system of claim 1 wherein each one of the taxonomies includes one root node and one or more hierarchically ordered paths, wherein each hierarchically ordered path includes the root node and a hierarchically ordered sequence of concept nodes, wherein each of the concept nodes represents a concept, wherein the hierarchically ordered sequence includes an ordering based on a hierarchically ordered path positioning of concept nodes, wherein concept nodes representing parent superconcepts immediately precede concept nodes representing child subconcepts of associated parent superconcepts representing superconcepts in the hierarchically ordered path, based on a concept hierarchy.

4. The system of claim 1 wherein each one of the taxonomies is acyclic.

5. The system of claim 1 wherein each of the concept nodes represents a semantic concept, each of the first set concepts represents a semantic concept, and each of the second set concepts represents a semantic concept.

6. The system of claim 1 wherein the concept analysis engine further comprises:

a web page engine configured to obtain web pages, wherein each web page includes a set of one or more semantic concepts.

7. The system of claim 1 wherein each of the taxonomies includes one root node and one or more hierarchically ordered paths, wherein each hierarchically ordered path is associated with an enumerated path representation including an ordered sequence of identifiers of branches from hierarchical predecessor nodes to each immediate hierarchical successor node in the each hierarchically ordered path, based on a concept hierarchy, and

wherein the hierarchical path engine is configured to determine, for each one of the concept pairs, the associated length of the nondiverging intersection based on a comparison of enumerated path representations associated with each of the first concept node representing the first set concept included in the each one of the concept pairs, and the second concept node representing the second set concept included in the each one of the concept pairs.

8. The system of claim 7 wherein each enumerated path representation includes an ordered sequence of numeric identifiers of branches from hierarchical predecessor nodes to each immediate hierarchical successor node in the each hierarchically ordered path, based on a concept hierarchy.

9. The system of claim 1 wherein the concept similarity engine is configured to determine pairwise similarity values associated with each of the concept pairs based on ratios based on first functions of associated lengths of nondiverging intersections determined by the hierarchical path engine and second functions of the associated lengths of the first and second portions, wherein a pairwise similarity value indicating a high similarity is determined for association with concepts pairs associated with nonempty nondiverging intersections including the root node and hierarchically immediate successor nodes of the root node that are included in the first subpath and the second subpath.

10. The system of claim 1 wherein the concept similarity engine is configured to determine pairwise similarity values associated with each of the concept pairs based on ratios based on first functions of associated lengths of nondiverging intersections determined by the hierarchical path engine and second functions of the associated lengths of the first and second portions, wherein a pairwise similarity value indicating a high similarity is determined for association with concepts pairs associated with nonempty nondiverging intersections including the root node and hierarchically immediate successor nodes of the root node that are included in the first subpath and the second subpath, wherein the ratios include weighted sums of values of the first and second functions divided by total sums of the values of the first and second functions.

11. The system of claim 1 wherein the concept similarity engine is configured to determine pairwise similarity values associated with each of the concept pairs based on ratios based on first functions of associated lengths of nondiverging intersections determined by the hierarchical path engine and second functions of the associated lengths of the first and second portions, wherein a pairwise similarity value indicating a high similarity is determined for association with concepts pairs associated with nonempty nondiverging intersections including the root node and hierarchically immediate successor nodes of the root node that are included in the first subpath and the second subpath, wherein a value of the second function indicates a high concept similarity if the first concept includes a subconcept of the second concept, and otherwise indicates a low concept similarity.

12. The system of claim 1 wherein the concept similarity engine is configured to determine pairwise similarity values associated with each of the concept pairs based on ratios based on first functions of associated lengths of nondiverging intersections determined by the hierarchical path engine and second functions of the associated lengths of the first and second portions, wherein a pairwise similarity value indicating a high similarity is determined for association with concepts pairs associated with nonempty nondiverging intersections including the root node and hierarchically immediate successor nodes of the root node that are included in the first subpath and the second subpath, wherein a value of the first function associated with the first subpath is greater than a value of the first function associated with the second subpath when the second subpath includes a shorter path length than the first subpath.

13. The system of claim 1 wherein the concept similarity engine is configured to determine pairwise similarity values associated with each of the concept pairs based on ratios based on first functions of associated lengths of nondiverging intersections determined by the hierarchical path engine and second functions of the associated lengths of the first and second portions, wherein a pairwise similarity value indicating a high similarity is determined for association with concepts pairs associated with nonempty nondiverging intersections including the root node and hierarchically immediate successor nodes of the root node that are included in the first subpath and the second subpath, wherein a value of the second function associated with the first subpath is greater than a value of the second function associated with the second subpath when the second subpath includes a shorter path length than the first subpath.

14. The system of claim 1 wherein the concept similarity engine is configured to determine pairwise similarity values associated with each of the concept pairs based on ratios based on first functions of associated lengths of nondiverging intersections determined by the hierarchical path engine and second functions of the associated lengths of the first and second portions, wherein a pairwise similarity value indicating a high similarity is determined for association with concepts pairs associated with nonempty nondiverging intersections including the root node and hierarchically immediate successor nodes of the root node that are included in the first subpath and the second subpath, wherein values of the first and second functions that are associated with empty subpaths indicate substantially no weight.

15. The system of claim 1 wherein the concept set similarity engine is configured to determine the concept set similarity value based on determining a weighted sum of the pairwise similarity values associated with optimal selected ones of the concept pairs, wherein the optimal selected ones are determined based on determining maximal similarity values associated with each one of the concept pairs, wherein the weighted sum is based on a weighted sum of the maximal similarity values determined for each concept pair.

16. The system of claim 1 further comprising:

a concept repository including;

a taxonomy storage area configured to taxonomy information associated with the one or more taxonomies;

a concept set storage area configured to store concept set information associated with the first set and the second set; and

a similarity storage area configured to store the concept set similarity value and similarity information associated with the pairwise similarity values and the associated concept pairs,

wherein;

the taxonomy manager is configured to obtain the set of one or more taxonomies from the taxonomy storage area,

the concept set engine is configured to store the first set and the second set in the concept set storage area,

the concept similarity engine is configured to store the similarity information associated with the pairwise similarity values and the associated concept pairs in the similarity storage area, and

the concept set similarity engine is configured to store the concept set similarity value in the similarity storage area.

17. The system of claim 1 further comprising:

a user interface configured to receive requests for similar concept sets from a user; and

a request manager configured to determine the similar concept sets based on one or more concept set similarity values.

18. The system of claim 17 wherein:

the user interface is configured to receive requests for similar web pages associated with concept sets from a user, and

the request manager is configured to determine the similar web pages based on the concept sets associated with the similar web pages based on the one or more concept set similarity values.

19. A method comprising:

obtaining a set of one or more taxonomies wherein each of the taxonomies includes one root node and one or more hierarchically ordered paths, wherein each hierarchically ordered path includes the root node and a hierarchically ordered sequence of concept nodes;

receiving a first set of first set concepts and a second set of second set concepts;

determining a plurality of concept pairs, wherein each concept pair includes one of the first set concepts and one of the second set concepts;

determining, for each one of the concept pairs, an associated length of a nondiverging intersection of a first subpath of one of the hierarchically ordered paths from the root node of one of the taxonomies to a first concept node representing the first set concept and a second subpath of one of the hierarchically ordered paths from the root node of the one of the taxonomies to a second concept node representing the second set concept, and an associated length of a first portion of the first subpath from a last concept node included in the nondiverging intersection to the first concept node, and an associated length of a second portion of the second subpath from the last concept node included in the nondiverging intersection to the second concept node;

determining pairwise similarity values associated with each of the concept pairs based on ratios based on associated lengths of nondiverging intersections determined by the determining the associated length of the nondiverging intersection and the associated lengths of the first and second portions, wherein a pairwise similarity value indicating a high similarity is determined for association with concept pairs associated with nonempty nondiverging intersections including the root node and hierarchically immediate successor nodes of the root node that are included in the first subpath and the second subpath; and

determining a concept set similarity value based on a weighted sum of the pairwise similarity values associated with optimal selected ones of the concept pairs.

20. The method of claim 19 wherein:

obtaining the set of one or more taxonomies comprises obtaining the set of one or more taxonomies wherein each of the taxonomies includes one root node and one or more hierarchically ordered paths, wherein each hierarchically ordered path includes the root node and a hierarchically ordered sequence of concept nodes, wherein each of the concept nodes represents a concept, wherein each hierarchically ordered path is indicated by an associated ordered vector of branch indicators, wherein each branch indicator indicates an edge between an immediate predecessor concept node and an immediate successor node based on the hierarchically ordered sequence, and

determining, for each one of the concept pairs, an associated length of a nondiverging intersection of a first subpath comprises determining, for each one of the concept pairs, a nondiverging intersection of one of the vectors associated with the first subpath of the one of the hierarchically ordered paths from the root node to the first concept node and one of the vectors associated with the second subpath of the one of the hierarchically ordered paths from the root node to the second concept node.

21. The method of claim 19 wherein:

receiving the first set comprises receiving a first web page associated with the first set including a plurality of first set concepts, wherein each first set concept represents a semantic concept,

receiving the second set comprises receiving a second web page associated with the second set including a plurality of second set concepts, wherein each second set concept represents a semantic concept, and

determining the concept set similarity value comprises determining the concept set similarity value between the first web page and the second web page based on determining a weighted sum of the pairwise similarity values associated with optimal selected ones of the concept pairs.

22. The method of claim 19 wherein determining the pairwise similarity values comprises:

determining pairwise similarity values associated with each of the concept pairs based on ratios based on first functions of associated lengths of nondiverging intersections determined by the determining the associated length of the nondiverging intersection and second functions of the associated lengths of the first and second portions, wherein a pairwise similarity value indicating a high similarity is determined for association with concepts pairs associated with nonempty nondiverging intersections including the root node and hierarchically immediate successor nodes of the root node that are included in the first subpath and the second subpath, wherein values of the first and second functions that are associated with empty subpaths indicate substantially no weight.

23. The method of claim 19 wherein determining the concept set similarity value comprises:

determining the concept set similarity value based on determining a weighted sum of the pairwise similarity values associated with optimal selected ones of the concept pairs, wherein the optimal selected ones are determined based on determining maximal similarity values associated with each one of the concept pairs, wherein the weighted sum is based on a weighted sum of the maximal similarity values determined for each concept pair.

24. A computer program product being tangibly embodied on a computer-readable medium and being configured to cause a data processing apparatus to:

obtain a set of one or more taxonomies wherein each of the taxonomies includes one root node and one or more hierarchically ordered paths, wherein each hierarchically ordered path includes the root node and a hierarchically ordered sequence of concept nodes;

receive a first set of first set concepts and a second set of second set concepts;

determine a plurality of concept pairs, wherein each concept pair includes one of the first set concepts and one of the second set concepts;

determine, for each one of the concept pairs, an associated length of a nondiverging intersection of a first subpath of one of the hierarchically ordered paths from the root node of one of the taxonomies to a first concept node representing the first set concept and a second subpath of one of the hierarchically ordered paths from the root node of the one of the taxonomies to a second concept node representing the second set concept, and an associated length of a first portion of the first subpath from a last concept node included in the nondiverging intersection to the first concept node, and an associated length of a second portion of the second subpath from the last concept node included in the nondiverging intersection to the second concept node;

determine pairwise similarity values associated with each of the concept pairs based on ratios based on associated lengths of nondiverging intersections determined by the determining the associated length of the nondiverging intersection and the associated lengths of the first and second portions, wherein a pairwise similarity value indicating a high similarity is determined for association with concept pairs associated with nonempty nondiverging intersections including the root node and hierarchically immediate successor nodes of the root node that are included in the first subpath and the second subpath; and

determine a concept set similarity value based on a weighted sum of the pairwise similarity values associated with optimal selected ones of the concept pairs.

25. The computer program product of claim 24 wherein the computer program is configured to cause the data processing apparatus to determine the pairwise similarity values based on determining pairwise similarity values associated with each of the concept pairs based on ratios based on first functions of associated lengths of nondiverging intersections determined by the determining the associated length of the nondiverging intersection and second functions of the associated lengths of the first and second portions, wherein a pairwise similarity value indicating a high similarity is determined for association with concepts pairs associated with nonempty nondiverging intersections including the root node and hierarchically immediate successor nodes of the root node that are included in the first subpath and the second subpath, wherein the ratios include weighted sums of values of the first and second functions divided by total sums of the values of the first and second functions.

26. The computer program product of claim 24 wherein the computer program is configured to cause the data processing apparatus to determine the concept set similarity value based on determining the concept set similarity value based on determining a weighted sum of the pairwise similarity values associated with optimal selected ones of the concept pairs, wherein the optimal selected ones are determined based on determining maximal similarity values associated with each one of the concept pairs, wherein the weighted sum is based on a weighted sum of the maximal similarity values determined for each concept pair.