JP2007334402A - Server, system and method for retrieving clustered vector data - Google Patents

Abstract

In a similar search for high-dimensional vector data, when high-speed processing is implemented by clustering, there is generally no guarantee that the search results refer to all cases. When high accuracy is required, many clusters need to be referred to, and a quick response cannot be realized.
A search engine and an application transmit and receive search results and information related to the referenced cluster, with a fixed number of clusters referenced by the search engine at a time. The search engine omits the processing related to the already referenced clusters and further executes the processing related to a certain number of clusters, thereby making it possible to construct a more accurate search result with a constant response time.
[Selection] Figure 4

Description

  The present invention relates to retrieval of vector data on a computer.

  A general search for vector data is a search based on spatial position information such as map data. In this case, the number of dimensions of the vector data is about 2 to several dimensions at most. On the other hand, in a similar search for images / videos, vectors of several tens of dimensions to several hundreds of dimensions are used as data characterizing each data. In the similar search, a search for data serving as a search key and data having a short distance in the vector space, that is, a closest search in the vector space is performed. For example, in a similarity search of still images, a histogram of color distribution in the image is used as a feature vector that characterizes data.

  In the nearest neighbor search, it is necessary to know the distance between vectors. If the number of target data for distance calculation is N and the number of dimensions of the feature vector is M, N distance calculations are required between the search key data and the target data for distance calculation, and each distance calculation is required. Is proportional to M. Therefore, when the closest search is realized by a linear search, a calculation time proportional to N × M of one search time is required.

  As a technique for speeding up the nearest neighbor search process, a plurality of methods for narrowing the target data for distance calculation according to the search key data have been proposed. A group of techniques collectively referred to as multidimensional indexing is an extension of the concept of balanced trees used in the field of databases to multidimensional space processing. In multidimensional indexing, regions in space are managed in a tree structure. When the search key data is given, the leaf in which the area including the search key data is defined is searched with the order of Log N. On the other hand, in the field of pattern recognition, speeding up based on clustering is often used in which objects that are close to each other are classified in advance. As a specific classification method, the k-means method is common.

