US 2004/0073545 A1 · Methods and apparatus for identifying related nodes in a directed graph having named arcs

Abstract

The invention provides methods for identifying related data in a directed graph (e.g., an RDF data set). A “first” 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.

Claims42

Dependent claims

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 in any of sub-steps (i), (ii) and (iii), and that is not in substantial conflict with the criteria;
(iii) 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), (ii) and (iii), 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 during execution of sub-step (ii),
B. generating an indication of data identified as related in step (A).

5 more elements

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

6 more elements

Dependencies are inferred from the claim text.

Methods and apparatus for identifying related nodes in a directed graph having named arcs

Life of this patent

Methods and apparatus for identifying related nodes in a directed graph having named arcs

Life of this patent

Abstract

Claims42