Apparatus and method for retrieving vector format data from database in accordance with similarity with input vector

[0002] 1. Field of the Invention

[0003] The present invention relates to processing vector format data, and more particularly to a data processing apparatus and method for retrieving a predetermined number of data pieces from a database in accordance with a similarity with input vector.

[0004] 2. Related Background Art

[0005] A distance is widely used as a similarity between data expressed by vector. For example, in a character recognition system and a speech recognition system, sampled data is mapped in a feature quantity space spanned by a proper base to store vector-expressed data as a prototype. A distance between prototypes and newly input data is calculated to identify the input data as belonging to a class corresponding to the nearest prototype.

[0006] A calculation method having a worst efficiency is an exhaustive search. A calculation amount by this method is in the order of a product of the vector dimension and the number of prototypes.

[0007] The calculation amount of a distance or an inner product is recognized as a critical obstacle against database search. Because of recent rapid progress of a computer processing ability, a database can store not only text data but also non-text data such as images and sounds. In order to search such non-text data by using a keyword as in a conventional method, the non-text data is required to be added with a keyword in advance. If it is desired to avoid a work of adding a keyword, it is necessary to perform a similarity search by using feature quantity vector.

[0008] Even in searching text data, a similarity search algorithm is used which searches text data by using vector in order to realize flexible search. In this case, the calculation amount becomes a substantial issue in realizing a search system. The number of data pieces stored in a general database is over several hundred thousands. Therefore, as the order of a vector dimension is raised by one, the calculation amount increases desperately by several hundred thousands times.

[0009] In order to avoid such a case, it is essential to either lower the order of a vector dimension or reduce the number of data pieces to be calculated. The former corresponds to lowering the order of a vector dimension of a space which expresses data. Therefore, there is a possibility that information necessary for data search is not sufficiently expressed in vector components. The latter becomes meaningful methodology when the number of data pieces requested as search results is sufficiently small as compared with the total number of data pieces. Those cases to be processed by k-NN search belong to this category, and several effective methods have been proposed.

[0010] According to the k-NN search, k prototypes nearest to a test vector are searched from a set of prototypes stored in a system, and in accordance with classes of the searched prototypes, the class of the test vector is identified. In this case, one of important issues is how k prototypes nearest to the text vector are searched at high speed. This requirement is also applied to database search.

[0011] A search user desires only data pieces nearest to the search key designated by the user, among a large amount of data stored in a database, and does not desire other data pieces at all, much less values of distances and inner products. Techniques satisfying such requirements of a search user are coincident with objectives of a high speed algorithm of k-NN search.

[0012] In order to reduce the calculation amount required for searching k prototypes nearest to a test vector from a set of prototypes, each prototype is generally structurized in advance. The more the quality of data is reflected upon when structurization is performed, the more the search calculation amount is expected to be reduced.

[0013] For example, if a prototype is structurized hierarchically, an operation of dividing an N-dimensional space expressing a prototype is recursively repeated. A method of dividing the space by using a boundary which is a hyperplane is called a K-D-B Tree [Document 1], a method of dividing the space by a rectangular plane is called an R-Tree [Document 2], a method of dividing the space by a hyper-sphere is called an SS-Tree [Document 3], and a method of dividing the space by a combination of a rectangular plane and a hyper-sphere is called an SR-Tree [Document 4]. If an N-dimensional vector space is mapped to a space spanned by an eigenvector of a covariance matrix representing a prototype distribution, a structurization more effective for reducing a search calculation amount can be expected [Documents 5, 6].

[0014] With these methods, however, the calculation amount and storage capacity necessary for data structurization exponentially increases as the order of a vector dimension is raised. Therefore, application to those data expressed by high-dimensional vector may be practically restricted.

[0015] [Document 1] J T. Robinson: “The K-D-B Tree: A search Structure for Large Multidimensional Dynamic Indexes”, Proc. on ACM SIGMOD, pp. 10-18, 1981.

[0016] [Document 2] A. Guttman: “R-trees: A dynamic index structure for spatial searching”, Proc. ACM SIGMOD, Boston, USA, pp. 47-57, June 1984.

[0017] [Document 3] D A. White and R. Jain: “Similarity indexing with the SS-tree”, Proc. of the 12th Int. Conf. on Data Engineering, New Orleans, USA, pp. 323—331, February 1996.

[0018] [Document 4] Katayama and Satoh: “SR-Tree: A proposal of index structure for nearest neighbor searching of high dimensional point data”, IEICE Papers (D-I), vol. 18-D-I, no. 8, pp. 703-717, August 1997.

[0019] [Document 5] R F. Sproull: “Refinements to Nearest Neighbor Searching in K-dimensional Trees”, Algorithmica, 6, pp. 579-589, 1991.

[0020] [Document 6] D A. White and R. Jain: “Similarity Indexing: Algorithms and Performance”, Proc. on SPIE, pp. 62-73, 1996).

[0021] There are algorithms which use “gentle” structurization not incorporating statistical means and a little “smart” search algorithm, in order to reduce the calculation amount. Of these, one of the most fundamental algorithms is an algorithm by Friedman et al., called a mapping algorithm [Document 7].

[0022] [Document 7] J H. Friedman, F. Baskett, and L J. Shustek: “An Algorithm for Finding Nearest Neighbors”, IEEE Trans. on Computers, pp. 1000-1006, October 1975.

[0023] A data structurization requested as a pre-process of the mapping algorithm is a sorting process of sorting vector at each component, which process corresponds to structurization based upon a phase. Namely, if a prototype is d-dimensional vector, d sorting lists are generated.