On the other hand, Non-Patent Document 1 discloses that a minimum distance and a maximum distance between an arbitrary point and another sample distribution under certain conditions established by a normal probability distribution based on analysis of probability vectors distributed in a high dimension. It has been shown that the ratio of and converges to 1 as the dimension of the space increases, that is, the difference in distance between all sample points disappears. Therefore, it is concluded that the above-mentioned various speed-up methods are difficult to produce a good effect in a general sense in high-dimensional space processing, and the performance is usually inferior to linear search. ing. However, Non-Patent Document 1 also points out that the clustering process is effective when the sample distribution is not a uniform structure but has a cluster structure.
Kevin Beyer, Jonathan Goldstein, Raghu Rmakrishnan, Uri Shaft .: "When Is Nearest Neighbor Meaningful", Proceeding of International Conference on Database Theory, 1999, p.217-235.

  Assuming that an appropriate feature vector is extracted for the target data, the sample distribution is assumed to have a certain degree of cluster structure. Therefore, if a cluster structure can be appropriately extracted therefrom, it is possible to expect a high-speed search based on clustering. However, how much speed can actually be increased depends on how far the existing clusters are separated from each other and the relationship between the search key and the clusters.

  For example, it is assumed that the entire data is classified into Nc clusters, and each cluster stores an average vector of members (that is, data included in each cluster). When searching, first, the distance between the search key vector and the average vector of each cluster is calculated. Next, the clusters are referred to in ascending order of the distance, and the distance between the members of each cluster and the search key is calculated to obtain the result of the similarity search, that is, the data near the search key.

  The true search result is a result when an exhaustive search (that is, a search for all members of all clusters) is performed. Next, in the above procedure, it is examined how many clusters can be referred to obtain a result that matches the true result.

  If the separation between clusters is good and the search key is near the average vector of any cluster, it will be sufficient to reference a small number of clusters. If the number of members of the nearest cluster is sufficiently larger than the required number of search results, it may be necessary to refer to only one cluster. Conversely, when the search key is located near the cluster boundary, it is necessary to refer to at least a cluster in contact with the boundary. Also, when the separation of clusters near the search key is poor, it is necessary to refer to a large number of clusters.

  During the actual search, the true result is unknown. Therefore, it is necessary to refer to as many clusters as possible in order to obtain a result as close as possible to the true result. However, if too many clusters are referenced, the amount of calculation is equivalent to that of linear search, so that the search speed cannot be increased. The same applies to the case where multidimensional indexing is used instead of clustering. In this case, a large number of leaves are referred to.

  Furthermore, when clustering or multidimensional indexing is used, processing other than the calculation of the distance to the data is required. That is, in clustering, distance calculation with the cluster average and multidimensional indexing require area determination when tracing a tree structure. In general, a simple linear search is more efficient for accessing a large amount of data. Therefore, it is necessary that these speed-up methods have sufficient effectiveness at least at the level of algorithm evaluation.

  Currently, in many fields that require similar search, the amount of data to be handled is increasing, and high-speed search instead of linear search is required. Accordingly, there is an increasing need for high-speed search technology that overcomes the above-mentioned problems.

  When considering the use of an actual similarity search, it is not always necessary to know the true result accurately, and a quick response on the application is often required. In the present invention, in a search engine based on clustering, a search engine and an application using the search engine transmit and receive the following data, thereby realizing an optimum processing system for an application that performs a similar search.

  When the search engine receives a search request from the client application, the search engine performs a similar search with reference to a predetermined number of clusters, and returns the acquired similar search result to the application side. At this time, the search engine also passes the information about the cluster referred for the search to the application side. The search result returned to the application side is generally high in reliability of the high-order, that is, high-similarity results, but low in reliability of the low-order results. When the application side needs a search result that is closer to the true result, it issues a search request under the same search condition to the engine side again. At this time, the application also transmits the search result acquired previously and information about the previously referenced cluster to the search engine. The search engine omits the process related to the previously referred cluster, refers to a predetermined number of clusters having a lower similarity, and performs a similar search process regarding the data of the cluster members. As a result, when data having a higher similarity than the previous search result is found, the search engine updates the search result and returns the search result to the application side together with the information of the referenced cluster. By repeating such processing, the application can acquire the result of the similarity search with higher accuracy as necessary.

  More specifically, a representative invention disclosed in the present application includes an interface for inputting and outputting data, a processor connected to the interface, and one or more storage devices connected to the processor. In the server, the storage device stores a plurality of first vector data each included in any of a plurality of clusters, and representative values for the clusters of the plurality of first vector data, and the processor Receives the search request including the second vector data, searches the representative value using the received second vector data as a key, and sequentially starts from the cluster including the representative value that is close to the second vector data. A plurality of first vector data included in the first predetermined number of clusters are searched using the second vector data as a key. Of the first vector data the search, the first vector data of a predetermined number of distance second close between the second vector data, and outputs through the interface.

  On the search engine side, only a fixed number of clusters are always referred to for a single search request, so that a substantially constant response time is realized. On the application side, the required search accuracy can be controlled in accordance with the usage context, so that it is possible to configure an optimum processing system for the end user.

  Hereinafter, a similarity search system for an image will be described as an embodiment of the present invention.

  FIG. 1 is a block diagram showing the configuration of the similarity search system according to the embodiment of this invention.

  The server computer 110 on which the search engine operates is connected to the client computer 130 on which the application program operates via the communication infrastructure 120, and provides services such as search to the client computer 130.

  The communication infrastructure 120 is a network (for example, an IP network) that connects the server computer 110 and the client computer 130.

  The server computer 110 includes at least an interface (I / F) 151, a CPU 152, a memory 153, and a hard disk 154 that are connected to each other.

  The I / F 151 is connected to the communication infrastructure 120 and is used for communication between the server computer 110 and the client computer 130.

  The CPU 152 is a processor that executes a program stored in the memory 153.

  The memory 153 is a storage device that stores a program executed by the CPU 152 and data referred to by the CPU 152. The memory 153 according to the present embodiment is a so-called main memory device, for example, a semiconductor memory device that can be randomly accessed. The memory 153 of this embodiment stores at least a server program and data for realizing the search server process 111.

  The hard disk 154 is a storage device including one or more hard disk drives (HDD). The hard disk 154 according to the present embodiment stores information about the feature vector of the image stored in the image server 140 as feature data 114 and cluster management information 115.

  The feature amount vector is obtained by digitizing the feature of an image stored in the image server 140 as vector data. The feature vector can be calculated by various conventionally known methods.

  In the present embodiment, each feature vector is classified into one of a plurality of clusters. It is desirable that feature vectors that are close to each other are classified into the same cluster. The feature amount vector may be classified into clusters by any method, but in the present embodiment, it is classified by the k-means method.

  One feature amount data 114 includes a set of a data ID for identifying one or more images classified into one cluster and a feature amount vector of image data identified by the ID. Note that the images and feature vectors classified into each cluster are also described as cluster members.

  The cluster management information 115 includes a set of a cluster ID for identifying each cluster and a representative value of the cluster identified by the cluster ID.

  In the present embodiment, the representative value of each cluster is an average vector (cluster average) of feature quantity vectors included in each cluster. However, a value other than the average vector may be used as the representative value of the cluster. For example, the feature vector of cluster members close to the average vector may be used, or other statistical representative values such as the mode value and the median value may be used. As a result of optimization by the k-means method, when each cluster is completely separated, each feature vector is included in a cluster including a representative value closest to the feature vector.

  Note that the hard disk 154 of this embodiment may be replaced with an optical disk device, a semiconductor storage device such as a flash memory, or any other type of storage device.

  The image server 140 is a computer that includes a storage device (not shown) that stores image data and is connected to the communication infrastructure 120.

  The search server process 111 in the server computer 110 manages search targets that are clustered (that is, classified into clusters). When the system is operating, the cluster management information 115 is expanded as the cluster management information 112 in the memory 153 of the server computer. As each cluster information 113, each cluster ID, an average vector which is a representative value of the cluster identified by the ID, a data ID string for identifying cluster members, and the like are stored. The feature vector of each cluster member is managed on the hard disk 154 collectively as feature data 114. For this reason, as the cluster information 113 in the memory 153, the position on the hard disk that stores the feature vector of each cluster member is further stored.

  The cluster management information 112 is a copy of the cluster management information recorded on the hard disk 154. Therefore, when an update to the cluster occurs, not only the cluster management information 112 but also the cluster management information 115 on the hard disk 154 is updated. However, the cluster management information 115 is not directly referenced in the search process.

  The client computer 130 is a computer connected to the communication infrastructure 120 and running an application program (not shown). Although two client computers 130 are shown in FIG. 1, the present similarity search system may include any number of client computers 130.

  The client computer 130 may be a computer having any configuration. FIG. 1 shows a configuration of a typical client computer 130. That is, the client computer 130 of FIG. 1 includes a CPU 131, a memory 132, an I / F 133, an input device 134, and an output device 135.

  The CPU 131 is a processor that executes a program stored in the memory 132.

  The memory 132 is a storage device that stores programs executed by the CPU 131. The memory 132 stores at least an application program (not shown).

  The I / F 133 is an interface that is connected to the communication infrastructure 120 and is used for communication between the client computer 130 and the server computer 110.

  The input device 134 is a device that receives input from the user of the client computer 130. The input device 134 may include, for example, a keyboard, a pointing device, an image scanner, or the like.

  The output device 135 is a device that displays information to the user of the client computer 130. Specifically, for example, an image acquired as a result of the similarity search is displayed on the output device 135. The output device 135 is an image display device such as a CRT or a liquid crystal display.

  Next, processing at the time of data registration in the similar search system will be described.

  This system uses clustering based on the k-means method. However, if all data is clustered for each data registration, it is impossible to perform the registration process in a practical processing time. In this system, when new data is registered, a predetermined number of clusters having a distance close to that data are searched as neighboring clusters, and optimization of the k-means method is executed for the retrieved neighboring clusters. In addition, in order to continuously and physically secure storage areas on the hard disks of the members of each cluster, a predetermined amount of disk area is secured at the time of cluster generation. Accordingly, the maximum number of each cluster member is also limited.

  FIG. 2 is a flowchart showing processing executed at the time of data registration in the embodiment of the present invention.

  The process shown in FIG. 2 is executed as a part of a server program that implements the search server process 111. Therefore, the process shown in FIG.

  When given the new data x to be registered, the CPU 152 first searches for a nearby cluster and acquires a set C * of neighboring clusters (210). Specifically, the CPU 152 compares the average vector of each cluster with the new data x, and selects a predetermined number of clusters in order from the cluster represented by the average vector whose distance is close to the new data x. Get as *.

  Next, the CPU 152 adds the new data x to the nearest cluster c * (that is, the cluster represented by the average vector closest to the new data x) in the set C * of adjacent clusters (220). .

  Next, the CPU 152 initializes the parameter t and the parameter i to “0” and “1”, respectively (221, 222). The parameter t is used to count the number of iterations of the k-means method update. The parameter i is used to indicate a cluster included as an element in the set C * of neighboring clusters.

  Thereafter, an optimization loop based on the k-means method shown in step 230 and after is entered.

  Specifically, the CPU 152 determines whether or not the number of cluster members exceeds the limit M_max for each cluster that is an element of the set C * of adjacent clusters (230) (231).

  Specifically, CPU 152 determines in step 230 whether parameter i is equal to or less than the number of elements in set C *. If it is determined in step 230 that the parameter i is less than or equal to the number of elements in the set C *, the CPU 152 targets the cluster c that is the i-th element of the set C * (234), and the number of members of the cluster c is It is determined whether or not M_max is exceeded (231). At the time of entering the optimization loop, it is assumed that the cluster other than the nearest cluster c * to which the new data x is added does not exceed the member number limit.

  If the number of members of the closest cluster c * exceeds M_max, the CPU 152 divides the cluster into two (232), and adds the newly generated cluster d to the elements of the set C * of neighboring clusters (233). . Various methods can be considered as a method of dividing a cluster into two. Here, the principal axis is obtained with respect to the vector distribution in the cluster, and the members are grouped into two clusters by determining on which side the projection of the vector of each member onto the principal axis is on the projection of the cluster average vector. Divide.

  After step 233 is executed, the process of the CPU 152 returns to step 231. In step 231, it is determined whether the number of cluster members after the division exceeds M_max. If it is determined that the number of members of the cluster after the division exceeds M_max, the process proceeds to step 232 to further divide the cluster. On the other hand, when it is determined that the number of members of the cluster after the division does not exceed M_max, the CPU 152 adds 1 to the value of the parameter i in order to execute the determination of step 231 for the next cluster (235 ) And return to Step 230.

  In step 230, when it is determined that the parameter i exceeds the number of elements of the set C *, it is confirmed that the number of members of all the clusters that are elements of the set C * is within M_max. In this case, the CPU 152 checks the number of optimization iterations t by the k-means method (240).

  In this system, the optimization shown in FIG. 2 is intended only for a subset of clusters, and does not mean optimization for the entire cluster. Further, it is assumed that the addition of data is repeatedly performed thereafter, and optimization is executed each time. Therefore, it is not necessary to place an extreme importance on optimization at a certain point in time, and it is sufficient that the maximum number of iterations t_max is several times.

  If it is determined in step 240 that the parameter t indicating the number of iterations is equal to or greater than the maximum number of iterations t_max, optimization by the k-means method has been performed a predetermined number of times, and the processing in FIG. 2 ends. Alternatively, if it is determined in step 240 that the set C * has not changed, it is considered that no further optimization is required. Therefore, also in this case, the process of FIG.

  On the other hand, if it is determined in step 240 that the parameter t indicating the number of iterations is smaller than the maximum number of iterations t_max and the set C * is changing, it is necessary to perform cluster optimization. Updates the set C * by the k-means method (250).

  The process of step 250 is the same as the normal k-means method. That is, all data included in the adjacent cluster is distributed to the cluster having the closest cluster average at that time. This updates the members of each neighboring cluster and the cluster average, and returns to step 230. Unlike the point in time when the optimization loop is entered, this time, if the cluster state changes greatly, there is a possibility that a plurality of clusters may exceed the upper limit of the number of members. Moreover, since it is not sufficient to divide into two, there is a possibility that division may be necessary again, or a newly generated cluster may exceed the upper limit. For this reason, the CPU 152 proceeds to step 240 after performing processing (from step 230 to step 235) so that the number of members of all clusters is equal to or less than the upper limit M_max. In step 240, if the number of iterations reaches the maximum number t_max, or if there is no change in the state of the set C * of neighboring clusters, the process is terminated.

  The series of processing shown in FIG. 2 is executed in the work area on the memory 153, and the final proximity cluster state is stored on the hard disk 154. When saving on the hard disk 154, the following functions are provided as options.

  In general, a cluster having high similarity is highly likely to be referred to at the time of update and search. Therefore, if the clusters having high similarity are arranged as close to each other as possible on the hard disk, the disk scanning load should be reduced.

  Equation (1) is an energy function for defining a cluster position rearrangement procedure. Nc represents the number of clusters, and v_i represents an average vector of clusters at the i-th position. This energy function is defined as the sum of the squared distances of the cluster averages at successive positions.

  However, the boundary conditions at the positions at both ends, that is, the first position and the Nc-th position are defined in a form in which folding is performed at both ends. Specifically, the average vector v_2 of the cluster at the second position is used instead of the average vector v_0 of the cluster at the zeroth position that does not exist. Further, instead of the average vector v_Nc + 1 of the non-existing Nc + 1-th cluster, the average vector v_Nc-1 of the Nc-1-th cluster is used. At this time, the amount of change in the energy function when the cluster at the i-th position and the cluster at the j-th position are exchanged is calculated by Expression (2). However, j> i.

  If the cluster positions in the array are updated so that the energy function is reduced based on the energy change amount, a state in which the distance between clusters existing at adjacent positions in the array is relatively small can be realized.

  FIG. 3 is a flowchart showing cluster position rearrangement processing executed in the embodiment of the present invention.

  The process shown in FIG. 3 is executed as part of a server program that implements the search server process 111. Therefore, the process shown in FIG.

  First, the CPU 152 searches a set of clusters that maximizes the amount of energy reduction calculated by the equation (1) from the set C * of adjacent clusters that are currently being updated (310).

  Next, the CPU 152 determines whether or not a cluster set corresponding to the condition of step 310 has been found (320).

  If no such cluster set is found, there is no exchange of positions that reduces energy (in other words, the current cluster array has the lowest energy). In this case, since each cluster is considered to be optimally arranged, the processing ends.

  On the other hand, if a corresponding cluster set is found, the CPU 152 updates the array by exchanging its position (330) and returns to step 310 to search for the next cluster set. Finally, the cluster member feature vector is stored on the hard disk 154 in accordance with the position on the array thus obtained.

  Next, search processing in this system will be described.

  FIG. 4 is an explanatory diagram showing an outline of information flow between the client and the server and processing in each program in the similarity search according to the embodiment of this invention.

  The client program is an application program that is stored in the memory 132 of the client computer 130 and executed by the CPU 131. The CPU 131 executes the processing on the client side shown in FIG. 4 while controlling the input device 134 and the output device 135 as necessary. On the other hand, the server program is a program for realizing the server process 111, stored in the memory 153 of the server computer 110, and executed by the CPU 152.

  In the following description, data transmitted from the client program to the server program and data returned from the server program to the client program are actually transmitted to the I / F 133, the communication infrastructure 120, and the I / F 151. Are sent and received via

  A user of the client computer can input a search request using the input device 134. The client program that has received the request (401) from the user transmits a search request including vector data (hereinafter referred to as key data) serving as a key for similarity search as a search condition to the server program (402).

  The server program first executes a similarity search for the cluster (403). Hereinafter, this is referred to as an intercluster search process. The inter-cluster search process calculates the distance between the key data and the average vector of all clusters, and obtains an array consisting of a predetermined number of Rc clusters sorted in the order of small (ie, close) distance. .

  Next, by referring to the members in the sorted cluster array and calculating the distance between the feature vector of each cluster member and the key data, the result of the similarity search is derived (404). Specifically, the distance between the feature vector of all members of the sorted Rc clusters and the key data is calculated, and the cluster members are sorted in ascending order of the distance. Hereinafter, this processing is referred to as intra-cluster search processing.

  The server program returns the result of the similarity search to the client program (405). The result of the similarity search returned to the client program includes identifiers of a predetermined number of cluster members in order from the one closest to the key data. At this time, the server program returns information about the cluster actually referred to (that is, the cluster for which the similar search has been completed) added to the result of the similar search. Hereinafter, the information about the cluster actually referred to in the previous similar search is referred to as “reference cluster information”. Search results and reference cluster information will be described later with reference to FIGS.

  The client program that has received the search result executes processing such as display of the search result (406). For example, the client program may display an image identified by an identifier included in the received search result on the output device 135. An example of the display of the search result will be described later with reference to FIG.

  After that, when a search request with the same condition is received from the user again (407), the client program transmits the previously acquired reference cluster information and search result together with the search condition to the server program as a search request (408). .

  When the search request is received, the server program executes the inter-cluster search process again (409). At this time, the server program can omit the distance calculation regarding the referenced cluster by using the reference cluster information. As a result of the search in step 409, Rc × 2 clusters obtained by adding Rc to the number of clusters Rc searched last time are sorted in ascending order of the distance between the average vector of each cluster and the key data. As a result, an array composed of sorted Rc × 2 clusters is obtained.

  In the next intra-cluster search process (410), the server program skips the search for the members of the top Rc clusters that were referenced last time, and the Rc items in the rank from Rc + 1 to Rc × 2 For the cluster, the key data is used to perform a similarity search with cluster members, and the search result is merged with the previous search result. Specifically, the search results obtained this time and the search results obtained last time are combined, and the cluster members that are the search results are sorted in order of increasing distance from the key data.

  The server program returns the search result updated in this way and the information related to Rc × 2 reference clusters to the client program (411).

  Thereafter, the number of reference clusters increases by repeating similar processing. As a result, the client program can sequentially obtain search results with higher accuracy in response to a request from the user. The number of clusters newly searched in response to one search request is constant (Rc). There is an upper limit (M_max) for the number of members in each cluster. For this reason, the time required for the search processing corresponding to one search request does not exceed a certain upper limit. If the number of members of each cluster is substantially the same, the time required for the search processing corresponding to one search request is also approximately the same.

  FIG. 5 is an explanatory diagram of the reference cluster information according to the embodiment of this invention.

  Specifically, FIG. 5 is an explanatory diagram of reference cluster information transmitted / received between the client program and the server program in, for example, steps 405, 408, and 411 of FIG.

  Each cluster is managed by a cluster ID that identifies each cluster. The reference cluster information includes a time stamp 510, a cluster ID column for identifying a cluster already referenced for search, and information indicating a distance between the average vector of each cluster and key data. The time stamp 510 records the time when the reference cluster information was generated.

  In FIG. 5, the pairs of cluster IDs and distances are aligned so that the distance values are in ascending order. That is, the cluster ID having the smallest distance value is the head of the reference cluster information.

  FIG. 6 is an explanatory diagram of search results according to the embodiment of this invention.

  Specifically, FIG. 6 is an explanatory diagram of search results transmitted and received between the client program and the server program in, for example, steps 405, 408, and 411 of FIG.

  The search result includes a data ID column for identifying the cluster member obtained as a result of the intra-cluster search process, and information indicating the distance between the feature quantity vector of each cluster member and the key data.

  As in FIG. 5, the pairs of data IDs and distances in FIG. 6 are aligned so that the distance values are in ascending order.

  FIG. 7 is a flowchart showing intra-cluster search processing executed in the server program according to the embodiment of this invention.

  The process of FIG. 7 is executed in steps 404 and 410 of FIG. Accordingly, the processing of FIG. 7 is executed by the CPU 152 of the server computer 110 as part of the server program.

  First, an outline of the process will be described.

  The determination in step 710 is a determination for skipping the referenced cluster from the beginning of the cluster array obtained by the inter-cluster search. When there is no change in the cluster members and the cluster order, the inter-cluster search results are unchanged. In this case, the result of the intra-cluster search process for the referenced cluster should be the same as the already acquired result. Therefore, in this case, the intra-cluster search process for the referenced cluster can be omitted.

  However, if the status of the entire cluster changes due to data update processing, the inter-cluster search result may change. For example, when a new member is added to the cluster (see FIG. 2), and when the order of the clusters is changed (see FIG. 3), it is necessary to execute a search process within the cluster for those clusters. . A determination is made in step 720 as to whether the intra-cluster search process can be omitted.

  In a loop after step 730, a similarity search is performed on members of predetermined Rc clusters excluding the referenced cluster. If there is a cluster whose state has changed since it was last referenced for similarity search, that cluster is not included in the referenced cluster.

  Next, details of the processing will be described.

  In the following description, the array A corresponds to the array of clusters indicated by the reference cluster information. The array B corresponds to the array obtained as a result of the intercluster search process. For example, when the process of FIG. 7 is executed in step 410 of FIG. 4, the array of clusters indicated by the reference cluster information (1) transmitted from the client program in step 408 corresponds to the array A, and the cluster of step 409 The result of the inter-search process corresponds to the array B. Parameters i and j are used to indicate the elements included in array A or B.

  First, the server program initializes the value of the parameter i to “0” (701).

  Next, the server program determines whether or not the value of the parameter i is less than or equal to the number of elements in the array A (710).

  If it is determined in step 710 that the value of parameter i is less than or equal to the number of elements in array A, then the server program determines whether cluster A [i] and cluster B [i] are the same. Determine (720).

  A cluster is managed by a cluster ID. Therefore, when the cluster IDs of A [i] and B [i] are different, it is determined that these clusters are not the same. Furthermore, even if the cluster IDs of A [i] and B [i] are the same, the states may be different. Therefore, the time stamp 510 is referred to for the determination in step 720. Even if the cluster IDs of A [i] and B [i] are the same, if B [i] has been updated after the time indicated by the time stamp 510 for A [i], these clusters are determined to be different clusters. Is done.

  If it is determined in step 720 that A [i] and B [i] are different clusters, the state of cluster B [i] has been updated since it was last referenced. In this case, the server program proceeds to Step 722 in order to execute the intra-cluster search process for the cluster B [i] and its lower clusters.

  On the other hand, if it is determined in step 720 that A [i] and B [i] are the same cluster, the intra-cluster search process for B [i] that is the referenced cluster may be omitted. it can. In this case, in order to determine the next element, the server program adds 1 to the value of the parameter i (721), and returns to step 710.

  If it is determined in step 710 that the value of the parameter i exceeds the number of elements in the array A, the cluster B [i] and lower clusters have not yet been subjected to intra-cluster search processing. In this case, the server program proceeds to Step 722 in order to execute the intra-cluster search process for the cluster B [i] and its lower clusters.

  When the start position of a cluster to be newly referred to (that is, B [i] at the time of step 722) is determined, the server program executes an intra-cluster search process for Rc clusters starting from the cluster.

  Specifically, in step 722, the server program initializes the value of the parameter j to “1”.

  Next, the server program determines whether or not the value of the parameter j is equal to or less than a predetermined reference cluster number Rc (730).

  If it is determined in step 730 that the value of the parameter j is equal to or less than Rc, the intra-cluster search process for Rc clusters has not been completed yet. In this case, the server program executes an intra-cluster search process for the cluster B [i + j] (740). Specifically, the server program calculates the distance between the members of the cluster B [i + j] and the key data.

  Next, the server program updates the search result by merging the result obtained from the cluster B [i + j] with the already obtained search result (750). Here, the already acquired search result is a search result included in the search request transmitted from the client program (for example, search result (1) shown in step 408 in FIG. 4). Specifically, the server program adds the members of the cluster searched in step 740 to the cluster members that are already acquired search results, and sorts these cluster members in ascending order of the distance from the search key data. To do.

  Next, in order to process the next cluster, the server program adds 1 to the value of the parameter j (751) and returns to step 730.

  If it is determined in step 730 that the value of the parameter j exceeds Rc, the intra-cluster search process for Rc clusters is completed. In this case, the server program ends the process.

  Next, display of search results for the user in this system will be described.

  FIG. 8 is an explanatory diagram of an example of the state transition of the search result display screen displayed in the embodiment of the present invention.

  As described with reference to FIGS. 1 to 7, the server program according to the present embodiment executes a similarity search for a large number of vector data using the vector data transmitted from the client program as a key. . Then, the server program returns the search result to the client program. The client program may display the vector data itself as a search result, but may display data associated with the vector data.

  In the present embodiment, the vector data to be searched is an image feature vector. In this case, the client program does not display the feature vector obtained by the search but displays an image corresponding to the feature vector as a search result. An image corresponding to the feature vector is stored in the image server 140.

  As shown in FIG. 6, when the search result transmitted from the server program to the client program includes a data ID, the client program acquires an image identified by the received data ID from the image server 140, and The search result is displayed on the output device 135.

  FIG. 8 shows an example of a screen that displays an image corresponding to the feature vector obtained by the search as a search result. The screen in FIG. 8 is displayed on the output device 135 of the client computer.

  In the example of FIG. 8, the maximum number of search results is 100, and the screen configuration displays 20 images on one screen. Although only 20 items are displayed on the screen, the client program always requests the server program for the top 100 search results having high similarity between the feature vector and the key data. Is set.

  FIG. 8 shows an example in which similar search result display screens 810, 820, 830, and 840 are sequentially displayed. Each screen 810 and the like includes a search result 811 and a button 812 and the like. The search result 811 is an image as a search result or a thumbnail image obtained by reducing the image.

  On the initial screen 810 of the search result display, the first to twentieth out of 100 search results are arranged and displayed in the order of high similarity between the feature vector and the key data (811). . The display of the initial screen 810 corresponds to step 406 in FIG. Therefore, the search result displayed at this time corresponds to the search result (1) in step 405 of FIG.

  On the initial screen 810, buttons 812 and 813 are further displayed. The button 812 is a button for receiving a request to display the first 20 search results (that is, the search results from the first place to the 20th place). On the other hand, the button 813 is a button for receiving a request to display the next 20 items (that is, the search results from the 21st place to the 40th place).

  The initial 20 items are displayed on the initial screen. For this reason, the user cannot operate the button 812. In this case, the button 812 is displayed in a different mode (for example, different color or shape) from the button 813.

  Here, when the user operates the button 813, the client program transmits a search request to the server again. When the input device includes a mouse, the operation of the button 813 may be a mouse click. The operation of the button 813 by the user corresponds to step 407 in FIG. 4, and the search request transmitted as a result corresponds to step 408. The server program executes a similar search process according to the received search request and returns the result to the client program (steps 409, 410 and 411 in FIG. 4).

  As a result, the client program acquires 100 updated search results. After obtaining the search results, the screen 810 transitions to the screen 820. In this system, the upper search results are relatively stable, and in the normal case, the images from the 21st to the 40th in the updated search results are displayed on the screen 820 in the order of high similarity. Is done.

  However, as a result of updating the search result, there are naturally cases where fluctuation occurs within the top 20 positions. In this case, on the screen 820, 20 images in the top 40 positions in the updated search result and not yet displayed on the screen 810 are displayed in descending order of similarity. For example, when the 4th and 8th images in the updated search result are not included in the 20th position in the previous search results, the search result displayed on the screen 820 is 4th in the top. Next, the 8th image is displayed, and then the 21st to 38th images are displayed. In this case, the 39th and 40th images are not displayed on the screen 820.

  On the screen 820, buttons 821, 822, and 823 are displayed. The functions of the buttons 821 and 822 are the same as the buttons 812 and 813 of the screen 810, respectively. The button 823 is a button for receiving a request to display the next 20 search results displayed on the screen 820 (that is, the search results from the 41st place to the 60th place). Therefore, when the user operates the button 821, the search result display of the top 20 is returned. When the user operates the button 823, search results from the 41st place to the 60th place are displayed. The user cannot operate the button 822.

  For example, when the user clicks the button 821, the screen 820 transitions to the screen 830. At this time, the search result is not updated. The search result image displayed on the screen 830 is exactly the same as that displayed on the image 810. However, the number of buttons displayed on the screen 830 is the same as that on the screen 820.

  Specifically, buttons 831, 832 and 833 are displayed on the screen 830. The functions of these buttons are equivalent to the buttons 821, 822 and 823 on the screen 820, respectively. However, like the button 812 on the screen 810, the user cannot operate the button 831.

  Thereafter, when the user sequentially requests display of lower-order search results that are not yet displayed, the search results are updated by the same procedure as described above, and the number of buttons increases. The above processing is executed until the screen 840 that finally displays the search results from the 81st place to the 100th place is displayed. On the screen 840, search result images from the 81st place to the 100th place and five buttons 841 to 845 are displayed. The functions of the buttons 841 to 843 are equivalent to the buttons 821 to 823 of the screen 820, respectively. The button 844 is a button for requesting display of search results from the 61st place to the 80th place. The button 845 is a button for requesting display of search results from the 81st place to the 100th place.

  If, on the screen 810, a button requesting display of search results after the 41st place is displayed from the beginning, for example, display of search results from the 41st place to the 60th place may be requested. When this request is made, the search results from the 21st place to the 40th place are not displayed yet. For this reason, the server program displays the search results in the clusters for the Rc clusters for displaying the search results from the 21st place to the 40th place and the search results from the 41st place to the 60th place. It is necessary to execute the intra-cluster search process for the next Rc clusters. In other words, the server program needs to execute an intra-cluster search process for Rc × 2 clusters in response to a single search request. As a result, the response time for a single search request becomes longer than when the intra-cluster search process for Rc clusters is executed.

  On the other hand, according to the user interface shown in FIG. 8, only when a higher-order search result is displayed, it is permitted to accept a display request for a search result continuous below the displayed search result. For example, when it is requested to display 20 search results from the top 20 first, the search results from 1st to 20th are displayed on the screen 810 displayed in response to the request. . However, on this screen 810, a button 813 for requesting display of the next 20 items (that is, 21st to 40th) is displayed, but a button for requesting display of search results after the 41st is displayed. Not. When the button 813 is operated and the search results from the 21st place to the 40th place are displayed once, then the buttons 823, 833 or 843 for displaying the search results from the 41st place to the 60th place are displayed (screen 820, 830 or 840). For this reason, the server program does not receive a search request for more than Rc clusters. Therefore, the server program can return the search result within a substantially fixed response time in response to one search request.

  A feature of the above screen configuration is that a restriction is imposed on the display range designation of the search result, and a certain range can be displayed only after the upper range is displayed. This restriction does not prevent a user operation that is normally performed to look in order from the top, but naturally encourages such an operation. In particular, when viewing data sorted according to some criteria, not limited to similarity, it is the most natural operation flow to check the contents in order from the top. Therefore, there is no dissatisfaction with the user in terms of operability. In addition, since unnecessary functions are removed, the screen is easier to understand.

  The search result display on the screen shown in FIG. 8 does not accurately reflect the rank of similar search results. In addition, there are rarely images that are not displayed as search results even though they are included in the top 100 final search results. First, regarding the ranking, in the case of the similar search, the purpose is to browse similar data, and the accurate ranking is not particularly meaningful information for the user. Therefore, there is no particular inconvenience for the user. Regarding the contents of the search results, as described above, in this system, the higher-order search results are relatively stable, and the data out of the display is the data with the lower similarity in the search results. In the similarity search, since it is assumed that the user is interested in data having high similarity, this is also not inconvenient for the user.

  On the other hand, unlike the screen configuration shown in FIG. 8, there is a user interface that displays a large amount of search results, for example, the top 1000 items. A method for displaying such a large amount of data is described in Japanese Patent Application Laid-Open Nos. 2000-29885 and 2004-62356. When displaying a large amount of data, since it takes time to transfer the image data, all images are not displayed at once. In this case, the search result is automatically updated at predetermined time intervals. When the search result is updated, the image to be displayed by the client program is also updated. Data deviating from the search result due to the update is also removed from the screen. This automatic update is repeated until the user specifies another search condition. When this method is adopted, the latest search result is always displayed on the screen. In addition, the fluctuation of the display image due to the automatic update decreases according to the number of updates, and the number of images that the application side needs to newly acquire also decreases. Therefore, an unnecessary communication load or the like does not occur.

  In the above embodiment of the present invention, the case where the vector data to be searched is the feature vector of the image has been described as an example. However, the present invention can be applied to search for any kind of vector data. it can.

  As described above, according to the embodiment of the present invention, the vector data to be searched is classified into clusters in advance, and the representative value of each cluster is determined. When a search request using arbitrary vector data as a key is issued, a similarity search is executed only for a predetermined number of clusters represented by representative values that are close to the key data. For this reason, a high-speed similarity search can be realized. When each cluster is composed of mutually similar vector data, a certain degree of accuracy can be expected for the first search. If the target data could not be acquired by the search according to the first search request, the range of target clusters for the similar search is sequentially expanded by repeatedly issuing a search request using the same vector data as the previous key. The As a result, the search accuracy improves each time the search request is repeated. The user can issue a search request repeatedly until a search result with a required accuracy is obtained. When the search request is repeated, a similar search for a cluster that has already been searched is omitted. For this reason, even if the range of the target of the similar search is expanded, the number of clusters in which the similar search is actually executed in response to one search request can be made constant. As a result, the response time to the search request is suppressed to a certain value or less.

