Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-12-18
2003-03-11
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C711S217000
Reexamination Certificate
active
06532468
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a data search method for reading a search object data one by one from a memory unit in which the search object data are specified and stored by address continuous in ascending order or descending order and an apparatus therefor. Specifically, in this search method and apparatus, processing for reading out a search object data from the memory unit and data comparison processing are optimized so that despite use of a memory having the same reading speed as a conventional one, as compared to a case in which the conventional binary search is used, entire processing time necessary for data search can be reduced.
2. Description of the Related Art
FIG. 1
shows a case that totally 2
n+1
search object data having n+1 search address are stored in a memory unit in which they are specified by address continuous in ascending order or descending order. Respective data are stored in the order of data number in the same figure and in the order of their value from small to large or from large to small. Referring to
FIG. 1
, processing in binary search in which these search object data are read out successively and compared with comparison data provided as a search key will be described.
In the binary search, usually a search address of the first time is “100000 . . . 0000” indicated by the sign A
1
in
FIG. 1
which is in the center of continuous address space. As a next search address, any one of “010000 . . . 000” or “110000 . . . 0000” is selected depending on a result of comparison between data specified by the first time search address and comparison data given as a search key.
In the binary search, the search address space is divided to two parts with an address in the center of the search address as a boundary and data specified by this boundary address, namely, the search address is compared with the comparison data. Further, one of the divided address space is selected depending on a result of the comparison and the selected address space is set to next search address space. After that, the same processing is repeated with the center address in the search address space as a boundary. In the binary search, the search address space is divided to two parts successively and an object data is searched.
The binary search has been well known as a retrieval method for a large amount of data because the retrieval time for N data is proportional to log N.
FIG. 2
shows a structure of a conventional binary search apparatus. Here, an address setting device
1
A is connected to a search object data storage unit
30
through an address bus
5
. A search data register
22
A of a data comparison unit
20
A is connected to the search object data storage unit
30
through a data bus
7
. The address setting device
10
A outputs a search address in succession. The search object data storage unit
30
outputs stored search object data to the search data register
22
A of the data comparison unit
20
A according to the search address. The data comparison unit
20
A compares this search object data in the search data register
22
A with comparison data for search preliminarily set in the comparison data register
24
A. A search of one time comprises a processing for reading the search object data from the search object data storage unit
30
according to the search address and a processing for comparing the read search object data with the comparison data as shown in FIG.
3
. These processings are carried out alternately and repeatedly. If both the data do not coincide with each other as a result of the comparison, a next search address is set according to which is larger. After that, these processings are repeated until the search object data coincides with the comparison data. Here, if it is assumed that the times for reading and comparison are the same and the time is Ct, an entire processing time can be expressed by a following expression (1).
T=
2
×Ct×log N
(1)
FIG. 4
shows the reading processing and comparison processing separately.
In the data comparison unit
20
A, the reading processing is not carried out as shown by a broken line of
FIG. 4
in a period of the processing for comparing data in the search data register
22
A with data in the comparison data register
24
A. On the other hand, the comparison processing is not carried out as shown by a broken line of the same Figure in a period of the processing for reading from the search object data storage unit
30
to the search data register
22
A according to the search address from the address setting device
10
A. As described above, the search object data storage unit
30
and data comparison unit
20
A are not actuated in a half period of the processing time required for the search. Further, the period in which they are not actuated occupies a large weight in the search processing time.
Further, as the other search method than the above described binary search method, multiple division search in which a search object area is divided to more than two can be considered. In this case, by carrying out comparisons on multiple data read from multiple divided regions at the same time, the time required for the search can be reduced. For example, the number of divisions is set to M=2
m
and totally M data are read one by one in succession from each region. Next, if the read M data are compared at the same time, a processing for a single search requires M+1 cycle. Therefore, the processing time Ta required until the search is completed can be expressed as follows.
T
a
=
(
M
+
1
)
×
C
t
×
log
N
/
m
=
(
M
+
1
)
/
m
×
C
t
×
log
N
(
2
)
If a ratio (R of a following expression) between the processing time T of the aforementioned binary search and processing time Ta for multiple division search is less than 1, it can be said that the processing time has been reduced.
R
=
T
a
/
T
=
(
M
+
1
)
/
m
×
C
t
×
log
N
/
2
×
C
t
×
log
N
=
(
M
+
1
)
/
m
/
2
(
3
)
Because the number of divisions is more than two in the expression (3) above, M≧4, m≧2. Therefore, R is 1.25 even if it is minimum, so that the multiple division search takes longer than the binary search. In the multiple division search described above, the number of comparison decreases as compared to the binary search and the frequency of data read increases, so that the entire processing time is extended.
SUMMARY OF THE INVENTION
Accordingly, the present invention has been achieved to solve the above problems and therefore, an object of the invention is to provide a data search method and an apparatus therefor capable of improving a processing speed and reducing an entire processing time required for data search as compared to a conventional binary search by optimizing a processing for reading search object data from a storage unit and a processing for data comparison even if a memory having the same reading speed as a conventional one is used.
Although the memory mentioned here refers to a general single port memory, it is not restricted thereto but a multi-port memory like a 2-port memory may be used. The single port memory refers to a general memory in which a pair of word line and bit line are provided for each memory cell of an incorporated memory cell matrix. The 2-port or multi-port memory refers to a specific memory in which by selecting two pairs or a plurality of the word lines at the same time, simultaneous access is enabled to different incorporated memory cells.
To achieve the above object, the present invention provides a binary search method in which search object data is stored in a storage unit according to continuous address in ascending order or descending order, the search object data is read out in succession and compared with comparison data given as a search key, the search object data being classified to data belonging to
Ishida Yoshihiro
Konishi Masahiro
Kawasaki Microelectronics Inc.
Le Uyen
Metjahic Safet
LandOfFree
Binary data search method for selecting from among candidate... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Binary data search method for selecting from among candidate..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Binary data search method for selecting from among candidate... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3001296