Processing of tree data structures
First Claim
1. A method for processing a collection of tree data structures in a computer-readable database, the method comprising:
- identifying a plurality of disjoint sets of trees in the collection of tree data structures, each tree in the respective set of trees having a same structure and including at least one leaf node having a value;
for each of the plurality of disjoint sets of trees, forming a pattern having the same structure as each tree in the set of trees thereby generating a set of patterns;
storing the set of patterns in a computer-readable memory in lieu of storing the plurality of sets of trees corresponding to each pattern;
storing the at least one leaf node of each tree of each of the sets of trees in a computer-readable memory;
associating each pattern in the set of patterns with the at least one leaf node of each tree in the set of trees corresponding to the pattern; and
processing the set of patterns with distributed processors, wherein each distributed processor processes one or more of the patterns in the set of patterns.
1 Assignment
0 Petitions
Accused Products
Abstract
Data items are represented by trees and stored in a database, the collection of data items defining a forest. Queries and masks are also represented by trees. A method for navigating the forest of data items is disclosed in the context of a graphical user interface. A set of operations on trees are defined such that the data items can be queried on the basis of structure as well as node values. That is, the query can include a specification of the relationship between nodes in a tree, as well as the data in the nodes themselves. Exemplary implementations of such operations are disclosed in the context of a database update procedure. Additionally disclosed are methods for efficiently storing and processing the forest of data items.
143 Citations
10 Claims
-
1. A method for processing a collection of tree data structures in a computer-readable database, the method comprising:
-
identifying a plurality of disjoint sets of trees in the collection of tree data structures, each tree in the respective set of trees having a same structure and including at least one leaf node having a value; for each of the plurality of disjoint sets of trees, forming a pattern having the same structure as each tree in the set of trees thereby generating a set of patterns; storing the set of patterns in a computer-readable memory in lieu of storing the plurality of sets of trees corresponding to each pattern; storing the at least one leaf node of each tree of each of the sets of trees in a computer-readable memory; associating each pattern in the set of patterns with the at least one leaf node of each tree in the set of trees corresponding to the pattern; and processing the set of patterns with distributed processors, wherein each distributed processor processes one or more of the patterns in the set of patterns. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A system for processing a collection of tree data structures, the system comprising:
-
a database component operative to maintain a database comprising the collection of tree data structures; a processing component communicatively connected to the database component, the processing component programmed to perform actions comprising; identifying, by communicating with the database component, a plurality of disjoint sets of trees in the collection of tree data structures, each tree in the respective set of trees having a same structure and including at least one leaf node having a value; for each of the plurality of disjoint sets of trees, forming a pattern having the same structure as each tree in the set of trees thereby generating a set of patterns; storing the set of patterns in a communicatively connected computer-readable memory in lieu of storing the plurality of sets of trees corresponding to each pattern; storing the at least one leaf node of each tree of each of the sets of trees in the computer-readable memory; associating each pattern in the set of patterns with the at least one leaf node of each tree in the set of trees corresponding to the pattern; and processing the set of patterns with distributed processors, wherein each distributed processor processes one or more of the patterns in the set of patterns. - View Dependent Claims (7, 8, 9, 10)
-
Specification