It is a block diagram which shows the structure of the similar search system of embodiment of this invention. It is a flowchart which shows the process performed at the time of data registration in embodiment of this invention. It is a flowchart which shows the process of the rearrangement of the cluster position performed in embodiment of this invention. It is explanatory drawing which shows the outline of the process in each information flow between the client and server in the similar search of embodiment of this invention, and each program. It is explanatory drawing of the reference cluster information of embodiment of this invention. It is explanatory drawing of the search result of embodiment of this invention. It is a flowchart which shows the search process in a cluster performed in the server program of embodiment of this invention. It is explanatory drawing of the example of the state transition of the search result display screen displayed in embodiment of this invention.

Explanation of symbols

110 Server computer.
111 Search server process.
112 Cluster management information 113 Cluster information 114 Cluster member feature data 115 Recorded cluster management information 120 Communication infrastructure 130 Client computer 131, 152 CPU
132, 153 Memory 133, 151 Interface 134 Input device 135 Output device 154 Hard disk 210 Acquisition of proximity cluster 220 Addition of data to nearest cluster 230 Loop determination part 231 regarding number of adjacent cluster elements Checking the number of cluster members 232 Cluster division 233 Addition of cluster 240 Check of number of iterations of k-means method 250 Execution of k-means method 310 Search for pair to be exchanged 320 Judgment whether pair has been found 330 Update cluster array 401 User input 402 From client to server Transmission information (first time)
403 Inter-cluster search process 404 In-cluster search process 405 Return information from server to client (first time)
406 Search result display 407 User input 408 Transmission information from client to server (second time)
409 Inter-cluster search process 410 In-cluster search process 411 Return information from server to client (second time)
510 time stamp 710 determination of number of referenced clusters 720 determination of cluster identity 730 determination of number of newly referred clusters 740 similarity search in cluster 750 search result update 810 similar image search result display screen / first to 20th 811 Search results 812, 821, 831, 841 Buttons 813, 822, 832, 842 for displaying the first place to the 20th place Button 820 for displaying the 21st place to the 40th place 820 Similar image search result display screen / 21st to 40th place Positions 823, 833, 843 Button 830 for displaying positions 41 to 60 830 Similar image search result redisplay screen / first to 20th positions 831 Button row 821 for switching the display order for displaying first to 20th positions Button 840 Similar image search result display screen / Display from 81st to 100th 841 Button for the button 845 81 position for displaying the 80-position from the column 844 61 of the button for switching the position to display the position 100

