JPS6013388A - Content retrieving type bubble memory device - Google Patents

Abstract

PURPOSE:To shorten retrieving time and to reduce the capacity of a semiconductor RAM and keyword comparing time by using a key code obtained by hashing a keyword. CONSTITUTION:In the retrieving operation by a bubble memory device at the retrieval of its contents, a retrieval keyword 361 is contracted and encoded by an error correcting circuit 360 at first. The obtained key code 362 is successively compared with the contents of a rapid key code memory 350 by a key code comparator 364. Subsequently, a data block having an error correcting code coincident to the retrieval key code 362 is read out from a bubble memory device 300 through a timing control part 320 and whether the keyword in the data block coincides with the retrieval keyword 361 or not is checked by using a keyword comparator 390. As the result of the retrieving operation, the data block having the keyword coincident to the retrieval keyword is entered to a buffer memory 370.

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a content search type bubble memory device that outputs records related to a keyword by giving it a keyword.

The content search type memory device is an important component of a database system. A database performs a service that retrieves data records related to a given keyword, and since the storage capacity is several GB or more, it is extremely difficult to use a magnetic disk. Therefore, a keyword is input, the storage address of a data record related to the keyword is determined on a mass storage device, and then that address is often used to retrieve a data record matching the search keyword from the mass storage device. . At that time, a relationship table between keywords and storage addresses is used,
It is called an indentation table. It is better to store the index table in a content-retrieval type memory. This is mainly because content search processing is required to find addresses from keywords.

Although it is desirable to use an associative memory element to realize a content retrieval type memory, there is nothing that is suitable for practical use in terms of cost and non-volatility in case of large capacity. Therefore, it is necessary to perform content retrieval processing using a normal memory element. At that time, the contents of all addresses in a memory device using ordinary storage elements are read, the keywords of each address are compared, and a search result is obtained from the stored contents of the address where there is a match. 1-
Therefore, a memory that can read the contents of all addresses at high speed is required. High-speed memory elements are commercially available in the form of semiconductors R, , A, and M, but none have a large capacity and are nonvolatile.

Although magnetic bubble memory is not as fast as semiconductor RAM, it has the advantage of being nonvolatile and having a large capacity with low bit cost. Compared to magnetic disks, magnetic bubble memory is much faster when it comes to content retrieval.

A conventional content search type bubble memory device stores a data block at each address consisting of a plurality of keywords and records, and performs a content search by sequentially accessing the data blocks at all addresses.

After that, we proposed a device configuration that aims to improve the processing speed of content retrieval by moving only the keyword portion to semiconductor RAM and comparing the search keyword with the contents of semiconductor RAM when the bubble memory device is powered on. However, when the data size of the keyword is large, there is a drawback that the proportion occupied by the semiconductor ILAM and the time required for comparing the keyword are too large.

The purpose of the present invention is to overcome the above-mentioned deficiencies.

That is, an object of the present invention is to provide a more economical device configuration of a content retrieval type memory using a magnetic bubble memory device, and to reduce the proportion occupied by the built-in semiconductors R and AM.

According to the present invention, data compression means generates a key code by compressing the amount of information of a keyword given from the outside;
A bubble memory device including a bubble chip that stores a record given from the outside, the keyword, and the key code in a data block, and a key code that sequentially reads all the data blocks and stores the key code portions in sequence. a memory, an address scanning means for sequentially scanning the addresses of the key code memory in synchronization with a rotating magnetic field applied to the bubble memory device, and a key code comparison means for comparing the key code with the output of the key code memory. and ticing control means for controlling reading of the data block located in contact with the gate of the bubble memory device according to the matching output of the key code comparison means, and a keyword in the data block read from the bubble memory device. There is provided a content retrieval type bubble memory device characterized in that it includes keyword comparing means for comparing the portion with the keyword given from the outside and outputting the result to the outside as a matching output.

