Conceptual factoring and unification of graphs representing semantic models

• US 6,847,979 B2
• Filed: 02/23/2001
• Issued: 01/25/2005
• Est. Priority Date: 02/25/2000
• Status: Expired due to Fees

• Current Assignee: Poppet International Pty Limited
• Original Assignee: Synquiry Technologies Ltd.
• Inventors: Allemang, Dean T., Simos, Mark A.
• Primary Examiner(s): LE, UYEN T
• Application Number:
  US10/204,792
• Publication Number:
  US 20030050915A1
• Time in Patent Office: 1,432 Days
• Field of Search: 707/102, 707/100, 707/101, 707/104.1, 345/440
• US Class Current: 707/797
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri
• CPC Class Codes: G06F 16/367 Ontology
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Techniques for factoring one or more source graphs into a composite graph containing nodes representing analogous elements of the source graphs and a variability graph containing nodes representing differences in the source graphs. The composite graph is made by taking analogous input trees from the source graphs and traversing the trees from top to bottom looking for nodes in each tree at each level that are analogous to the nodes at that level in the other input trees. The sets of analogous nodes are found by first automatically correlating the nodes in the level currently being examined. Correlation may, for example, be based on similar values of a property of the nodes being correlated. Representations of the sets of correlated nodes are then displayed to a user, who indicates which sets of correlated nodes are in fact analogous. The user may also indicate that the nodes in a set of correlated nodes are not analogous or that nodes that were found by the automatic correlation not to be autonomous are in fact. The analogous nodes are allocated to a corresponding node at a corresponding level in the composite graph; the other nodes are allocated to a set of anomalous nodes. One application for the techniques is managing graphs which are models of catalogs of items.

Claims

1. A method performed in a system having a processor, a memory accessible thereto, and a user interface of unifying child nodes of a plurality of parent nodes from one or more other graphs into composite graph child nodes of a composite graph parent node in a composite graph, the graphs being stored in the memory and

the method comprising the steps performed by the processor of:

correlating the child nodes, including any of the composite graph child nodes, to produce one or more sets of possibly analogous nodes;

displaying a representation of the set of possibly analogous nodes in the user interface and receiving an indication via the user interface whether nodes in the represented set are taken to be analogous; and

making siblings of the composite graph child nodes of the composite graph parent node as required to provide a composite graph child node corresponding to each of the indicated sets of analogous nodes.

2. A method performed in a system having a processor and a memory accessible thereto of correlating a node in a first graph with a possibly analogous node in a second graph, both graphs being stored in the memory and

the method comprising the steps performed by the processor of:

analyzing the first node'"'"'s relationship to another node in the first graph to obtain a first result;

analyzing the second node'"'"'s relationship to another node in the second graph to obtain a second result; and

using the results to determine at least in part whether the first node is correlated with the second node.

3. A system for unifying similar structures from one or more source graphs into a composite graph,

the system comprising:

a correlator that correlates nodes from similar portions of the similar structures to find one or more sets of possibly analogous nodes;

a user interface that displays a representation of the set of possibly analogous nodes and receives an indication whether the represented nodes are taken to be analogous; and

an allocator that allocates the indicated set of analogous nodes to a corresponding node in the composite graph.

4. The system set forth in claim 3 wherein:

when there is no corresponding node in the composite graph, the allocator adds a corresponding node thereto.

5. The system set forth in claim 3 wherein:

the correlator correlates nodes from similar portions of pairs of similar structures; and

the representation of the set of possibly analogous nodes represents a pair of possibly analogous nodes.

6. The system set forth in claim 3 further comprising:

a variability graph containing nodes corresponding to nodes in the similar structures that differentiate the similar structures one from another.

7. The system set forth in claim 6 wherein:

the user interface further displays the similar structures and receives indications of the differentiating nodes therein; and

the system further responds to the indications of the differentiating nodes by allocating nodes in the variability graph corresponding to the indicated differentiating nodes.

8. The system set forth in claim 6 wherein:

the system further comprises a remainder graph corresponding to each of the source graphs, each remainder graph containing those nodes of the source graph that do not have corresponding nodes in either the composite graph or the variability graph, whereby no information contained in the source graphs is lost.

9. The system set forth in claim 3 wherein:

the nodes in the source graphs and the composite graph represent concepts;

