Browse Prior Art Database

Rete Pattern Matching Using Hashing Applied to Equal Join Tests

IP.com Disclosure Number: IPCOM000119840D
Original Publication Date: 1991-Mar-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 2 page(s) / 82K

Publishing Venue

IBM

Related People

Schor, MI: AUTHOR

Abstract

This invention relates to a computer-implemented method for minimizing the number of data object and pattern matchings occurring at the nodes of a flow graph of the type in which elements of a pattern are compiled into an acyclic directed graph of entry and join nodes. The entry nodes represent the single elements of the pattern while the join nodes represent compound elements. The entry and join nodes are connected in pattern-directed association.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Rete Pattern Matching Using Hashing Applied to Equal Join Tests

      This invention relates to a computer-implemented method
for minimizing the number of data object and pattern matchings
occurring at the nodes of a flow graph of the type in which elements
of a pattern are compiled into an acyclic directed graph of entry and
join nodes.  The entry nodes represent the single elements of the
pattern while the join nodes represent compound elements.  The entry
and join nodes are connected in pattern-directed association.

      In the prior art, the so-called RETE pattern-matching algorithm
has been modified to include the steps of applying data objects to
the entry nodes of the flow graph, performing a comparison match
between the attributes of the data objects and the node pattern
elements, maintaining a list of instantiations satisfying the match
conditions expressed at that node and passing tokens to descendant
nodes, maintaining pointers to all ancestor nodes through which the
token for each object passed, and traversing the pointers as a path
for avoiding those flow graph node pattern/object matchings redundant
between a previously matched and an object currently being processed.

      The join operation occurs when a change token is passed down
from the right or left predecessor in the flow graph. The basic join
operation compares the change token with each token from the opposite
memory running any tests specified. Those combinations of change
token and opposite memory token pass through the node and are used
for subsequent processing.

      In this method, an additional hash table is used to speed up
the operation when some of the specified tests are equal.  The hash
table has a key and an associated value. The key is an observed value
in a field used as one argument in an equal test.  The value consists
of a pair of lists. The first list is a list of tokens in the
left memory having that value in a tested attribute slot.  The second
list is a list of tokens in the right memory having that value in the
tested attribute slot.  The keys form a non-overl...