Data processors

• US 7,065,517 B1
• Filed: 06/26/2000
• Issued: 06/20/2006
• Est. Priority Date: 06/26/1999
• Status: Expired due to Fees

• Current Assignee: York University
• Original Assignee: University of York
• Inventors: Austin, James Leonard
• Primary Examiner(s): Gaffin, Jeffrey
• Assistant Examiner(s): Mahmoudi, Hassan
• Application Number:
  US10/019,172
• Time in Patent Office: 2,185 Days
• Field of Search: 707/1, 707/3, 707/5, 707/10, 707/104.1, 702/19, 711/104, 711/144
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

An input device receives sets of input data to be stored in a correlation matrix memory. A sampler derives, from each set of input data, a respective set of tuples, and a coder codes each of the tuples, which are then combined for the respective set of input data. A separator generator generates for each set of input data a respective, associated, unique separator, which is stored with its respective set of input data. For each set of input data, the respective combined coded tuples and the respective unique separator are applied to the correlation matrix memory as a row address and as a column address, or vice-versa.

Claims

1. A data processor comprising:

(a) a correlation matrix memory arranged to store data;

(b) input means arranged to receive sets of input data to be stored in the correlation matrix memory;

(c) a sampler arranged to derive, from each set of input data, a respective set of tuples;

(d) a coder arranged to code each of the tuples by tensoring;

(e) a combiner arranged to combine the coded tuples for a respective set of input data;

(f) a separator generator arranged to generate for each set of input data a respective, associated, unique separator;

(g) storage means arranged to store the association of each separator with its respective set of input data; and

(h) addressing means arranged to applying to the correlation matrix memory, for each set of input data, the respective combined coded tuples as a row address and the respective unique separator as a column address, or vice-versa;

wherein said correlation matrix memory comprises a plurality of sub-correlation matrix memories;

said addressing means is arranged to access a first one of said sub-correlation matrix memories and apply the combined coded tuples of a respective set of input data to that sub-correlation matrix memory unless a respective row (or column) of that sub-correlation matrix memory will become saturated by application of those tuples; and

in the event of such prospective saturation, access successive ones of the sub-correlation matrix memories until those tuples can by applied to a respective one of the sub-correlation matrix memories without such saturation.

2. A data processor according to claim 1, wherein the combined coded tuples for each set of input data are in the form of a binary coded word;

the data processor further comprises a translator arranged to translate each such binary coded word into a translated word comprising index values representing which bits of the binary coded word are set; and

said addressing means is arranged to apply the translated word to the correlation matrix memory.

3. A data processor according to claim 1, wherein said separator generator is arranged to generate separators in a random manner.

4. A data processor according to claim 1, wherein said separator generator is arranged to generate separators which are M bits wide and having N bits set, where N>

1 or N=1, and where N<

M.

5. A data processor according to claim 1, wherein, for each said set of tuples, each tuple comprises three successive elements of a respective set of input data, and each successive tuple is offset by one such element from the preceding tuple.

6. A data processor according to claim 1, wherein said combiner is arranged to combine the coded tuples for a respective set of input data, by superimposition.

7. A data processor according to claim 1, wherein at least some of the rows (or columns) of the correlation matrix memory are represented by binary words, each of which represents the positions of each bit in the respective row (or column) which is set.

8. A data processor according to claim 1, arranged to process sets of input data and query data in the form of postal addresses.

9. A method of processing data, comprising the steps of:

(a) receiving sets of input data to be stored in a correlation matrix memory;

(b) deriving, from each set of input data, a respective set of tuples;

(c) coding each of the tuples;

(d) combining the coded tuples for a respective set of input data;

(e) generating for each set of input data a respective, associated, unique separator;

(f) storing the association of each separator with its respective set of input data;

(g) applying to the correlation matrix memory, for each set of input data, the respective combined coded tuples as a row address and the respective unique separator as a column address, or vice-versa;

(h) receiving sets of query data to be matched with sets of input data stored in the correlation matrix memory;

(i) deriving, for each set of query data, a respective set of coded tuples analogous to those derived for the original input data;

(j) applying to the correlation matrix memory, for each set of query data, the respective combined coded tuples as a row (or column) address;

(k) outputting a raw superimposed separator which represents, for a respective set of query data, the number of rows (or columns) having a bit set by the applied combined coded tuples in each column (or row) represented by the raw superimposed separator;

(l) converting the raw superimposed separator into a binary superimposed separator;

(m) extracting one or more individual separator from the binary superimposed separator; and

(n) identifying the or each respective original set of input data from association with the or each individual separator extracted from the binary superimposed separator.

10. A method according to claim 9, wherein said sets of input data and query data are in the form of postal addresses.

11. A data processor comprising:

(a) a correlation matrix memory arranged to store data;

(b) input means arranged to receive sets of input data to be stored in the correlation matrix memory;

(c) a sampler arranged to derive, from each set of input data, a respective set of tuples;

(d) a coder arranged to code each of the tuples by tensoring;

(e) a combiner arranged to combine the coded tuples for a respective set of input data;

(f) a separator generator arranged to generate for each set of input data a respective, associated, unique separator;

(g) storage means arranged to store the association of each separator with its respective set of input data; and

(h) addressing means arranged to applying to the correlation matrix memory, for each set of input data, the respective combined coded tuples as a row address and the respective unique separator as a column address, or vice-versa;

wherein the data processor is arranged to receive sets of query data to be matched with sets of input data stored in the correlation matrix memory, and to derive, for each set of query data, a respective set of coded tuples analogous to those derived for the original input data, and to apply to the correlation matrix memory, for each set of query data, the respective combined coded tuples as a row (or column) address;

the data processor further comprising;

(i) output means for outputting a raw superimposed separator which represents, for a respective set of query data, the number of rows (or columns) having a bit set by the applied combined coded tuples in each column (or row) represented by the raw superimposed separator;

(j) threshold means arranged to convert the raw superimposed separator into a binary superimposed separator; and

(k) an extractor arranged to extract individual separators from the binary superimposed separator.

12. A data processor according to claim 11, wherein said thresholding means sets an absolute threshold value, and provides said binary superimposed separator as a word in which bits represent respective columns (or rows) of the correlation matrix memory, and each of those bits is set if the number of rows (or columns) having a bit set by the applied combined coded tuples in the respective column (or row) equals or is greater than said absolute threshold value.

13. A data processor according to claim 11, wherein said thresholding means determines a value k, and provides said binary superimposed separator as a word in which bits represent respective columns (or rows) of the correlation matrix memory, and are set for the k respective columns (or rows) having the highest number of rows (or columns) which have a bit set by the applied combined coded tuples in the correlation matrix memory.

14. A data processor according to claim 11, further comprising back-checking means arranged to compare sets of recalled data, identified by respective separators extracted by said extractor, with original query data, in order to identify the set or sets of recalled data which matches best the original query data.

15. A data processor according to claim 11, arranged to process sets of input data and query data in the form of postal addresses.