Hereinafter, the present invention will be described in detail using the drawings. FIGS. 1(a) and 1(b) are explanatory diagrams of an indense table. The index table 15 (FIG. 1(a)) shows the address of each record in the large-capacity (magnetic disk) storage device 10 (FIG. 1(b)) in which the database is stored and the information assigned to that record. This shows the correspondence with the keywords. This indence table 15 needs to be stored in a high-speed memory so that the search keyword can be inscribed and the storage address of the record containing the keyword can be quickly found. For example, if you give age 35 as a keyword, output 110 and 069 as addresses 1~, and if you give age 35 and job skill as a key code, output 110 as address and it will be criticized. A magnetic bubble memory can be used to store this index table 15, but if the keyword and address of each row are stored in each page of the bubble memory and all pages are accessed sequentially, even if it is 10m5ec per page,
It takes 1000 seconds to search 100,000 tuples. Therefore, the conventional bubble memory device, which takes too long a search time, is not useful for searching the contents of the index table 15. Of course,
Although it helps increase reliability.

FIG. 2 (b) shows the design concept of the content search type bubble memory device. ) shows the difference in the bubble memory access range that changes due to changes in the data structure.

In Figure 2 (a), the data structure of the basic configuration 24 is such that each page is
It is shown that it consists of the keyword 21 and address record 22 shown in 5. On the other hand, in the content search type bubble memory, a data structure with a hash structure 25 is used, and each page includes, in addition to the keyword 2J and the address record 22, a key code for hashing (separately classifying) each keyword. Arrow 26 indicates that the data size of each keyword is compressed to generate and add a key code. Note that the key codes may be grouped together at the end of each page, or may be inserted immediately after each keyword.

FIG. 2(b) shows that the memory area accessed during content retrieval is narrowed down from area 27 to area 28 or area 29 by changing the data structure. Elijah 27 means all addresses. Area 29 is a memory area containing only pages matching the search keyword. This is the memory area that will be requested by content search and will not be smaller than this. Area 28 is a memory area between areas 27 and 29, and key code 23
It has been narrowed down to the parts selected by. In order to bring the area 28 closer to the area 29, it is necessary to optimize the data compression (mapping conversion) method from keyword to key code.

Generally, if the data size of a keyword is n bits, 2n keywords can exist. but,
The number of rows (double) of the index φ table is 100,000 or 1
0,000,000, which can be said to be sufficiently smaller than 2. Or, conversely, the data size of the keyword is not so small that n ranges from 128 to 512 bits. Therefore, a hash function is often used to compress the data size of a keyword into an 8- to 16-bit key code. If the data size of the key code is m, the badge function is 10m1e
It can be said to be a data compression (or slam classification) method that divides c million tuples into 2m classes equally (or randomly).

If an ideal hash function is completed, it is possible to generate a −m-bit key code for an n-bit keyword and narrow down the memory area containing the search keyword to 172 mK in the area 24. Even if Elijah 24 is a 10 address, if m is 8, Elijah 25 is 10/25.
6, that is, the number is narrowed down to 400 addresses. per page, j
Even if the time is 710 msec, the search time is within 4 seconds.

Therefore, the content retrieval type bubble memory of the present invention adopts the data structure of the hash structure 25, adds a key code to each page, and transfers only the key code from the bubble memory to the high-speed semiconductor R, AM when the power is turned on.

During a search, the contents of the semiconductor RAM are sequentially read, and only the pages whose addresses match the key code compressed from the search keyword are output from the bubble memory. Among the output pages, only the pages that match the search keyword are output. be taken out to the outside.

FIG. 3 shows an embodiment of the invention. This is a content retrieval device configuration that employs the data structure of hash structure 25. The bubble memory device 300 in the figure includes a rotating magnetic field drive coil and a bias magnetic circuit as well as a bubble chip, but these are omitted. Such a bubble memory device [10] 300 is a rotating magnetic field drive circuit 311 and signal detection circuit 3.
12, a gate current pulse drive circuit 313, a generated current pulse drive circuit 314, and the like.