[0024] With this process, two lists including a list V_jstoring j-component values arranged in the ascending order and a list I_jstoring corresponding prototype ID numbers, are formed as many as the order of a vector dimension. Namely, the value V_j(n+1) at the (n+1)-th component value from the start of V_jis equal to or larger than V_j(n) at the n-th component value. The j component value Y_Ij(n)(j) of the prototype Y_Ij(n)having the ID number of I_j(n) is coincident with V_j(n).

[0025] A principle of the mapping algorithm for selecting a pair of prototypes nearest to a test prototype from a prototype set will be described with reference to FIG. 10. A search is performed by using a pair of sorting lists V_mand I_mselected by a proper criterion. In the example shown in FIG. 10, an m-axis is selected. Im stores the ID number of data sorted based upon the component values, so that the order on the list correctly reflects the phase along the m-axis. First, a value nearest to the m component X(m) of a test vector X is searched from V_m. This value is assumed to be V_m(j). The prototype corresponding to V_m(j) is Y_Im(j). In the example shown in FIG. 10, Y_Im(j)corresponds to Y₁. Although Y₁is nearest to X with respect to the m component, it is not necessarily nearest to X in the whole space.

[0026] Next, a distance ρ(X, Y₁) between X and Y₁is calculated. It can be understood that there is a possibility that only a prototype having the m component value belonging to an open interval (X(m)−ρ(X, Y₁), X(m)+ρ(X, Y₁)) (area A in FIG. 10) is nearer to X than Y₁and that such a prototype is significant in terms of search target. In the example shown in FIG. 10, the next nearest prototype Y₂with respect to the m component is checked so that the prototype set to be searched is further restricted to (X(m)−ρ(X, Y₂), X(m)+ρ(X, Y₂)) (area B in FIG. 10). As above, with the mapping algorithm, the prototype set to be searched is made smaller in accordance with the component value in the one-dimensional space to thereby reduce the calculation amount.

[0027] It is reported, however, that the mapping algorithm by Friedman et al. lowers its performance as the order of a vector dimension becomes higher [Document 7]. A ratio of the expected number of prototypes whose distances were actually calculated to the total number of prototypes is herein called a relative efficiency η. For the case that one nearest neighbor is searched from a set of 1000 prototypes, η is 0.03 for two-dimensional vector, whereas η lowers to 0.6 for nine-dimensional vector.