the concept nodes in the source graphs are associated with item instance nodes; and

when a concept in a given one of the similar structures has a corresponding concept in the composite graph, the allocator associates each item instance node associated with the concept with the corresponding concept in the composite graph.

10. The system set forth in claim 6 wherein:

the nodes in the source graphs, the composite graph, and the variability graph represent concepts;

the concept nodes in the source graphs are associated with item instance nodes; and

the allocator associates each item instance node associated with a concept in a given one of the similar structures that has a corresponding concept in the composite graph with the corresponding concept in the composite graph and with a node in the variability graph that corresponds to a node in the given similar structure.

11. The system set forth in claim 6 wherein:

the nodes in the composite graph and the variability graph represent concepts;

the composite graph is a concept graph and the variability graph is a feature graph; and

the allocator connects each node allocated to the composite graph to the nodes in the feature graph that are features of the nodes in the set of nodes corresponding to the allocated node.

12. The system set forth in claim 3 wherein:

the source graphs are not permanently altered by operation of the system thereon.

13. The system set forth in claim 3 wherein:

one or more of the source graphs is a pre-existing composite graph.

14. The system set forth in claim 12 wherein:

the pre-existing composite graph was produced by the system.

15. The system set forth in claim 3 wherein:

the similar structures are parent nodes with child nodes, the parent nodes corresponding to a node in the composite graph;

the correlator correlates the child nodes; and

the allocator allocates a correlated child node to a corresponding node in the composite graph that is a child of the node in the composite graph that corresponds to the parent nodes in the similar structures.

16. The system set forth in claim 15 wherein:

having correlated and allocated the child nodes in the similar structures, the system correlates and allocates the nodes in any further similar structures, each further similar structure having one of the correlated and allocated child nodes as a parent node.

17. The system set forth in claim 16 wherein:

the parent nodes of the further similar structures correspond to the same node in the composite graph.

18. The system set forth in claim 3 wherein:

the correlator correlates the nodes at least in part on the basis of a value of a property in the nodes being correlated.

19. The system set forth in claim 18 wherein:

the correlation is on the basis of a best match between the values of the properties.

20. The system set forth in claim 18 wherein:

the correlator correlates the nodes additionally on the basis of similar locations in the similar structures.

21. The system set forth in claim 20 wherein:

the similar structures are trees; and

the correlator correlates nodes belonging to corresponding levels in the trees.

22. The system set forth in claim 3 wherein:

the correlator correlates the nodes at least in part on the basis of similarity of relationships between nodes and the structures to which the nodes belong.

23. The system set forth in claim 22 wherein:

the similar structures are trees; and

the correlator correlates nodes belonging to corresponding levels in the trees.

24. The system set forth in claim 22 wherein:

the nodes in the source graphs are connected by typed facets; and

the correlator correlates the nodes at least in part on the basis of similarity of facets.

25. The system set forth in claim 22 wherein:

the nodes in the source graphs and the composite graph represent concepts;

the concept nodes in the source graphs are associated with item instance nodes; and

the correlator correlates the nodes in the source graphs at least in part on the basis of similarity of item instance nodes.

26. The system set forth in claim 3 wherein:

the user interface further receives editing inputs for editing the set of possibly analogous nodes; and

the indication whether the represented nodes are to be taken as analogous is an accept input for accepting the set of possibly analogous nodes as edited.

27. The system set forth in claim 26 wherein:

the user interface further includes a representation of nodes that do not belong to the set of possibly analogous nodes and

the editing inputs include a first editing input that indicates that the set of possibly analogous nodes is not taken to be analogous and a second editing input that indicates that nodes in the representation of nodes that do not belong to the set of possibly analogous nodes are to be taken as analogous.

28. The system set forth in claim 27 wherein:

the user interface responds to the first editing input by adding any node that is not taken to be analogous to the representation of nodes that do not belong to the set of possibly analogous nodes and responds to the second editing input by adding the nodes that do not belong to the set of possibly analogous nodes but are to be taken as analogous to the representation of possibly analogous nodes.

29. The system set forth in claim 26 wherein:

the user interface further includes representations of contexts of the nodes in the set of possibly analogous nodes.

30. The system set forth in claim 26 wherein:

the user interface further includes a representation of a method used to correlate the nodes in the set of possibly analogous nodes.