Data base retrieval system utilizing stored vicinity feature valves

• US 5,450,580 A
• Filed: 04/24/1992
• Issued: 09/12/1995
• Est. Priority Date: 04/25/1991
• Status: Expired due to Term

• Current Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Original Assignee: Nippon Steel Corporation
• Inventors: Takada, Hiroshi
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US07/873,130
• Time in Patent Office: 1,236 Days
• Field of Search: 395/600, 395/425, 395/3, 395/900, 395/934, 364/715.02
• US Class Current: 1/1
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/3341 using boolean model
• CPC Class Codes: Y10S 706/90 Fuzzy logic
• CPC Class Codes: Y10S 706/934 Information retrieval or Information management
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A data base retrieval system includes a memory for storing vicinity feature values of data records as search (or retrieval) objects of the data records. The vicinity feature values indicate a correspondence between data characters of the data records which are in the same vicinity. A searching device obtains matching degrees between a vicinity feature value of a search (or retrieval) key and the vicinity feature values of the search objects of the data records. Data record numbers are output arranged in a descending order of the matching degrees. Since phase information of data (position information indicating the position of a search key in a record) as a factor for prolonging the search time upon execution of full-record direct searching is abstracted by a vicinity feature value calculation, a high-speed and fuzzy searching operation can be performed so that the search time depends only on the length of the search key information, and does not depend on the volume of data.

Claims

1. A method for retrieving information from data records of a search object of a data base in response to an input search key, the method comprising the steps of:

storing vicinity feature values of the data records, said vicinity feature values indicating a correspondence between data characters of the data records;

obtaining matching degrees for the data records indicating a degree of correspondence between the stored vicinity feature values of the data records and a vicinity feature value of the search key, the vicinity feature value of the search key indicating a correspondence between data characters of the search key; and

providing as search results of the information retrieving method data record numbers and corresponding matching degrees for the data records.

2. A method according to claim 1, wherein said data record numbers and corresponding matching degrees are provided in a descending numerical order of said matching degrees.

3. A method according to claim 1, further comprising the step of extracting the vicinity feature values of the data records from the search object by a convolution calculation among data characters of the search object.

4. A method according to claim 1, further comprising the step of extracting the vicinity feature value of the search key by a convolution calculation among data characters of the search key.

5. A method according to claim 1, wherein the vicinity feature values of the data records are calculated in a similar manner as the vicinity feature value of the search key.

6. A method according to claim 1, wherein a quantization value x associated with a j-th data character C_i,j in an i-th data record of the search object, and a quantization value y associated with k data characters C_i,j+1, C_i,j+2, . . . C_i,j+k in the vicinity of the data character C_i,j are obtained by:

x=f (c_i,j)

y=g(C_i,j, C_i,j+1, C_i,j+2, . . . C_i,j+k)

wherein f(A) and g(B) are functions of A and B, respectively, wherein i,j and k are integers, and wherein a data record number i and a significance w(x,y,i) of the data record are stored for each data record as said vicinity feature values in a memory location defined by the obtained values x and y.

7. A method according to claim 6, wherein the significance w(x,y, i) is 1.

8. A method according to claim 6, wherein the quantization value x is expressed by one of n-stage values.

9. A method according to claim 1, wherein quantization values x=f(c_i) and y=g(c_i, c_i+j) are given to i-th data character c_i of a data sequence of the search object, and data c_i+j (j=1, 2, . . . ) in the vicinity of the data character c_i, the quantization values are used as element numbers of a matrix, one element value (=1) of two values (1, 0) is given to the element numbers, and a bit matrix generated for all i'"'"'s is used as the vicinity feature values.

10. A method according to claim 9, wherein the quantization values x=f(c_i) and y=g(c_i, c_i+j) are given to i-th data character c_i of a data sequence of the search object, and data c_i+j (j=1, 2, . . . ) in the vicinity of the data character c_i, an element value of the corresponding element number of the bit matrix is checked using the quantization values as the element numbers of the matrix, when the element value is 1, +1 is counted as the matching degree, and the matching degrees for all i'"'"'s are obtained in units of records.

11. A method according to claim 1, further comprising the step of converting data characters of the search object and the search key into integer data characters in which each data character is n-gradation data.

12. A method according to claim 11, wherein n=256.

13. A method according to claim 11, further comprising the steps of:

dividing said integer data characters by a predetermined value, said integer data characters being arranged in an ascending order of value;

comparing a new quotient obtained by said dividing means with a previously stored old quotient;

when the new quotient is larger than the old quotient, providing a difference between the new and old quotients and storing a remainder obtained by said dividing step together with the difference between the new and old quotients;

when the new quotient is not larger than the old quotient, storing only the remainder obtained by said dividing step; and

decoding original integer character data on the basis of the stored difference data and remainder data.

14. A method according to claim 13, further comprising the step of storing the difference between the new and old quotients together with a mark indicating a carry when the new quotient is larger than the old quotient.

15. A method according to claim 6, further comprising the steps of:

sequentially storing in a variable-length data memory means variable-length data corresponding to data records of said search object;

assigning identification numbers to the stored variable-length data;

storing in a storage location memory means the assigned identification numbers in correspondence with storage locations of the variable-length data stored in said variable-length memory means; and

when data is to be read from said variable-length memory means, reading the storage location of the data from said storage location memory means to access said variable-length data memory means.

16. A method according to claim 15, further comprising the step of temporarily storing data read from said variable-length data memory means.

17. A method according to claim 6, further comprising the steps of:

searching a data base using the search key to obtain matching degrees between the search key and each of the data records;

comparing the matching degrees obtained by the data base searching step for each of the data records with a predetermined threshold value;

