Data retrieval apparatus

Details Data retrieval apparatus Data retrieval apparatus

1999-03-25

2003-08-26

Nguyen, Hiep T. (Department: 2187)

Electrical computers and digital processing systems: memory

Addressing combined with specific memory configuration or...

For multiple memory modules

C711S157000, C711S168000, C711S217000, C711S219000, C707S793000

Reexamination Certificate

active

06611894

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates to a data retrieval apparatus for retrieving desired data from a number of data stored in a memory.
2. Description of Related Art
Conventionally, data retrieval apparatus are widely used.
FIG. 12
is a block diagram showing an example of a conventional data retrieval apparatus that includes a control circuit
10
and a memory
20
. The control circuit controls retrieval, register and deletion of data.
According to the data retrieval apparatus shown by
FIG. 12
, when a retrieval operation is carried out by a retrieval value KEY, the retrieval value KEY is provided as data and a retrieval start signal is transmitted. Further, when a register value INS is registered, the register value INS is provided as data and a register request signal is transmitted. Similarly, when a deletion value DEL is deleted, the deletion value DEL is provided as data and a deletion request signal is transmitted.
Although there are many methods for data retrieval, an explanation will be given for a data retrieval apparatus using a binary search method as follows.
Consider a series of data comprising a[0], a[1], a[2], . . . , a[n−1]. According to the binary search method, it is assumed that the series of data is ordered in an ascending order or a descending order If the ascending order is assumed, then:
a[
0]<
a[
1]<
a[
2]<. . . <
a[n−
1].
The binary search method searches for an element which is equal to the retrieval value KEY from the series of data. A range of retrieval is initially from a[0] to a[n−1] (the entire series of data). In general, the binary search method is a process of dividing the series of data in 2, selecting one portion of the series of data in which the retrieval value KEY is considered to exist, further dividing the selected portion of the series of data in 2 end so on. This process is repeated and a number of elements in the retrieval range is halved at each selection. The retrieval operation is finished when a number of elements in the retrieval range becomes 1, or the retrieval value KEY coincides with a certain element of the series of data.
FIG. 13
shows a flow chart of the binary search method;
FIG. 14
shows address transitions of a central element in the retrieval range; and
FIG. 15
shows a timing diagram of the retrieval operation. An explanation will be given by specifically pointing out the retrieval operation of the data retrieval apparatus in reference to FIG.
13
through
FIG. 15
as follows.
For example, if the series of data includes 15 elements, addresses of memory locations storing the series of data may be 0 through 14. Assume that the retrieval value is designated by notation KEY and data stored in the memory addresses 0 through 14 are respectively designated by notations MEM[0] through MEM[14]. An explanation will be given of an example of a case in which the data have the following relationships:
MEM[
0]<
MEM[
1]<
MEM[
2]< . . . <
MEM[
14];
and
MEM[
5]<
MEM[
6]<
MEM[
7],
where the retrieval value KEY coincides with data of memory address 6.
At step
1301
of
FIG. 13
, S=0, E=14. Here, notations S, E and M mentioned below are variables in executing the flow in which notation S designates a first address number in a retrieval range, notation E designates a final address number in the retrieval range and notation M designates an address number at a center of the retrieval range.
Next, at step
1302
, the central element in the range of MEM[0] to MEM[14] is generated as M=(S+B)/2=7. Accordingly, the center element becomes MEM[7]. Then, the central element MEM[7] is read from the memory
20
(cycle
1
of FIG.
15
).
At step
1303
, if a number of elements in the retrieval range is E−S+1=15 which does not equal to 1, the processing is shifted to step
1304
. At step
1304
, the retrieval value KEY is compared with the central element MEM[7] (cycle
2
of
FIG. 15
) to determine whether the retrieval value KEY is greater than, equal to or less than the central element MEM[7].
If the retrieval value KEY is less than MEM[7] (KEY<MEM[7]), then the retrieval value KEY (MEM[6]) is in a range less than the central element MEM[7] and the processing is shifted to step
1305
. At step
1305
, the value of E is set equal to the value of M which is 7. Thus, the retrieval range becomes a range of MEM[0] through MEM[7]. Then the processing returns to step
1302
.
At step
1302
, a next central element of the successive retrieval range is generated. The central element at this time becomes MEM[3] which is obtained by omitting numbers less than a decimal point from M=(S+E)/2=3.5 and MEM[3] is read from the memory
20
(cycle
3
of FIG.
15
). At step
1303
, the number of elements in the retrieval range is 8 which does not equal to 1 and accordingly, the operation proceeds to step
1304
. At step
1304
, the retrieval value is compared with the central element (cycle
4
of
FIG. 15
) and the operation proceeds to step
1306
since KEY>MEM[3]. In the processing at step
1306
, by setting S=M+1=4, the retrieval range is narrowed a range of MEM[4]through MEM[7].
Returning again to the step
1302
, the central element MEM[5] is generated. At step
1303
, the number of elements of the retrieval range is 4 which is not equal to 1, and accordingly, the operation proceeds to step
1304
. According to the comparison at this step, KEY>MEM[5], thus the operation proceeds to step
1306
and S=M+1=6 (cycles
5
,
6
of FIG.
15
).
Returning again to step
1302
, the central element is generated and MEM[6] is provided. At step
1303
, the number of elements of the retrieval range is 2, thus the operation proceeds to step
1304
and KEY=MEM[6] is found by the comparison. Accordingly, the retrieval operation is finished (cycles
7
,
8
of
FIG. 15
) and MEM[6] constitutes the retrieval result.
Next, an explanation will be given of operation of registering data.
FIG. 16
shows an outline of operation in registering a register value INS into a series of effective data of a[0] through a[11]. For this example, INS is larger than a[5] and smaller than a[6], that is, a [5]<INS<a[6].
The series of data must always be stored in memory in an ascending (or descending) order such that retrieval of data can be carried out. Therefore, in registering data, a position in memory where data is to be registered must be searched and a free memory location for the register data to be inserted must be obtained by shifting data already in the memory one by one and thereafter, the register data to be inserted must be written into the free memory location. Data registering operation is provided with the insertion operation described above when there is not an element which is equal to the register value in a series of data and is provided with an overwriting operation when there exists an element which is equal to the register value.
FIG. 17
shows a flow chart of the registering operation which includes both the insertion and overwriting operations.
FIG. 18
shows operational timings of the registering operation. An explanation will be given by pointing out a specific example of registering operation of data in reference to FIG.
17
and FIG.
18
.
Assume that there are 15 elements in the series of data. Thus, addresses of memory locations of the series of data may be designated by 0 through 14. Also assume that 12 elements of effective data are stored at addresses 0 through 11 is an order a

Affiliated with

Also associated with

Rating

Data retrieval apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data retrieval apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data retrieval apparatus will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3093783