Derivation of an Efficient Rule System Pattern Matcher
Formalizing algorithm derivations is a necessary prerequisite for developing automated algorithm design systems. This report describes a derivation of an algorithm for incrementally matching conjunctive patterns against a growing database. This algorithm, which is modeled on the Rete matcher...
| Main Author: | |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Online Access: | http://hdl.handle.net/1721.1/6979 |
| _version_ | 1811071502005567488 |
|---|---|
| author | Wertheimer, Jeremy M. |
| author_facet | Wertheimer, Jeremy M. |
| author_sort | Wertheimer, Jeremy M. |
| collection | MIT |
| description | Formalizing algorithm derivations is a necessary prerequisite for developing automated algorithm design systems. This report describes a derivation of an algorithm for incrementally matching conjunctive patterns against a growing database. This algorithm, which is modeled on the Rete matcher used in the OPS5 production system, forms a basis for efficiently implementing a rule system. The highlights of this derivation are: (1) a formal specification for the rule system matching problem, (2) derivation of an algorithm for this task using a lattice-theoretic model of conjunctive and disjunctive variable substitutions, and (3) optimization of this algorithm, using finite differencing, for incrementally processing new data. |
| first_indexed | 2024-09-23T08:52:12Z |
| id | mit-1721.1/6979 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:52:12Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/69792019-04-10T11:52:15Z Derivation of an Efficient Rule System Pattern Matcher Wertheimer, Jeremy M. Formalizing algorithm derivations is a necessary prerequisite for developing automated algorithm design systems. This report describes a derivation of an algorithm for incrementally matching conjunctive patterns against a growing database. This algorithm, which is modeled on the Rete matcher used in the OPS5 production system, forms a basis for efficiently implementing a rule system. The highlights of this derivation are: (1) a formal specification for the rule system matching problem, (2) derivation of an algorithm for this task using a lattice-theoretic model of conjunctive and disjunctive variable substitutions, and (3) optimization of this algorithm, using finite differencing, for incrementally processing new data. 2004-10-20T20:12:04Z 2004-10-20T20:12:04Z 1989-02-01 AITR-1109 http://hdl.handle.net/1721.1/6979 en_US AITR-1109 9034855 bytes 3382405 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Wertheimer, Jeremy M. Derivation of an Efficient Rule System Pattern Matcher |
| title | Derivation of an Efficient Rule System Pattern Matcher |
| title_full | Derivation of an Efficient Rule System Pattern Matcher |
| title_fullStr | Derivation of an Efficient Rule System Pattern Matcher |
| title_full_unstemmed | Derivation of an Efficient Rule System Pattern Matcher |
| title_short | Derivation of an Efficient Rule System Pattern Matcher |
| title_sort | derivation of an efficient rule system pattern matcher |
| url | http://hdl.handle.net/1721.1/6979 |
| work_keys_str_mv | AT wertheimerjeremym derivationofanefficientrulesystempatternmatcher |