preparing a list of data records which are determined by said comparing step to have matching degrees larger than the threshold value; and

storing as search results the list of data records prepared by said list preparing step.

18. A method according to claim 17, further comprising the step of sorting the data records in a descending numerical order of the matching degrees.

19. A method according to claim 6, further comprising the steps of:

performing full-record searching under predetermined conditions;

storing search results of said full-record searching step; and

performing conditional searching using the search results stored in said search result storing step.

20. A data base retrieval system for retrieving information from data records of a search object of a data base in response to an input search key, said system comprising:

first means for storing vicinity feature values of the data records, said vicinity feature values indicating a correspondence between data characters of the data records; and

second means for obtaining matching degrees for the data records indicating a degree of correspondence between the data record vicinity feature values stored in said first means and a vicinity feature value of the search key, said vicinity feature value of the search key indicating a correspondence between data characters of the search key, and for providing as search results of said data base retrieval system data record numbers and corresponding matching degrees for the data records.

21. A system according to claim 20, wherein said searching means provides said data record numbers and corresponding matching degrees in a descending numerical order of said matching degrees.

22. A system according to claim 20, further comprising means for extracting the vicinity feature values of the data records from the search object by a convolution calculation among data characters of the search object.

23. A system according to claim 20, further comprising means for extracting the vicinity feature value of the search key by a convolution calculation among data characters of the search key.

24. A system according to claim 20 wherein the vicinity feature values of the data records are calculated in a similar manner as the vicinity feature value of the search key.

25. A system according to claim 20, wherein a quantization value x associated With a j-th data character C_i,j in an i-th data record of the search object, and a quantization value y associated with k data characters C_i,j+1, C_i,j+2, C_i,j+k in the vicinity of the data character C_i,j are obtained by:

x=f(C_i,j)

Y=g(C_i,j, C_i,j+1, C_i,j+2, . . . C_i,j+k)

wherein f(A) and g(B) are functions of A and B, respectively, wherein i, j and k are integers, and wherein a data record number i and a significance w(x,y, i) of the data record are stored for each data record in said first means in a location defined by the obtained values x and y.

26. A system according to claim 25, wherein the significance w(x,y, i) is 1.

27. A system according to claim 25, Wherein the quantization value x is expressed by one of n-stage values.

28. A system according to claim 20, wherein quantization values x=f(c_i) and y=g(c_i, c_i+j) are given to i-th data character c_i of a data sequence of the search object, and data c_i+j (j=1, 2, . . . ) in the vicinity of the data character c_i, the quantization values are used as element numbers of a matrix, one element value (=1) of two values (1, 0) is given to the element numbers, and a bit matrix generated for all i'"'"'s is used as the vicinity feature values.

29. A system according to claim 28, wherein the quantization values x=f(c_i) and y=g(c_i, c_i+j) are given to i-th data character c_i of a data sequence of the search object, and data c_i+j (j=1, 2, . . . ) in the vicinity of the data character c_i, an element value of the corresponding element number of the bit matrix is checked using the quantization values as the element numbers of the matrix, when the element value is 1, +1 is counted as the matching degree, and the matching degrees for all i'"'"'s are obtained in units of records.

30. A system according to claim 20, further comprising means for converting data characters of the search object and the search key into integer data characters in which each data character is n-gradation data.

31. A system according to claim 30, wherein n=256.

32. A system according to claim 30, further comprising:

means for dividing said integer data characters by a predetermined value, said integer data characters being arranged in an ascending order of value;

means for comparing a new quotient obtained by said means for dividing with a previously stored old quotient, and when the new quotient is larger than the old quotient, providing a difference between the new and old quotients;

a compressed data memory, storing, when said means for comparing provides a difference between the new and old quotients, a remainder obtained by said means for dividing together with the difference between the new and old quotients, and storing, when said means for comparing does not provide a difference between the new and old quotients, only the remainder obtained by said means for dividing; and

a decoder decoding original integer character data on the basis of the difference data and the remainder data stored in said compressed data memory.

33. A system according to claim 32, wherein when the new quotient is larger than the old quotient, said means for comparing provides the difference between the new and old quotients together with a mark indicating a carry.

34. A system according to claim 25, further comprising:

means for sequentially storing variable-length data corresponding to data records of said search object;

means for assigning identification numbers to the variable-length data stored in said means for sequentially storing; and

means for storing storage locations of the variable-length data in said means for sequentially storing in correspondence with the identification numbers assigned by said means for assigning;

wherein when data is stored in said means for sequentially storing, the identification number and storage location of the data is stored said means for storing storage locations, and when data is to be read from said means for sequentially storing, the storage location of the data is read from said means for storing storage locations memory means to access said means for sequentially storing.

35. A system according to claim 34, further comprising means for temporarily storing data read from said means for sequentially storing.

36. A system according to claim 25, further comprising:

means for searching a data base using the search key to obtain matching degrees between the search key and each of the data records;

a comparator comparing the matching degrees obtained by the searching means of each of the data records with a predetermined threshold value;

means for preparing a list of data records which are determined by said Comparator to have matching degrees larger than the threshold value; and

means for storing as search results the list of data records prepared by said means for preparing a list.

37. A system according to claim 36, further comprising means for sorting the data records in a descending numerical order of the matching degrees.

38. A system according to claim 25, further comprising:

means for performing full-record searching under predetermined conditions;

search result memory storing search results of said means for performing full-record searching; and

means for performing conditional searching using the search results stored in said search result memory;

wherein said conditional search means of performing conditionally searching searches under conditions as a combination of the conditions used in the searching of said means for performing full-record searching, on the basis of the search results stored in said search result memory.

39. A system according to claim 38, further comprising means for inputting the conditions.