Methods and apparatus for identifying related nodes in a directed graph having named arcs
First Claim
Patent Images
1. A method for identifying related triples in a resource description framework (RDF) data set, comprisingA. executing, on a digital data processing system, 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 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 triple is deemed a direct descendent of that other triple,wherein sub-step (iii) is defined below;
(iii) identifying as related a triple (hereinafter “
identified descendent”
) that is a direct descendent of a 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),(iv) identifying as related a triple that is a sibling of another triple identified as related in sub-step (i) and that is not in substantial conflict with the criteria, where triples that share a common subject are deemed siblingsB. generating an indication of triples identified as related in step (A),C. wherein the criteria specifies a predicate and an object associated with that predicate, and wherein sub-step (ii) includes comparing at least one of the predicate and object specified in the criteria with the direct ancestor in order to determine whether the direct ancestor is in substantial conflict with the criteria.
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.
200 Citations
10 Claims
-
1. A method for identifying related triples in a resource description framework (RDF) data set, comprising
A. executing, on a digital data processing system, 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 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 triple is deemed a direct descendent of that other triple, wherein sub-step (iii) is defined below; (iii) identifying as related a triple (hereinafter “
identified descendent”
) that is a direct descendent of a 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), (iv) identifying as related a triple that is a sibling of another triple identified as related in sub-step (i) and that is not in substantial conflict with the criteria, where triples that share a common subject are deemed siblings B. generating an indication of triples identified as related in step (A), C. wherein the criteria specifies a predicate and an object associated with that predicate, and wherein sub-step (ii) includes comparing at least one of the predicate and object specified in the criteria with the direct ancestor in order to determine whether the direct ancestor is in substantial conflict with the criteria.
-
-
2. A method for identifying related triples in a resource description framework (RDF) data set, comprising
A. executing, on a digital data processing system, 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 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 triple is deemed a direct descendent of that other triple, wherein sub-step (iii) is defined below; (iii) identifying as related a triple (hereinafter “
identified descendent”
) that is a direct descendent of a 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), C. wherein the criteria specifies a predicate and an object associated with that predicate, and wherein sub-step (ii) includes comparing at least one of the predicate and object specified in the criteria with the direct ancestor in order to determine whether the director ancestor is in substantial conflict with the criteria.
-
-
3. A method for identifying related triples in a resource description framework (RDF) data set, comprising
A. executing, on a digital data processing system, 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 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 triple is deemed a direct descendent of that other triple, wherein sub-step (iii) is defined below; (iii) identifying as related a triple (hereinafter “
identified descendent”
) that is a direct descendent of a 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), C. wherein the criteria specifies a predicate and an object associated with that predicate, and wherein sub-step (iii) includes comparing at least one of the predicate and object specified in the criteria with the identified descendent in order to determine whether the identified descendent ancestor is in substantial conflict with the criteria.
-
-
4. A method for identifying related triples in a resource description framework (RDF) data set, comprising
A. executing, on a digital data processing system, 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 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 triple is deemed a direct descendent of that other triple, wherein sub-step (iii) is defined below; (iii) identifying as related a triple (hereinafter “
identified descendent”
) that is a direct descendent of a 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), C. executing step (A) with respect to a first data set of RDF triples, and D. executing step (A) separately with respect to a second, related data set of RDF triples, E. wherein the criteria specifies a predicate and an object associated with that predicate, and wherein sub-step (ii) includes comparing at least one of the predicate and object specified in the criteria with the direct ancestor in order to determine whether the direct ancestor is in substantial conflict with the criteria. - View Dependent Claims (5)
-
-
6. A method for identifying related triples in a resource description framework (RDF) data set, comprising
A. executing, on a digital data processing system, 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 (hereinafter “
identified descendent”
) that is a direct descendent of a triple (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, where 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 triple is deemed a direct descendent of that other triple; B. generating an indication of triples identified as related in step (A), C. wherein the criteria specifies a predicate and an object associated with that predicate, and wherein sub-step (ii) includes comparing at least one of the predicate and object specified in the criteria with the identified descendent in order to determine whether the identified descendent is in substantial conflict with the criteria. - View Dependent Claims (7, 8, 9, 10)
-
Specification
-
- Resources
Litigation Campaign Assessment
Thank you for your request. You will receive a custom alert email when the Litigation Campaign Assessment is available.
×
-
Current AssigneeObjectstore Incorporated
-
Original AssigneeMetatomix, Inc. (ESW Capital, LLC)
-
InventorsGreenblatt, Howard, Greenblatt, Alan, Bigwood, David A., Britton, Colin P.
-
Primary Examiner(s)Ehichioya; Fred I
-
Application NumberUS11/245,994Publication NumberTime in Patent Office1,488 DaysField of Search707/100, 707/1, 707/2, 707/3, 707/4, 707/10, 707/102, 707/103.Y, 707/200US Class Current1/1CPC Class CodesG06F 16/278 Data partitioning, e.g. hor...Y10S 707/99934 Query formulation, input pr...Y10S 707/99935 Query augmenting and refini...Y10S 707/99942 Manipulating data structure...Y10S 707/99944 Object-oriented database st...Y10S 707/99945 Object-oriented database st...
