Browse Prior Art Database

Improved Rete Algorithm: Hashing Techniques Applied to Partial Match Memories

IP.com Disclosure Number: IPCOM000109239D
Original Publication Date: 1992-Aug-01
Included in the Prior Art Database: 2005-Mar-23
Document File: 1 page(s) / 59K

Publishing Venue

IBM

Related People

Schor, MI: AUTHOR

Abstract

Disclosed is a process which uses hashing to optimize searches in large RETE "result memories."

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

Improved Rete Algorithm: Hashing Techniques Applied to Partial Match Memories

       Disclosed is a process which uses hashing to optimize
searches in large RETE "result memories."

      The RETE method is commonly used in pattern matchers, such as
OPS5 production systems, to keep track of partial matches of data
with pattern parts.  These partial matches are stored in look-up
tables referred to as "result memories."

      Searches were originally performed on "result memories" using a
linear search technique.  However, linear searches become inefficient
when the size of the result memory is large.

      One way to speed up the search process is to use a hashing
technique.  The hashing algorithm builds a result memory look-up
table to hold the matched data or "object keys."  This is
accomplished in the following manner.

      The hashing algorithm generates a "hash code" from the object
keys which determines the location or address at which the object key
is to be stored.  In some cases, the same "hash code" may be
generated for more than one object key.  This is known as a
"collision."  Consequently, the address identified by the hash code
is already occupied.  To avoid overwriting this data, the colliding
object key is stored instead in the next available sequential
address.

      Storing items in this manner can reduce search time
significantly.  To perform a search, the hashing algorithm merely
generates a hash code for the item or...