[0028] By representing the number of prototypes picked up from a prototype set by N_EXTand the number of prototypes whose distances were calculated by N_g, the calculation amount required for deciding whether a distance calculation is to be performed is O(N_EXT), and the calculation amount for actual distance calculation is O(dN_g). As Ng becomes near to the value of N_EXT, a process overhead is added so that an actual calculation time for nine-dimensional vector may become worse than the exhaustive search. In order to solve this problem that the mapping algorithm cannot be used for high-dimensional vector, Nene et al. have devised a very simple and effective algorithm [Document 8]. This algorithm called “Searching by Slicing” leaves as a search candidate only the prototype belonging to a closed interval [X(j)−ε, (X(j)+ε] spaced before and after the j-th component X(j) of test vector by an amount of ε, as a search candidate. Since this algorithm independently evaluates each component, it is apparent that the performance is dependent upon ε. Although Nene et al. have proposed a method of deciding a value ε, this method is probabilistic and not suitable for high-dimensional vector.

[0029] [Document 8] S A. Nene and S K. Nayar: “A Simple Algorithm for Nearest Neighbor Search in High Dimensions”, IEEE Trans. on PAMI, vol. 19, no. 9, pp. 989-1003, September 1997.

[0030] It is an object of the present invention to provide a data processing apparatus and method capable of retrieving data relevant to input data from a database having a large amount of data, at high speed.

[0031] According to one aspect, the present invention which achieves the object relates to a data processing apparatus comprising: a database storing a set of data of a vector format; list forming means for forming a list of data of the database arranged in an order of a value of each component of a vector, for each component; input means for inputting test data of a vector format; component selecting means for sequentially selecting each component of the vector format; data selecting means for sequentially selecting data in an ascending order of a difference value between the data and the test data from the list, for each component of the vector format; distance calculating means for calculating a distance in a whole space between the data selected by the data selecting means and the test data; retrieving means for retrieving a predetermined number of data pieces in an ascending order of a distance calculated by the distance calculating means; completion judging means for judging, from a difference of a component value between one data piece selected by the data selecting means and the test data, whether data selection by the data selecting means is to be continued or terminated; and distance calculating control means for controlling whether the distance calculating means is to calculate a distance in the whole space, in accordance with a distance in a partial space between the data selected by the data selecting means and the test data.

[0032] According to another aspect, the present invention which achieves the object relates to a data processing apparatus comprising: a database storing a set of data of a vector format; pre-processing means for calculating a square of a norm of each data piece in the database and forming a list of data arranged in an order of a value of each component of the vector, for each component; input means for inputting test data of the vector format and operating a metric tensor upon the test data; component selecting means for sequentially selecting each component of the vector format; data selecting means for sequentially selecting data in an ascending order of a difference value between the data and the test data from the list, for each component of the vector format; similarity calculating means for calculating a similarity in a whole space between the data selected by the data selecting means and the test data by using a square of a norm of the data; retrieving means for retrieving a predetermined number of data pieces in a descending order of the similarity calculated by the similarity calculating means; and similarity calculating control means for controlling whether the similarity calculating means is to calculate a similarity in the whole space, in accordance with a similarity in a partial space between the data selected by the data selecting means and the test data.

[0033] According to another aspect, the present invention which achieves the object relates to a data processing method comprising: a list forming step of forming a list of data in a database storing a set of data of a vector format, for each component of a vector, the data in the list being arranged in an order of a value of each component; an input step of inputting test data of a vector format; a component selecting step of sequentially selecting each component of the vector format; a data selecting step of sequentially selecting data in an ascending order of a difference value between the data and the test data from the list, for each component of the vector format; a distance calculating step of calculating a distance in a whole space between the data selected at the data selecting step and the test data; a retrieving step of retrieving a predetermined number of data pieces in an ascending order of a distance calculated at the distance calculating step; a completion judging step of judging, from a difference of a component value between one data piece selected at the data selecting step and the test data, whether data selection at the data selecting step is to be continued or terminated; and a distance calculating control step of controlling whether the distance calculating step is to calculate a distance in the whole space, in accordance with a distance in a partial space between the data selected at the data selecting step and the test data.

[0034] According to another aspect, the present invention which achieves the object relates to a data processing method comprising: a pre-processing step of calculating a square of a norm of each data piece in a database storing a set of data of a vector format and forming a list of data arranged in an order of a value of each component of the vector, for each component; an input step of inputting test data of the vector format and operating a metric tensor upon the test data; a component selecting step of sequentially selecting each component of the vector format; a data selecting step of sequentially selecting data in an ascending order of a difference value between the data and the test data from the list, for each component of the vector format; a similarity calculating step of calculating a similarity in a whole space between the data selected at the data selecting step and the test data by using a square of a norm of the data; a retrieving step of retrieving a predetermined number of data pieces in a descending order of the similarity calculated at the similarity calculating step; and a similarity calculating control step of controlling whether the similarity calculating step is to calculate a similarity in the whole space, in accordance with a similarity in a partial space between the data selected at the data selecting step and the test data.

[0035] According to a further aspect, the present invention which achieves the object relates to a computer-readable storage medium storing a program for controlling a computer to perform data processing, the program comprising codes for causing the computer to perform; a list forming step of forming a list of data in a database storing a set of data of a vector format, for each component of a vector, the data in the list being arranged in an order of a value of each component; an input step of inputting test data of a vector format; a component selecting step of sequentially selecting each component of the vector format; a data selecting step of sequentially selecting data in an ascending order of a difference value between the data and the test data from the list, for each component of the vector format; a distance calculating step of calculating a distance in a whole space between the data selected at the data selecting step and the test data; a retrieving step of retrieving a predetermined number of data pieces in an ascending order of a distance calculated at the distance calculating step; a completion judging step of judging, from a difference of a component value between one data piece selected at the data selecting step and the test data, whether data selection at the data selecting step is to be continued or terminated; and a distance calculating control step of controlling whether the distance calculating step is to calculate a distance in the whole space, in accordance with a distance in a partial space between the data selected at the data selecting step and the test data.

[0036] According to a further aspect, the present invention which achieves the object relates to a computer-readable storage medium storing a program for controlling a computer to perform data processing, the program comprising codes for causing the computer to perform: a pre-processing step of calculating a square of a norm of each data piece in a database storing a set of data of a vector format and forming a list of data arranged in an order of a value of each component of the vector, for each component; an input step of inputting test data of the vector format and operating a metric tensor upon the test data; a component selecting step of sequentially selecting each component of the vector format; a data selecting step of sequentially selecting data in an ascending order of a difference value between the data and the test data from the list, for each component of the vector format; a similarity calculating step of calculating a similarity in a whole space between the data selected at the data selecting step and the test data by using a square of a norm of the data; a retrieving step of retrieving a predetermined number of data pieces in a descending order of the similarity calculated at the similarity calculating step; and a similarity calculating control step of controlling whether the similarity calculating step is to calculate a similarity in the whole space, in accordance with a similarity in a partial space between the data selected at the data selecting step and the test data.

[0037] Other objectives and advantages besides those discussed above shall be apparent to those skilled in the art from the description of preferred embodiments of the invention which follows. In the description, reference is made to accompanying drawings, which form a part thereof, and which illustrate an example of the invention. Such example, however, is not exhaustive of the various embodiments of the invention, and therefore reference is made to the claims which follow the description for determining the scope of the invention.

[0038] FIG. 1 is a functional diagram of a data processing apparatus according to a first embodiment.

[0039] FIG. 2 is a flow chart illustrating a process sequence to be executed by a distance calculation unit.

[0040] FIG. 3 is a flow chart illustrating a search process sequence.

[0041] FIG. 4 is a flow chart illustrating an initialization process sequence for a pointer.

[0042] FIG. 5 is a flow chart illustrating an initialization process sequence for a neighbor set.

[0043] FIG. 6 is a flow chart illustrating an update process sequence for a pointer.

[0044] FIG. 7 is a flow chart illustrating a process sequence of distance calculation.

[0045] FIG. 8 is a flow chart illustrating a pre-process sequence.

[0046] FIG. 9 is a graph showing the results of computer calculation experiments according to the first embodiment.

[0047] FIG. 10 is a diagram illustrating a principle of a mapping algorithm.

[0048] FIG. 11 is a functional diagram of a data processing apparatus according to a second embodiment.

[0049] FIG. 12 is a flow chart illustrating a search process sequence.

[0050] FIG. 13 is a flow chart illustrating an initialization process sequence for a neighbor set.

[0051] FIG. 14 is a flow chart illustrating a function calculation process sequence.

[0052] FIG. 15 is a graph showing the results of computer calculation experiments according to the second embodiment.

[0053] Preferred embodiments of the invention will be detailed with reference to the accompanying drawings.

[0054] [First Embodiment]

[0055] A high speed algorithm of this embodiment is a mapping algorithm extended to high-dimensional vector in a natural way. This algorithm of the embodiment is a generalized algorithm which does not require “hard” structurization of a prototype set and parameters to be set in advance.

[0056] The algorithm by Friedman et al uses a square of a norm of a difference vector mapped to a one-dimensional partial space in order to decide whether the distance between an extracted prototype and a test prototype is to be calculated.

[0057] The algorithm proposed in this embodiment adaptatively raises the order of a vector dimension of a partial space until the prototype to be searched satisfies some conditions. Namely, if a square of a norm of a difference vector between a text vector and a prototype mapped to an m-dimensional partial space is smaller than a square of a radius ξ of a set of k neighbors already obtained, a difference vector in a (m+1)-dimensional partial space is calculated and compared with ξ². This process is repeated until the dimension of the partial space becomes coincident with a preset value.

[0058] In order to verify the validity of the embodiment algorithm, experiments were conducted by using a set of prototypes generated by a computer by using uniform random numbers. It was confirmed that the calculation amount was able to be reduced even if the order of a vector dimension was raised.

[0059] Prior to describing the details of the embodiment algorithm, a subject of study and the definitions of words and symbols will be clarified.

[0060] The subject of study is to extract k prototypes from Ω which prototypes have a metric ρ (X, Y_j) nearest to an arbitrarily given test vector X ε R^d, where Ω is a set of N prototypes Y_jexpressed as a d-dimensional vector:

[0061] Ω={Y₁, Y₂, . . . , Y_n}, Y_jεR^d

[0062] A Euclidean distance is defined by a squared norm of a difference vector so that a space is assumed to be formed by spanning vector data by an orthogonal base: $\begin{array}{cc}\rho \left(X,Y\right)=\Vert X-Y\Vert =(\sum _{j=1}^{j=d}{\left(X\left(j\right)-{Y\left(j\right)}^2\right)}^{1/2}& \left(1\right)\end{array}$

[0063] where k component values of the test vector X and prototype vector Y_jare represented by X(k) and Y_j(k), respectively.

[0064] FIG. 1 is a functional diagram of a data processing apparatus of the first embodiment. An input/output unit 101 has an input unit such as a reception apparatus and a keyboard and an output unit such as a transmission apparatus and a display.

[0065] For example, in the case of a stand-alone computer, the input/output unit 101 is constituted of a keyboard and a display. Data input from the keyboard is transferred to a distance calculation unit 102, and data supplied from the distance calculation unit 102 is displayed on the display.

[0066] Alternatively, in the case of a communications terminal equipment connected to a communications line, the input/output unit 101 is constituted of a communications control apparatus for data transmission/reception. Data input via the communications line is transferred to the distance calculation unit 102, and data supplied from the distance calculation unit 102 is transmitted via the communications line to another terminal at a designated address.

[0067] The distance calculation unit 102 is realized by a CPU which executes each function program (corresponding to a process sequence shown in each of flow charts to be described later) stored in a ROM, a disk memory or the like, and has other memories such as a RAM for storing calculation results and various data generated during each process sequence.

[0068] A database 103 stores a set of N prototypes expressed by d-dimensional vector, and is accessed by the distance calculation unit 102.

[0069] The process to be executed by the distance calculation unit 102 will be described with reference to the flow chart shown in FIG. 2.

[0070] At Step S201 it is checked whether any data is input from the input/output unit 101. If not, the flow stands by at Step S201, whereas if data is input, the flow advances to Step S202. At Step S202 it is checked whether the input data indicates that data in the database 103 is to be updated. If not, the flow advances to Step S203, whereas if data is to be updated, the flow advances to Step S204. At Step S203 a pre-process to be described later is executed to thereafter return to Step S201. At Step S204 it is checked whether the input data indicates a calculation process. If a calculation process, the flow advances to Step S205, whereas if not, the flow returns to Step S201. At Step S205, a search process to be described later is executed to thereafter return to Step S201.

[0071] The pre-process to be executed at Step S203 will be described with reference to the flow chart shown in FIG. 8.

[0072] In this pre-process, sorting lists are formed with respect to each component value of a prototype set. In this process, two lists including a list V_jstoring j-component values arranged in the ascending order and a list I_jstoring corresponding prototype ID numbers, are formed as many as the order of a vector dimension. At Step S801 “1” is set to n. At Step S802 a pair of an n-th component value and its ID number is formed for each of N prototypes, namely:

[0073] {(Y₁(n), 1), (Y₂(n), 2), . . . , (Y_N(n), N)}

[0074] At Step S803, a set of pairs is rearranged in the ascending order of n component values:

[0075] {(Y_In(1)(n), In(1)), (Y_In(2)(n), In(2)), . . . , (Y_In(N)(n), In(N))}

[0076] In the following, the order of component values is represented by a list V and the order of ID numbers is represented by a list I:

[0077] Vn={Y_In(1)(n), Y_In(2)(n), . . . , Y_In(N)(n)}  (2)

[0078] In={In(1), In(2), . . . , In(N)}  (3)

[0079] At Step S804 the value n is incremented by “1”. If the incremented value n is larger than the order d of a vector dimension, the process is terminated, whereas if not, the flow advances to Step S802.

[0080] The relation between the two lists is as follows. Namely, the value V_j(n+1) at the (n+1)-th component value from the start of V_jis equal to or larger than V_j(n) at the n-th component value. The j component value V_Ij(n)(j) of the prototype Y_Ij(n)having the ID number of I_j(n) is coincident with V_j(n).

[0081] Next, the search process to be executed at Step S205 will be described with reference to the flow chart of FIG. 3.

[0082] Given as the input for the search process are a vector X (hereinafter called a test vector) to be searched and the number k of prototypes requested as the search results.

[0083] At Step S301 an index list is formed which stores bases of a vector space. This list decides the order of bases which are applied to an end condition and a rejection condition to be described later. For example, this list is formed in correspondence with a descending order of an absolute value of a component value of the test vector X:

[0084] ={λ₁, λ₂, . . . ,λ_d}  (4)

[0085] A set of L bases from the smallest is written as:

[0086] ={λ_d−L+1, λ_d−L+2, . . . , λ_d}  (5)

[0087] At Step S302 an initialization process for PTR and related variables is executed. This process will be described with reference to the flow chart shown in FIG. 4.

[0088] At Step S401 λ1 is set to m. At Step S402 a sorting list V_mfor the m component values is acquired. At Step S403 the value nearest to the m component value X(m) of the test vector is searched from V_m, and the position of the value is stored in PTR, namely:

[0089] |V_m(PTR)−X(m)|≦|V_m(j)−X(m)|, ∀_jε{1, 2, . . . , N}

[0090] The related variables are initialized as follows:

[0091] PTR_L=PTR−1, BND_L=0, CAL_L=0

[0092] PTR_H=PTR+1, BND_H=0, CAL_H=0

[0093] At Step S303 a set of k neighbors is initialized. This process will be described with reference to the flow chart shown in FIG. 5.

[0094] At Step S501, the neighbor set N₀(X) is initialized to an empty set. At Step S502 “1” is set to t. At Step S503 PTR is updated, this process being later described with reference to the flow chart shown in FIG. 6. At Step S504 a square ρ(x, Y_Im(PTR))²of a distance between the test vector X and the prototype Y_Im(PTR)having the ID number I_m(PTR) is calculated: ${\rho \left(X,Y_{\mathrm{Im}\left(\mathrm{PTR}\right)}\right)}^2={\Vert X-Y_{\mathrm{Im}\left(\mathrm{PTR}\right)}\Vert }^2=(\sum _{j=1}^{j=d}{\left(X\left(j\right)-Y_{\mathrm{Im}\left(\mathrm{PTR}\right)}\left(j\right)\right)}^2$

[0095] At Step S505 the prototype ID and the square of the distance are added to the neighbor set N_t−1(X):

[0096] N_t(X)=N_t−1(X)+{(I_m(PTR), ρ(X, Y_Im(PTR))²)}

[0097] At Step S506 t is incremented by “1”. If t is larger than k, the flow advances to Step S507, whereas if not, the flow returns to Step S503.

[0098] At Step S507 the maximum value of ρ(X, Y_Im(PTR))²and corresponding ID number in the neighbor set are stored as ξ_t−1and I_MAX,t−1, respectively.

[0099] At Step S304 k is set to t. At Step S305 an update process for PTR is executed. This process will be described with reference to the flow chart shown in FIG. 6.

[0100] At Step S601 it is checked whether PTR_Lis smaller than 1. If smaller, the flow advances to Step S602, whereas if not, the flow advances to Step S603. At Step S602 the following process is executed:

[0101] BND_L=1, DX_L=∞

[0102] At Step S603 it is checked whether PTR_His larger than N. If larger, the flow advances to Step S604, whereas if not, the flow advances to Step S605. At Step S604 the following process is executed:

[0103] BND_H=1, Dx_H=∞

[0104] At Step S605 it is checked whether a product of BND_Land CAL_Lis “1”. If “1”, the search process is terminated, whereas if not, the flow advances to Step S606. At Step S606 it is checked if BND_L+CAL_Lis “1”. If “1”, the flow advances to Step S607, whereas if not, the flow advances to Step S607. At Step S607 the following process is executed:

[0105] DX_L=(V_m(PTR_L)−X(m))²

[0106] CAL_L=1

[0107] At Step S608 it is checked whether BND_H+CAL_His “1”. If “1”, the flow advances to Step S609, whereas if not, the flow advances to Step S610. At Step S609 the following process is executed:

[0108] DX_H=(V_m(PTR_H)−X(m))²

[0109] CAL_H=1

[0110] If DX_Lis smaller than DX_Hat Step S610, the flow advances to Step S611, whereas if not, the flow advances to Step S612.

[0111] At Step S611 the following process is executed to thereafter return to Step S306 of the search process shown in FIG. 3:

[0112] Dx=Dx_L, PTR=PTR_L, CAL_L=0

[0113] At Step S612 the following process is executed to thereafter return to Step S306 of the search process shown in FIG. 3:

[0114] Dx=Dx_H, PTR=PTR_H, CAL_H=0

[0115] In the update process for PTR, PTR and related variables are changed and if the end condition is satisfied, the search process shown in FIG. 3 is terminated. At Step S306 it is checked whether the end condition of the following formula is satisfied. If satisfied, the search process is terminated, whereas if not, the flow advances to Step S307.

[0116] Dx ≧ξ_t−1  (8)

[0117] At Steps S307 to S309 it is checked whether the rejection condition is satisfied. At Step S307 “2” is set to m.

[0118] At Step S308, the following process is executed:

[0119] n=I_m(PTR)

[0120] j=λ_m

[0121] Dx←Dx+(Y_n(j)−X(j))²

[0122] The obtained Dx is a square of the distance of Yn in the m-dimensional partial space.

[0123] It is checked whether the following formula is satisfied. If satisfied, the flow advances to Step S311, whereas if not, the flow advances to Step S308.

[0124] Dx≧ξ_t−1  (9)

[0125] At Step S309 m is incremented by “1”. If the incremented m is larger than g, the flow advances to Sep S310, whereas if not, the flow advances to Step S308.

[0126] At Step S310 a distance calculation process to be described later with reference to the flow chart of FIG. 7 is executed to thereafter advance to Step S311.

[0127] At Step S311 t is incremented by “1”. If the incremented t is larger than N, the search process is terminated, whereas if not, the flow returns to Step S305.

[0128] The distance calculation process at Step S310 will be described with reference to the flow chart of FIG. 7.

[0129] At Step S701 (g+1) is set to j. At Step S702 λ_jis set to s.

[0130] At Step S703 the following process is executed:

[0131] Dx←Dx+(Y_n(s)−X(s))²

[0132] where n=I_m(PTR).

[0133] At Step S704 j is incremented by “1”. If the incremented j is larger than the order d of the vector dimension, the flow advances to Step S705, whereas if not, the flow returns to Step S702. At Step S705 it is checked whether Dx is smaller than ξ_t−1.If smaller, the flow advances to Step S706, whereas if not, the distance calculation process is terminated.

[0134] At Steps S706 and S707 the neighbor set is updated. At Step S706 a pair of the ID number and a squared distance corresponding to ξ_t−1is deleted from the neighbor set:

[0135] N_t(X)←N_t−1(X)−{(I_{MAX, t−1}, ξ_t−1)}

[0136] At Step S707 the following process is executed to thereafter return to Step S310 shown in FIG. 3:

[0137] N_t(X)←N_t−1(X)+{(I_m(PTR), Dx)}

[0138] N_t(X) after the termination at Step S305, Step S306 or S310 is output as the search result.

[0139] The effect of the embodiment described above was verified by experiments through computer calculations.

[0140] [Computer Experiments]

[0141] In order to verify the validity of the embodiment, computer experiments were made for the number k=10 of prototypes requested as the search results and for the number N=1000, 10000 of prototypes in each set. The following item was used as the experiment parameters:

[0142] the order of a vector dimension: d={10, 20, 30, 40, 50, 60, 70, 80, 90, 100}

[0143] The following values were checked by the experiments:

[0144] a change in the calculation amount with raising the order of a vector dimension; and

[0145] a change in the calculation amount with the number N of prototypes.

[0146] The computer used by the experiments is as follows:

[0147] Silicon Graphics Co. 02

[0148] CPU: MIPS R10000, Rev 2.6 (174 MHz)

[0149] Main memory: 128 MB

[0150] OS: IRIX Release 6.3

[0151] The C programming language was used.

[0152] [Experiment Steps]

[0153] (1) A set of N prototypes of d-dimensional vector was generated by using uniform random numbers.

[0154] (2) One test vector of d-dimensional vector was generated by using uniform random numbers.

[0155] (3) An exhaustive search was conducted.

[0156] (4) A search was conducted by using the embodiment algorithm.

[0157] These four steps were repeated 100 times and an average of relative CPU times was calculated. The relative CPU time is (CPU time using the embodiment algorithm) divided by (CPU time using the exhaustive search).

[0158] Since the performance improvement for a raised order of a vector dimension was confirmed by a relatively small set of a relatively lower vector dimension, the performance of the k-NN search was testified for a larger set of prototypes of a higher vector dimension.

[0159] The experiment results are shown in the graph of FIG. 9. In this graph, the abscissa represents a vector dimensionality and the ordinate represents a relative CPU time (CPU time ratio) η_T. The prototype number N was used as a parameter.

[0160] It is seen from FIG. 9 that as the order of a vector dimension is raised, the relative CPU time ratio increases in linear order independently from the prototype number N. A slope at N=10000 is very small. The relative CPU time ratio at N=10000 is very small as 1% for ten-dimensional vector and 7% even for 90-dimensional vector. The search process of searching ten nearest prototypes from 10000 prototypes of 90-dimensional vector took 3.7 sec for an exhaustive search as compared to 0.26 sec for the embodiment algorithm.

[0161] [Second Embodiment]

[0162] In this embodiment, an equation representing a relation between an inner product and a distance is derived and the mapping algorithm is used as an inner product high speed calculation method. This algorithm of the embodiment is a generalized algorithm which does not require “hard” structurization of a prototype set and parameters to be set in advance.

[0163] Prior to describing the details of the embodiment algorithm, a subject of study and the definitions of words and symbols will be clarified.

[0164] The subject of study is to extract k prototypes from Ω which prototypes have a metric ρ_G(X, Y_j) nearest to an arbitrarily given test vector X ε R^d, where Ω is a set of N prototypes Y_jexpressed as a d-dimensional vector:

[0165] Ω={Y₁, Y₂, . . . Y_N}, Y_jεR^d

[0166] The metric ρ_G(X, Y_j) is defined as an inner product so that a space is assumed to be formed by spanning vector data by an orthogonal base: $\begin{array}{cc}{\rho }_G\left(X,Y\right)=X^T\mathrm{GY}=\sum _{n=1}^{n=d}\sum _{m=1}^{m=d}G\left(m,n\right)X\left(m\right)Y_j\left(n\right)& \left(1\right)\end{array}$

[0167] where k component values of the test vector X and prototype vector Y_jare represented by X(k) and Y_j(k), respectively.

[0168] A first feature of this embodiment is a function δ(Z, Y_j) is incorporated as a function of giving the same phase as the metric ρ_G(X, Y_j). ρ_G(X, Y_j) can be divided by the following two-step processes:

[0169] Z=GX

[0170] ρ_G(X, Y)=X^TGY=(GX)^TY=Z^TY=ρ(Z, Y_j)

[0171] where ρ(Z, Y_j) is an inner product in a normalized orthogonal system.

[0172] The following equation is obtained by developing a square of the distance between Z and Y_j:

[0173] ∥Z−Y_j∥²=(Z−Y_j)^T(Z−Y_j)=∥Z∥²+∥Y_j∥²−2ρ(Z, Y_j)

[0174] This equation is arranged to obtain the following equation:

[0175] 2ρ(Z, Y_j)−∥Z∥²=∥Y_jμ²−∥Z−Y_j∥²

[0176] The right (or left) side of this equation is defined as a new function δ(Z, Y_j):

[0177] δ(Z, Y_j)=∥Y_j∥²−∥Z−Y_j∥²

[0178] FIG. 11 is a functional diagram of a data processing apparatus of the second embodiment. An input/output unit 1101 has an input unit such as a reception apparatus and a keyboard and an output unit such as a transmission apparatus and a display.

[0179] For example, in the case of a stand-alone computer, the input/output unit 1101 is constituted of a keyboard and a display. Data input from the keyboard is transferred to an inner product calculation unit 1102, and data supplied from the inner product calculation unit 1102 is displayed on the display.

[0180] Alternatively, in the case of a communications terminal equipment connected to a communications line, the input/output unit 1101 is constituted of a communications control apparatus for data transmission/reception. Data input via the communications line is transferred to the inner product calculation unit 1102, and data supplied from the inner product calculation unit 1102 is transmitted via the communications line to another terminal at a designated address.

[0181] The inner product calculation unit 1102 is realized by a CPU which executes each function program (corresponding to a process sequence shown in each of flow charts to be described later) stored in a ROM, a disk memory or the like, and has other memories such as a RAM for storing calculation results and various data generated during each process sequence.

[0182] A database 1103 stores a set of N prototypes expressed by d-dimensional vector, and is accessed by the inner product calculation unit 1102.

[0183] The process to be executed by the inner product calculation unit 1102 is approximately similar to that shown in FIG. 2 to be executed by the distance calculation unit 102 of the first embodiment. In this embodiment, in place of the input/output unit 101 and database 103, the input/output unit 1101 and database 1103 are used.

[0184] The pre-process to be executed at Step S203 will be described. In this pre-process, sorting lists are formed with respect to a squared norm and reach component value of a prototype in a prototype set. The former squared norm ∥Y_j∥²is calculated and stored. The latter component value is generated in a manner similar to the first embodiment described with reference to FIG. 8.

[0185] Next, the search process to be executed at Step S205 will be described with reference to the flow chart of FIG. 12.

[0186] Given as the input for the search process are a vector X (hereinafter called a test vector) to be searched, a metric tensor G and the number k of prototypes requested as the search results.

[0187] At Step S1201 the test vector X is multiplied by the metric tensor G at the left side to obtain a vector X:

[0188] Z=GX

[0189] At Step S1202 an index list is formed which stores bases of a vector space. This list decides the order of bases which are applied to an end condition and a rejection condition to be described later. For example, this list is formed in correspondence with a descending order of an absolute value of a component value of the test vector X:

[0190] ={λ₁, λ₂, . . . , λ_d}  (4)

[0191] A set of L bases from the smallest is written as:

[0192] ={λ_d−L+1, λ_d−L+2, . . . , λ_d}  (5)

[0193] At Step S1203 an initialization process for PTR and related variables is executed. This process is executed in a similar manner to the first embodiment shown in FIG. 4.

[0194] At Step S1204 a set of k neighbors is initialized. This process will be described with reference to the flow chart shown in FIG. 13.

[0195] At Step S1301, the neighbor set N₀(X) is initialized to an empty set. At Step S1302 “1” is set to t. At Step S1303 PTR is updated, this process being executed in a similar manner to the first embodiment shown in FIG. 6. At Step S1304 a function Δ_sand the prototype Y_Im(PTR)having the ID number I_m(PTR) are calculated:

[0196] s=I_m(PTR)

[0197] Δ_s=∥Y_s∥²−∥Z−Y_s∥²

[0198] Since the first term of the right side of this equation was calculated by the pre-process, only a read operation from a memory is performed.

[0199] At Step S1305 the prototype ID and the value Δ_sare added to the neighbor set N_t−1(X):

[0200] N_t(X)=N_t−1(X)+{(s, Δ_s)}

[0201] At Step S1306 t is incremented by “1”. If t is larger than k, the flow advances to Step S1307, whereas if not, the flow returns to Step S1303.

[0202] At Step S1307 the minimum value Δ_sand corresponding ID number in the neighbor set are stored as ξ_t−1and τ_t−1, respectively.

[0203] Reverting to FIG. 12, at Step S1205 k is set to t. At Step S1206 an update process for PTR is executed. This process is performed in a similar manner to the first embodiment shown in FIG. 6. Equations to be used for calculations are, however, partially different from the first embodiment.

[0204] At Step S601 it is checked whether PTR_Lis smaller than 1. If smaller, the flow advances to Step S602, whereas if not, the flow advances to Step S603. At Step S602 the following process is executed:

[0205] BND_L=1, DX_L=∞

[0206] At Step S603 it is checked whether PTR_His larger than N. If larger, the flow advances to Step S604, whereas if not, the flow advances to Step S605. At Step S604 the following process is executed:

[0207] BND_H=1, DX_H=∞

[0208] At Step S605 it is checked whether a product of BND_Land CAL_Lis “1”. If “1”, the search process is terminated, whereas if not, the flow advances to Step S606.

[0209] At Step S606 it is checked whether BND_L+CAL_Lis “1”. If “1”, the flow advances to Step S607, whereas if not, the flow advances to step S607. At Step S607 the following process is executed:

[0210] DX_L=∥Y_Im(PTR_L)∥²−(V_m(PTR_L)−Z(m))²

[0211] CAL_L=1

[0212] At Step S608 it is checked whether BND_H+CAL_His “1”. If “1”, the flow advances to Step S609, whereas if not, the flow advances to Step S610. At Step S609 the following process is executed:

[0213] DX_H=∥Y_Im(PTR_H)∥²−(V_m(PTR_H)−Z(m))²

[0214] CAL_H=1

[0215] If DX_Lis smaller than Dx_Hat Step S610, the flow advances to Step S611, whereas if not, the flow advances to Step S612.

[0216] At Step S611 the following process is executed to thereafter return to Step S1206 shown in FIG. 12:

[0217] Dx=Dx_L, PTR=PTR_L, CAL_L=0

[0218] At Step S612 the following process is executed to thereafter return to Step S1206 shown in FIG. 12:

[0219] Dx=Dx_H, PTR=PTR_H, CAL_H=0

[0220] In the update process for PTR, PTR and related variables are changed and if the end condition is satisfied, the search process shown in FIG. 12 is terminated. At Step S1207 it is checked whether the value Dx calculated at Step S1206 satisfies the following formula, and if satisfied, the flow advances to Step S1216, whereas if not, the flow advances to Step S1208:

[0221] Dx≦ξ_t−1

[0222] At Step S1208 “2” is set to n. At Step S1209, the following process is executed:

[0223] s=I_m(PTR)

[0224] Dx←Dx−(Y_s(λ_n)−X(λ_n))²

[0225] At Step S1210 it is checked whether the value Dx satisfies the following formula, and if satisfied, the flow advances to Step S1216, whereas if not, the flow advances to Step S1211:

[0226] Dx≦ξ_t−1

[0227] At Step S1211 n is incremented by “1”. If the incremented n is larger than g, the flow advances to Sep S1212, whereas if not, the flow advances to Step S1209.

[0228] At Step S1212 a function calculation to be later described with reference to FIG. 14 is executed to thereafter advance to Step S1213. If g is equal to the vector dimension order d, the function calculation is not performed and the flow advances to Step S1214.

[0229] At Step S1213 it is checked whether the value Dx updated by the function calculation at Step S1212 satisfies the following formula, and if satisfied, the flow advances to Step S1216, whereas if not, the flow advances to Step S1214;

[0230] Dx≦ξt−

[0231] At Step S1214 an element corresponding to ξ_t−1is deleted from the neighbor set and a prototype currently processed is added;

[0232] N_t(X)←N_t−1(X)−{(τ_t−1, ξ_t−1)}+{(I_m(PTR), Dx)}

[0233] At Sep S1215, the minimum Dx and corresponding ID number of N_t(X) elements are stored as ξ_tand τ_t, respectively to advance to Step S1217.

[0234] At Step S1216 the following processes are executed to thereafter advance to Step S1217:

[0235] ξ_t=ξ_t−1, τ_t=τ_t−1

[0236] At Step S1217 t is incremented by “1”. If the incremented t is larger than N, the process is terminated, whereas if not, the flow returns to Step S1206.

[0237] The function calculation to be executed at Step S1212 will be described with reference to FIG. 7.

[0238] At Step S1401, (g+1) is set to j. At Step S1402 the following process is executed.

[0239] Dx←Dx−(Y_s(λ_j)−X(λ_j))²

[0240] At Step S1403, j is incremented by “1”. If the incremented j is larger than the vector dimension order d, the function calculation at Step S1212 is terminated, whereas if not, the flow returns to Step S1402.

[0241] N_j(X) after the completion of Step S1217 is output as the search result.

[0242] The effect of the embodiment described above was verified by experiments through computer calculations.

[0243] [Computer Experiments]

[0244] In order to verify the validity of the second embodiment, computer experiments were made for the number k=10 of prototypes requested as the search results and for the number N=10000 of prototypes. The following item was used as the experiment parameters:

[0245] the order of a vector dimension: d={10, 20, 30, 40, 50, 60, 70, 80, 90, 100}

[0246] The computer used by the experiments is as follows:

[0247] Silicon Graphics Co. 02

[0248] CPU: MIPS R10000, Rev 2.6 (175 MHz)

[0249] Main memory: 128 MB

[0250] OS: IRIX Release 6.3

[0251] The C programming language was used.

[0252] [Experiment Steps]

[0253] (1) A set of N prototypes of d-dimensional vector was generated by using uniform random numbers.

[0254] (2) One metric tensor of d-dimensional vector was generated by using uniform random numbers.

[0255] (3) One test vector of d-dimensional vector was generated by using uniform random numbers.

[0256] (4) An exhaustive search was conducted.

[0257] (5) A search was conducted by using the embodiment algorithm.

[0258] These five steps were repeated 100 times and an average of relative CPU times was calculated. The relative CPU time is (CPU time using the embodiment algorithm) divided by (CPU time using the exhaustive search).

[0259] The experiment results are shown in the graph of FIG. 15. In this graph, the abscissa represents a vector dimensionality and the ordinate represents a relative CPU time (CPU time ratio) η_T. The prototype number N was used as a parameter.

[0260] It is seen from FIG. 15 that as the order of a vector dimension is raised, the relative CPU time ratio increases in linear order independently from the prototype number N. A slope at N=10000 is very small. The relative CPU time ratio at N=10000 is very small as 3% for ten-dimensional vector and 11% even for 100-dimensional vector. The search process of searching ten nearest prototypes from 10000 prototypes of 100-dimensional vector took 3.7 sec for an exhaustive search as compared to 0.40 sec for the embodiment algorithm.

[0261] As described above, according to the embodiment a predetermined number of data pieces can be retrieved from a vector data set at high speed in accordance with an inner product of a given vector data. For example, a database such as an image database can be searched at high speed.

[0262] The invention is applicable to a system constituted of a plurality of computers as wall as a particular computer in the system. The invention may be realized by a program to be executed by a computer. This program may be supplied from an external storage medium. Such a storage medium storing the program falls in the scope of this invention.

[0263] Although the present invention has been described in its preferred form with a certain degree of particularity, many apparently widely different embodiments of the invention can be made without departing from the spirit and the scope thereof. It is to be understood that the invention is not limited to the specific embodiments thereof except as defined in the appended claims.