Claims (20)

In a search server comprising an interface for inputting and outputting data, a processor connected to the interface, and one or more storage devices connected to the processor,
The storage device stores a plurality of first vector data each included in one of a plurality of clusters, and representative values for the clusters of the plurality of first vector data,
The processor is
When the search request including the second vector data is received, the representative value is searched using the received second vector data as a key,
A plurality of first vector data included in a first predetermined number of the clusters are searched in order from the cluster including the representative value that is close to the second vector data using the second vector data as a key. ,
A search server characterized in that a second predetermined number of the first vector data having a short distance to the second vector data among the searched first vector data is output via the interface.   2. The search server according to claim 1, wherein each of the first vector data is included in the cluster including the representative value that is closest to the first vector data. The processor is
When a search request including the second vector data and information indicating the cluster for which the search for the first vector data has been completed using the second vector data as a key is received, other than the cluster indicated by the received information The representative value of the cluster of the second vector data as a key, and
Among the clusters other than the cluster indicated by the received information, a plurality of the clusters included in the first predetermined number of the clusters in order from the cluster including the representative value that is close to the second vector data. The search server according to claim 1, wherein the first vector data is searched using the second vector data as a key.   2. The search server according to claim 1, wherein the processor outputs information indicating the cluster for which the search of the first vector data has been completed using the second vector data as a key. The processor is
When a search request including the second vector data and information indicating the cluster for which the search for the first vector data has been completed using the second vector data as a key is received, other than the cluster indicated by the received information The representative value of the cluster of the second vector data as a key, and
Among the clusters other than the cluster indicated by the received information, a plurality of the clusters included in the first predetermined number of the clusters in order from the cluster including the representative value that is close to the second vector data. The search server according to claim 4, wherein the first vector data is searched using the second vector data as a key. The one or more storage devices include a first storage device that stores the first vector data, and a second storage device that stores the representative value,
The first storage device is a disk storage device;
The search server according to claim 1, wherein the second storage device is a randomly accessible storage device. In a search system comprising a terminal computer and a search server connected via a network,
The search server includes an interface connected to the network, a processor connected to the interface, and one or more storage devices connected to the processor,
The storage device stores a plurality of first vector data each included in one of a plurality of clusters, and representative values for the clusters of the plurality of first vector data,
When the terminal computer receives the input of the second vector data, the terminal computer transmits a search request including the received second vector data to the search server via the network,
The processor is
When a search request including the second vector data is received via the interface, the representative value is searched using the received second vector data as a key,
A plurality of first vector data included in a first predetermined number of the clusters are searched in order from the cluster including the representative value that is close to the second vector data using the second vector data as a key. ,
Out of the searched first vector data, a second predetermined number of the first vector data having a short distance to the second vector data is output via the interface;
The terminal device, when receiving the first vector data from the search server, displays the received first vector data or data associated with the received first vector data as a search result. system.   The search system according to claim 7, wherein each of the first vector data is included in the cluster including the representative value that is closest to the first vector data. The processor is
When a search request including the second vector data and information indicating the cluster for which the search for the first vector data has been completed using the second vector data as a key is received, other than the cluster indicated by the received information The representative value of the cluster of the second vector data as a key, and
Among the clusters other than the cluster indicated by the received information, a plurality of the clusters included in the first predetermined number of the clusters in order from the cluster including the representative value that is close to the second vector data. The search system according to claim 7, wherein the first vector data is searched using the second vector data as a key.   8. The search system according to claim 7, wherein the processor outputs, via the interface, information indicating the cluster for which the search of the first vector data has been completed using the second vector data as a key. . The processor is
When a search request including the second vector data and information indicating the cluster for which the search for the first vector data has been completed using the second vector data as a key is received, other than the cluster indicated by the received information The representative value of the cluster of the second vector data as a key, and
Among the clusters other than the cluster indicated by the received information, a plurality of the clusters included in the first predetermined number of the clusters in order from the cluster including the representative value that is close to the second vector data. The search system according to claim 10, wherein the first vector data is searched using the second vector data as a key. The one or more storage devices include a first storage device that stores the first vector data, and a second storage device that stores the representative value,
The first storage device is a disk storage device;
The search system according to claim 7, wherein the second storage device is a randomly accessible storage device.   When the terminal device receives the first vector data searched using the second vector data as a key and the information indicating the cluster for which the search of the first vector data is completed from the search server, the terminal device The search request including vector data, the received first vector data, and the received information indicating the cluster is transmitted to the search server via the network. Search system. The terminal device
Upon receiving a display request for the second predetermined number of search results, the search request is transmitted to the search server;
Displaying the second predetermined number of search results in ascending order of distance between the second vector data and the first vector data;
Only when the second predetermined number of search results are displayed, reception of a display request for the second predetermined search result that is consecutively lower than the displayed search results is permitted. Item 14. The search system according to Item 13. A computer comprising: an interface for inputting / outputting data; a processor connected to the interface; and one or more storage devices connected to the processor;
The storage device stores a plurality of first vector data each included in one of a plurality of clusters, and representative values for the clusters of the plurality of first vector data,
The method
When the search request including the second vector data is received, the representative value is searched using the received second vector data as a key,
A plurality of first vector data included in a first predetermined number of the clusters are searched in order from the cluster including the representative value that is close to the second vector data using the second vector data as a key. ,
A method of outputting, via the interface, a second predetermined number of the first vector data having a short distance from the second vector data among the searched first vector data.   The method according to claim 15, wherein each of the first vector data is included in the cluster including the representative value that is closest to the first vector data. The method
When a search request including the second vector data and information indicating the cluster for which the search for the first vector data has been completed using the second vector data as a key is received, other than the cluster indicated by the received information The representative value of the cluster of the second vector data as a key, and
Among the clusters other than the cluster indicated by the received information, a plurality of the clusters included in the first predetermined number of the clusters in order from the cluster including the representative value that is close to the second vector data. The method according to claim 15, wherein the first vector data is searched using the second vector data as a key.   16. The method according to claim 15, wherein the method outputs information indicating the cluster for which the search of the first vector data has been completed using the second vector data as a key. The method
When a search request including the second vector data and information indicating the cluster for which the search for the first vector data has been completed using the second vector data as a key is received, other than the cluster indicated by the received information The representative value of the cluster of the second vector data as a key, and
Among the clusters other than the cluster indicated by the received information, a plurality of the clusters included in the first predetermined number of the clusters in order from the cluster including the representative value that is close to the second vector data. 19. The method according to claim 18, wherein the first vector data is searched using the second vector data as a key. The one or more storage devices include a first storage device that stores the first vector data, and a second storage device that stores the representative value,
The first storage device is a disk storage device;
The method of claim 15, wherein the second storage device is a randomly accessible storage device.

Images