US 4,290,115 AGranted

Data processing method and means for determining degree of match between two data arrays

AssigneeSystem Development Corporation

InventorsPaul E. Pitt, Edward L. Glaser, Louis M. Galie

Life of this patent

Estimating the term…

Loading patent…

Abstract

Method and means are disclosed for determining a particular criterion value and an associated positional value for a degree of match between the juxtaposition of a plurality of events of a query and a plurality of events of a stored data base entry. The method and means use a processing means having a plurality of data stores and a temporary store for each data store. Each data store stores a group of data values. The data values are priorly formed and represent the number of event positions between the occurrence of events in the query and the occurrence of the corresponding events in the stored data base. The processing means using the plurality data stores, the temporary stores and the data values stored therein form determined data values and sum-of-distance values which are then used by a utilizing means for in turn deriving a criterion value and a positional value corresponding to the degree of match between the query and the data base.

Claims57

Dependent claims

A method utilizing data processing means comprising a plurality of data stores and a corresponding temporary store for each such data store, the method determining a particular criterion value and an associated positional value for the degree of match between the juxtaposition of a plurality of event types of a query and a plurality of event types of a stored data base entry, the method utilizing a priorly-formed array of data values, each data value representing the number of event positions between the occurrence of an event type in the query, the occurrence of a corresponding event type in the stored data base, a group of one or more data values being provided for each of a plurality of different query event types, each different group being stored in a different data store with the data values thereof arranged in monotonic order from a first end, the method comprising the steps of:

(a) designating a data value in each of a plurality of data stores as a first data value;
(b) detecting at least one of the designated first data values having a predetermined magnitude relative to the other designated first data values;
(c) storing the at least one detected data value in the temporary store which corresponds to the data store in which such detected data value is detected;
(d) forming for each of individual data stores a first distance value which represents the algebraic difference between the detected data value and the designated data value in such data store;
(e) forming for each of individual data stores a second distance value representing the algebraic difference between the detected data value and a data value in the temporary store corresponding to such individual data store;
(f) selecting for each of individual data stores a distance value from the corresponding first and second distance values, the selected distance value having a predetermined magnitude relative to the other;
(g) forming for a detected data value a sum-of-distance value representing the sum of the absolute values of the selected distance values formed therefrom;
(h) designating a new data value in the data value store containing the at least one detected data value and repeating the steps (b)-(h) using such new data value as a designated data value,
the step of designating a new data value including the step of designating, in a predetermined order in the monotonic order of data values, the next data value from the one which was previously designated;
and
(i) utilizing the detected data values and the corresponding sum-of-distance values provided during steps (b)-14 (h) for deriving such criterion value and positional value.

8 more elements

Data processing means comprising a plurality of data stores and a corresponding temporary store for each such data store, the data processing means determining a particular criterion value and an associated position value for a match between the juxtaposition of a plurality of event types of a query and a plurality of event types of a stored data base, the data processing means utilizing a priorly-formed array of data values, each data value representing the number of event positions between the occurrence of an event type in the query and the occurrence of a corresponding event type in the stored data base, a group of one or more data values being provided for each of a plurality of different query event types, each different group being stored in a different data store with the values thereof arranged in monotonic order from a first end, the data processing means comprising:

(a) means for designating a data value in each of a plurality of data stores as a first data value;
(b) means for detecting at least one of the designated first data values having a predetermined magnitude relative to the other designated first data values;
(c) means for storing the at least one detected data value in the temporary store which corresponds to the data store in which such detected data value is detected;
(d) means for forming for each of individual data stores a first distance value which represents the algebraic difference between the detected data value and the designated data value in such data store;
(e) means for forming for each of individual data stores a second distance value representing the algebraic difference between the detected data value and a data value in the temporary store corresponding to such individual data store;
(f) means for selecting for each of individual data stores a distance value from the corresponding first and second distance values, the selected distance value having a predetermined magnitude relative to the other;
(g) means for forming for a detected data value a sum-of-distance value representing the sum of the absolute values of the selected distance values formed therefrom;
(h) means for designating a new data value in the data value store containing the at least one detected data value wherein the designated value is the next data value from the one which was previously-designated the next data value in a predetermined order in the monotonic order of data values;
and
(i) means for utilizing the detected data values and the corresponding sum-of-distance values for deriving such criterion value and positional value.

7 more elements

A method utilizing data processing means comprising a store for a dimness value, a store for a positional value, a plurality of data stores, and a temporary store for each such data store, the method determining a particular match between a plurality of event types of a query and a plurality of event types of a stored data base, the method utilizing a priorly-formed array of data values, each data value representing the number of event positions between the juxtaposition of an event type in the query and a corresponding event type in the stored data base, a group of one or more data values being provided for each of a plurality of different query event types, each different group being stored in a different data store with the data values thereof arranged in monotonic order from a first end, the method comprising the steps of:

(a) detecting the data value at the first ends of the groups having a predetermined relation to other data values at the first ends of the groups in data stores;
(b) transferring the detected data value from the corresponding group to the corresponding temporary store, replacing a previous data value therein;
(c) combining data values to form a dimness value representing the sum of the absolute values of algebraic differences where each algebraic difference is taken between the data value which is detected in the preceding step and different ones of the data values existing at the first ends of the groups in the data stores and in the temporary stores;
(d) detecting if the dimness value formed in the last step has a predetermined relation to the value in the dimness value store;
(e) replacing a value in the dimness value store with such formed dimness value if such formed dimness value is detected as having such predetermined relation;
and
(f) replacing a value in the positional store with such detected data value which is used in the step of combining if the dimness value formed from such data value is detected as having such predetermined relation.

4 more elements

Data processing means for determining a particular match between a plurality of event types of a query and a plurality of event types of a stored data base, utilizing a priorly-formed array of data values, each data value representing the number of event positions between the juxtaposition of an event type in the query and a corresponding event type in the stored data base, a group of one or more data values being provided for each of a plurality of different query event types, the processing means comprising:

(a) a store for a dimness value;
(b) a store for a positional value;
(c) a plurality of data stores, each different group being stored in a different data store with the data values thereof arranged in a monotonic order from a first end;
(d) a temporary store for each such data store;
(e) means for detecting the data value at the first ends of the groups having a predetermined relation to other data values at the first ends of the groups in data stores;
(f) means for transferring the detected data value from the corresponding group to the corresponding temporary store, replacing a previous data value therein;
(g) means for combining data values to form a dimness value representing the sum of the absolute values of algebraic differences where each algebraic difference is taken between the data value which is transferred to the temporary store by the preceding means and different ones of the data values existing at the first ends of the groups in the data stores and in the temporary stores;
(h) means for detecting if the dimness value formed by the preceding means has a predetermined relation to the value in the dimness value store;
(i) means for replacing a value in the dimness value store with such formed dimness value if such formed dimness value is detected as having such predetermined relation;
and
(j) means for replacing a value in the positional store with such data value which is used by the means for combining if the dimness value formed from such data value is detected as having such predetermined relation.

8 more elements

Dependencies are inferred from the claim text.