The memory device of the present invention stores a data block (corresponding to the page in FIG. 2) consisting of a set of records, a keyword, and an error correction code in the bubble memory device 300, and uses a search keyword given from the outside during a search operation. This is to read a data block having a matching keyword or a record therein. The data blocks are multiple minor loops 30 within the bubble memory device 300.
It is stored in the same storage location on 1. When used as a normal bubble memory, various drive timing signals generated by the address scan control section 330 and timing control section 320 are directly supplied to the peripheral circuit 310 to perform R, read/write operations of data blocks. When used as a content search memory, an error correction circuit (11) generates an error correction code for each keyword and record by inputting a keyword and record given from the outside at the time of registration, and uses this as a keyword. Configure data blocks (pages) for each record,
Supplied directly to peripheral circuit 310. This data block is stored in the bubble memory device 300 under the control of the timing controller 320.

After power is turned on, the address scan control unit 330 operates the timing control unit 320 and the address scan circuit 340, sequentially reads all data blocks in the bubble memory device 300, and reads the error correction code portion for each keyword in each data block. The data blocks are stored in the key code memory 350 in correspondence with the storage location of each data block within the bubble memory device 300. This error correction code corresponds to the key code 23 shown in FIG.

The key code memory 350 is composed of a normal random access memory and can be accessed much faster than the bubble memory device 300. Search behavior in bubble memory device during content search (12)
0, and the search key code 362 obtained as a result is sequentially compared with the contents of the high-speed key code memory 350 using a key code comparison circuit 364, and then an error matching the search key code 362 is detected. This is done by reading a data block having a correction code from the bubble memory device 300 via the timing control unit 320 and checking whether the keyword in the data block matches the search keyword 361 using the keyword comparison circuit 390. This search operation causes data blocks having keywords matching the search keyword to be retrieved into buffer memory 370.

To explain the search operation in more detail, the search keyword 361 given from the outside is sent to the error correction circuit 360.
and is temporarily stored in the search keyword memory 375. It is set in the key code register 363 as distinguished from the error correction circuit data, and the search key code 362
This becomes the input to the key code comparison circuit 364. In this state, the address scan control section 330 controls the timing control section 3 so that the error correction code regarding the data block on the minor loop 301 in contact with the gate 302 in the bubble memory device 300 is output from the key code memory 350.
20 and address scanning circuit 340. That is, the address scanning circuit 340 scans the addresses of the key code memory 350 in synchronization with the rotating magnetic field applied to the bubble memory device 300. As a result, the error correction code portion of each data block in bubble memory device 300 is sequentially read out from key code memory 350.

When the error correction code that matches the search key code 362 is read from the key code memory 350, the key code comparison circuit 364 immediately supplies the key code match signal 366 to the timing control section 340, and the gate in the bubble memory device 300 302 instructs a read operation of the approaching data block. Timing control section 340 is in contact with gate 302 . Timing control signals for reading data blocks are provided directly to peripheral circuitry 310.

The read data block from the bubble memory device 300 is directly sent to the error correction circuit 3 via the peripheral circuit 310.
60 is input. The error correction circuit 360 corrects the read error even if the keyword portion contains a read error, compares the keywords supplied to the keyword comparison circuit 390 via the data switch 380, and outputs the result as a matching signal 391 to the outside. Output to.

Only when matching signal 391 indicates a match, matching data block 365 output from bubble memory device 300 can be loaded into buffer memory 370 via error correction circuit 360. Therefore, it becomes possible to extract a desired code related to the search keyword 3611 from this buffer memory 370 to the outside.

Key code match signal 3 from key code comparison circuit 364
66 may also occur during a data block read operation, but the timing control unit 320 internally prohibits the key code match signal 366 during the read operation.

Address scanning control section 330 controls address scanning circuit 340 until all data blocks containing error correction codes in key code memory 350 that match search key code 362 are read.

