Data string storage device and method of storing and retrieving data strings

• US 5,129,074 A
• Filed: 09/20/1989
• Issued: 07/07/1992
• Est. Priority Date: 09/22/1988
• Status: Expired due to Fees

• Current Assignee: Hitachi Vlsi Engineering Corporation
• Original Assignee: Hitachi Vlsi Engineering Corporation
• Inventors: Saito, Nobuo, Atoda, Oichi, Kikuchi, Takashi, Fukuta, Hiroshi
• Primary Examiner(s): Fleming, Michael R.
• Assistant Examiner(s): Ray, Gopal C.
• Application Number:
  US07/409,672
• Time in Patent Office: 1,021 Days
• Field of Search: 365/230.03, 365/220, 365/49, 395/425, 364/200 MS File, 364/900 MS File
• US Class Current: 711/173
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 8/313 Logic programming, e.g. PROLOG programming language

Abstract

A data storage device for storing data strings each including units of data has a plurality of memory sections each for storing therein a table, a plurality of processor elements one provided for each of the tables and a controlling unit having an internal memory in which data strings are stored. The table contains a plurality of records each including a unit of data, a first index data representative of the number of units of data of a data string which the unit of data constitutes and a second index data unique to each individual data string. The processor elements access in parallel their associated tables under control of the control unit for data storage and data retrieval. The first and index data are generated by the controller for the purpose of data storage. For retrieval of data strings: a key data string is divided into units of data; retrieval keys are produced each from a combination of one of the divided units of data and a third index data representing the number of units of data of the key data string; second index data are retrieved in parallel in the tables of the data storage device with the retrieval keys so that a single second index data common to all of the retrieved second index data is found among them; and a data string corresponding to the found common second index data is outputted from the internal memory of the storage device.

Claims

1. A data storage device for storing therein data strings each including units of data, comprising:

memory means having a plurality of memory sections;

a plurality of processor elements one provided for each of said memory sections, said processor elements being arranged for parallel access to their associated memory sections for data storage and data retrieval; and

control means having an internal memory and a controller, said controller serving for data storage, and including a write means to write data strings supplied from a central processing unit to the data storage device in said internal memory, first dividing means to divide each of said data strings into units of data and, generating means to generate a first index data representing the number of units of data of said data string and a second index data unique to said data string, said processor elements being controlled by a processor element control means of said control means to write said units of data along with corresponding first and second index data in their associated memory sections by said parallel access for data storage so that a retrieval means retrieves said written units of data in terms of said first and second index data in respective memory sections by said parallel access for data retrieval, said controller further serving for data retrieval, and further including a second dividing means to divide a data string supplied to the data storage device into units of data, transfer means to transfer the divided units of data to said processor elements for retrieval in their associated memory sections of second index data corresponding to said units of data, detecting means to detect a single common second index data among said retrieved index data and output means to output from said internal memory a data string corresponding to the detected common second index data.

2. A data storage device according to claim 1, in which combinations of a divided unit of data and a first index data written in each of said memory sections are arranged such that combinations having units of data and index data identical with one another are located adjacent to one another in each memory section.

3. A data storage device for storing therein data strings each including units of data, comprising:

memory means having a plurality of memory sections each storing therein a hash table;

a plurality of table processors one provided for each of said hash tables, said table processors being arranged for parallel access to their associated memory sections for data storage and data retrieval; and

control means having an internal memory and a controller, said controller serving for data storage, and including a write means to write data strings supplied from a central processing unit to the data storage device in said internal memory, first dividing means to divide each of said data strings into units of data and generating means to generate a first index data representing the number of units of data of said data string and a second index data unique to said data string, said table processors being controlled by a table processor control means of said control means to write said units of data along with corresponding first and second index data in their associated hash tables in said memory sections by said parallel access for data storage so that a retrieval means retrieves said written units of data in terms of said first and second index data in respective hash tables by said parallel access for data retrieval, said controller further serving for data retrieval, and further including a second dividing means to divide a data string supplied to the data storage device into units of data, transfer means to transfer the divided units of data to said table processors for retrieval in their associated hash tables in said memory sections of second index data corresponding to said units of data, detecting means to detect a single common second index data among said retrieved second index data and output from said internal memory a data string corresponding to the detected common second index data.

