Methods and apparatus for identifying related nodes in a directed graph having named arcs
3 Assignments
0 Petitions
Accused Products
Abstract
The invention provides methods for identifying related data in a directed graph (e.g., an RDF data set). A “first” in step—though the steps are not necessarily executed in sequential order—includes identifying (or marking) as related data expressly satisfying the criteria. A “second” step includes identifying as related ancestors of any data identified as related, e.g., in the first step, unless that ancestor conflicts with the criteria. A “third” step of the method is identifying descendents of any data identified, e.g., in the prior steps, unless that descendent conflicts with the criteria or has a certain relationship with the ancestor from which it descends. The methods generates, e.g., as output, an indication of each of the nodes identified as related in the three steps.
-
Citations
42 Claims
-
1-10. -10. (canceled)
-
11. A method for identifying related data in a directed graph, comprising:
-
A. executing the sub-steps of (i) identifying as related data substantially matching a criteria;
(ii) identifying as related data that is a direct ancestor of data identified as related in any of sub-steps (i) and (ii), and that is not in substantial conflict with the criteria;
B. generating an indication of data identified as related in step (A). - View Dependent Claims (12, 13, 14)
-
-
15. A method for identifying related data in a directed graph, comprising:
A. executing the sub-steps of (i) identifying as related data substantially matching a criteria;
(ii) identifying as related data (hereinafter “
identified descendent”
) that is a direct descendent of data (hereinafter “
identified ancestor”
) identified in any of substeps (i) and (ii), and which identified descendent(a) does not have a named relationship with the identified ancestor substantially matching a relationship named in the criteria, if any, and (b) is not in substantial conflict with the criteria;
(c) does not have a named relationship with the identified ancestor matching a relationship the identified ancestor has with a data, if any, as a result of which the identified ancestor was identified as related. - View Dependent Claims (16, 17, 18, 19, 20)
-
21. A method for identifying related triples in a resource description framework (RDF) data set, comprising
A. executing with respect to the data set the sub-steps of (i) identifying as related a triple substantially matching a criteria; -
(ii) identifying as related a triple that is a direct ancestor of a triple identified as related in any of sub-steps (i), (ii) and (iii), and that is not in substantial conflict with the criteria, where, for purposes hereof, a triple whose object is the subject of another triple is deemed a direct ancestor of that other triple, and, conversely, where a triple whose subject is the object of another triples is deemed a direct descendent of that other triple;
;
(iii) identifying as related a triple (hereinafter “
identified descendent”
) that is a direct descendent of triple (hereinafter “
identified ancestor”
) identified as related in any of sub-steps (i), (ii) and (iii), and which identified descendent(a) is not associated with the identified ancestor via a predicate substantially matching a predicate named in the criteria, if any, and (b) is not in substantial conflict with the criteria;
(c) is not associated with the identified ancestor via a predicate matching a predicate by which the identified ancestor is associated with a triple, if any, as a result of which the identified ancestor was identified during execution of sub-step (ii), B. generating an indication of triples identified as related in step (A). - View Dependent Claims (22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 40, 41)
-
-
32. A method for identifying related triples in a resource description framework (RDF) data set, comprising
A. executing with respect to the data set the sub-steps of (i) identifying as related data substantially matching a criteria; -
(ii) identifying as related a triple that is a direct ancestor of a triple identified in any of sub-steps (i) and (ii), and that is not in substantial conflict with the criteria, where, for purposes hereof, a triple whose object is the subject of another triple is deemed a direct ancestor of that other triple;
a triple whose subject is the object of another triples is deemed a direct descendent of that other triple;
B. generating an indication of data identified as related in step (A). - View Dependent Claims (33, 34, 35)
-
-
36. A method for identifying related triples in a resource description framework (RDF) data set, comprising
A. executing with respect to the data set the sub-steps of (i) identifying as related data substantially matching a criteria; -
(ii) identifying as related data (hereinafter “
identified descendent”
) that is a direct descendent of data (hereinafter “
identified ancestor”
) identified as related in any of sub-steps (i) and (ii), and which identified descendent(a) is not associated with the identified ancestor via a predicate substantially matching a predicate named in the criteria, if any, and (b) is not in substantial conflict with the criteria;
(c) is not associated with the identified ancestor via a predicate matching a predicate by which the identified ancestor is associated with a triple, if any, as a result of which the identified ancestor was identified as related, B. generating an indication of data identified as related in step (A). - View Dependent Claims (37, 38, 39)
-
-
42. (canceled)
Specification