Each data block stored in bubble memory device 300 includes a record, a keyword, and an error correction code. A bubble memory device (/stores a keyword in a minor loop 301 near the detector 303 in the space 300, and stores a keyword in a minor loop 301 near the generator 304).
The record is stored in 01. Since a keyword is composed of many words, the keyword comparison circuit 390
Furthermore, generation of the matching signal 391 to be outputted is delayed until reading of the keyword portion in the data block is completed. However, the (1G) keyword is detected by the detector 3 in the bubble memory device 300.
By storing the matching signal 391 in the minor loop 301 close to 03, the matching signal 391 can be outputted to the outside before the record is outputted to the outside. Furthermore, if it is sufficient to generate the match signal 391 before the last word of the record is output, the keyword comparison circuit 390 can be implemented using an inexpensive microprocessor, although the comparison takes time.

A microprocessor can also be commonly used in the address scan control section 330, further reducing the cost.

When such a device configuration is adopted, only data blocks having an error correction code matching the search key code are read out from the bubble memory device 300, and among them, only data blocks having a keyword matching the search keyword are taken out. . Therefore, the content search type bubble memory device according to the present invention has the bubble memory device 300.
In the conventional method, all data blocks within the data block are read and searched.

This enables significantly faster searches than with memory devices.

In addition, expensive associative memory (17
) -- resulting in a significant price reduction compared to other conventional content retrieval memory devices using elements. Furthermore, as explained in FIG. 3, the content retrieval type bubble memory device according to the present invention uses an error correction code as a key code, so that highly reliable retrieval processing can be achieved. Recent highly reliable general storage devices use error correction codes. Therefore, the error correction circuit can also be used as a special data compressor for generating the key code, and there is no need to provide a storage area for the key code in the bubble memory device 300 other than the error correction code. bring about a decline.

As described above, according to the present invention, by using a key code obtained by hashing a keyword,
To not only shorten search time, but also reduce semiconductor RAM capacity and keyword comparison time, and easily solve the conventional drawbacks.

Furthermore, no special hardware is required to generate the key code, resulting in further price reduction.

(18) In the above explanation, the key code data size is 8 bits and the number of keywords is about 4, but the cycle time of the key code memory 350 is sufficient compared to the drive cycle of the bubble memory device 300. Furthermore, the data size of the key code and the number of keywords can be easily increased.

[Brief explanation of the drawing]

Figures 1 (a) and (b) show the configuration of a general database, Figure 2 is a conceptual diagram of the data structure of the present invention, and Figure 3 is a content search type bubble memory device according to an embodiment of the present invention. FIG. 10...Magnetic disk, J5...Index table, 21...°...Keyword, 2
2...Address record, 23...Key code, 24...Basic configuration data structure 25.
-...Badge-configuration data structure. 27.28,29...Memory area. 300... Bubble memory device, 310...
... Direct peripheral circuit, 320 ... Timing control unit, 330 ... Address (19) Error correction circuit, 363 ... Key code register. 364...Key code comparison circuit, 370...
...Output data buffer, 375...-Keyword memory, 380...Data switch, 390...
...Keyword comparison circuit. (20) 71 Figure O 2 Figure 3 Figure 7・' :201 Koi = U・3°. 10 white white white day 20 40 66 330 364 350 361 shi

Claims (3)

[Claims] (1) A data compression means that compresses the amount of information of an externally given keyword to generate a key code, and a bubble chip that stores the externally given record, the keyword, and the key code in a data block. a bubble memory device including a key code memory that sequentially reads all the data blocks and sequentially stores the key code portions, and a key code memory that sequentially stores the addresses of the key code memory in synchronization with a rotating magnetic field applied to the bubble memory device. an address scanning means for scanning the address of the data block located in contact with the gate of the bubble memory zonometer, a key code comparing means for comparing the output of the key code memory, and a matching output of the key code comparing means; a timing control means for controlling reading, and a keyword comparison means for comparing a keyword portion in the data block read from the bubble memory device with the keyword given from the outside, and outputting the result to the outside as a matched output. A content search type bubble memory device comprising: (2) The data compression means is an error correction circuit. A content search type bubble memory device according to claim 1. (3) The content search type bubble memory device according to claim 1, wherein the keyword part in the data block is stored in a minor loop close to the detector in the bubble chip.