4. A system for storing and retrieving data strings each including units of data, comprising:

a central processing unit; and

a data storage unit for storing therein data strings, said central processing unit being coupled to said data storage unit for storing and retrieving data strings therein, said data storage unit including,

memory means having a plurality of memory sections,

a plurality of processor elements one provided for each of said memory sections, said processor elements being arranged for parallel access to their associated memory sections for data storage and data retrieval, and

control means having an internal memory and a controller, said controller serving for data storage, and including a write means to write data strings supplied from said central processing unit to said data storage unit in said internal memory, first dividing means to divide each of said data strings into units of data and generating means to generate a first index data representing the number of units of data of a data string and a second index data unique to a data string, said processor elements being controlled by a processor element control means of said control means to write said units of data along with corresponding first and second index data in their associated memory sections by said parallel access for data storage so that a retrieval means retrieves said written units of data in terms of said first and second index data in respective memory sections by said parallel access for data retrieval, said controller further serving for data retrieval, and further including a second dividing means to divide a data string supplied from said central processing unto to said data storage unit into units of data, transfer means to transfer the units of data to said processor elements for retrieval in their associated memory sections of second index data corresponding to said units of data, detecting means to detect a single common second index data among said retrieved second index data and output means to output, from said internal memory to said central processing unit, a data string corresponding to the detected common second index data.

5. A method of storing data strings in a data storage device, each of said data strings including units of data, the method comprising the steps of:

storing by a storing means, an inputted data string in a first portion of said storage device;

dividing by a dividing means of said storage device, said inputted data string into units of data and attaching a first index data to each of said divided units of data, said first index data representing the number of units of data included in that data string which said each unit of data constitutes;

generating by a generating means of said storage device, a second index data for said inputted data string, said second index data being unique to each data string, and producing records each including a unit of data, a first index data and a second index data; and

accessing in parallel, by an accessing means of said storage devices, individual memory sections to store said records therein in a second portion of said storage device, said memory sections being always responsible for units of data in predetermined locations in data strings.

6. A method of storing and retrieving data strings in a data storage device, each of said data strings including units of data, the method comprising the steps of:

storing by a storing means, an inputted data string for storage in a first portion of said storage device;

dividing by a first dividing means, said inputted data string for storage into units of data and attaching a first index data to each of said divided units of data, said first index data representing the numbers of units of data included in that data string which said each unit of data constitutes;

generating by a generating means, a second index data for said inputted data string for storage, said second index data being unique to each data string, and producing records each including a unit of data, a first index data and a second index data;

accessing in parallel, by an accessing means, individual memory sections to store said records therein in a second portion of said storage device, said memory sections being always responsible for units of data in predetermined locations in data strings;

dividing by a second dividing means, an inputted data string for retrieval into units of data, detecting the number of units of data included in said inputted data string for retrieval and producing retrieval keys each including a combination of one of said divided units of data and a third index data representing the detected number of units of data;

retrieving in parallel, by a retrieving means, second index data in said memory sections in said second part of said data storage device with said retrieval keys;

detecting by a detecting means, a single second index data common to all of the retrieved second index data among them; and

outputting by an outputting means, a data string corresponding to said detected single common index data from said first portion of said storage device to a central processing unit.

7. A method according to claim 6, in which the retrieved second index data in said parallel retrieving step are those in records having first index data and units of data identical with said third index data and said divided units of data of said inputted data string for retrieval, respectively, and are those in records having first index data identical with said third index data of said inputted data string for retrieval and variables.

8. A method according to claim 6, in which said step of parallel retrieving second index data in said memory sections in said second part of said data storage device with said retrieval keys is carried out with predetermined matching rules.