Back to results
US 7,454,415 B1Granted
Method and system for pattern matching having holistic twig joins
AssigneesThe Trustees of Columbia University, AT&T Corp.
InventorsNicolas Bruno, Nikolaos Koudas, Divesh Srivastava
Life of this patent
Estimating the term…
Abstract
A method of query pattern matching uses a chain of linked stacks to compactly represent partial results to root-to-leaf query paths, which are then composed to obtain matches for the twig pattern.
Claims18
A method of computing an answer to a query path pattern, comprising:
- determining whether a first set of streams in a subtree rooted at a node q is empty;
- and
- if so, then terminating the method and if not, then the method comprises:
- (a) retrieving a first node in the first set of streams having a minimum ordering value;
- (b) removing partial answers that cannot extend to full answers from a stack associated with the first node;
- (c) augmenting remaining partial answers with a further stream node;
- (d) determining whether the further stream node is a leaf node;
- and
- (e) producing solutions if the further stream stream node is a leaf node, and if the first node is not a leaf node, returning to step (a);
- associating nodes in a query pattern with respective streams containing positional attributes, wherein the minimum ordering value is for a first one of the positional attributes;
- associating a respective stack to each node in the query pattern;
- and
- sorting the stream nodes according to a first one of the positional attributes.
10 more elements
A computing device that computes an answer to a query path pattern, the computing device comprising:
- a processor that processes functions as directed by software modules;
- a module configured to determine whether a first set of streams in a subtree rooted at a node q is empty;
- and
- a module configured to terminate if the first set of streams in the subtree rooted at the node q is empty, and to perform the following functions if the first set of streams in the subtree rooted at the node q is not empty:
- (a) retrieve a first node in the first set of streams having a minimum ordering value;
- (b) remove partial answers that cannot extend to full answers from a stack associated with the first node;
- (c) augment remaining partial answers with a further stream node;
- (d) determine whether the further stream node is a leaf node;
- and
- (e) produce solutions if the further stream node is a leaf node, and if the first node is not a leaf node, returning to the function of module (a);
- a module configured to associate nodes in a query pattern with respective stream nodes containing positional attributes, wherein the minimum ordering value is for a first one of the positional attributes;
- a module configured to associate a respective stack to each node in the query pattern;
- and
- a module configured to sort the stream nodes according to a first one of the positional attributes.
11 more elements
A computer memory storing a computer program having instructions for controlling a computing device to compute an answer to a query path pattern, the instructions comprising:
- determining whether a first set of streams in a subtree rooted at a node q is empty;
- and
- if so, then terminating and if not, then the instructions control the computing device to perform the following functions:
- (a) retrieving a first node in the first set of streams having a minimum ordering value;
- (b) removing partial answers that cannot extend to full answers from a stack associated with the first node;
- (c) augmenting remaining partial answers with a further stream node;
- (d) determining whether the further stream node is a leaf node;
- and
- (e) producing solutions if the further stream node is a leaf node, and if the first node is not a leaf node, returning to step (a);
- associating nodes in a query pattern with respective streams containing positional attributes, wherein the minimum ordering value is for a first one of the positional attributes;
- associating a respective stack to each node in the query pattern;
- and
- sorting the stream nodes according to a first one of the positional attributes.
10 more elements
Dependencies are inferred from the claim text.