JP6300982B2 - SEARCH DATA MANAGEMENT DEVICE, SEARCH DATA MANAGEMENT METHOD, AND SEARCH DATA MANAGEMENT PROGRAM - Google Patents

Description

  The present invention relates to a search data management device, a search data management method, and a search data management program.

  In the field of data search such as image search, data search is performed by constructing data having a graph structure in which search target data is virtually connected by connection elements and tracing the connection elements. The connection element is information indicating that two pieces of data are connected, and is referred to as an edge or a link (hereinafter referred to as an edge). The setting of the edge is performed according to a rule such that an object of data to be searched is first obtained and data close to each other is connected. An object is data whose distance can be defined. An object is typically represented by multidimensional vector data, and being close to an object is defined, for example, as a short distance between multidimensional vector data. As the distance between the multidimensional vector data, for example, the Lp norm obtained for the difference between the vector elements is used (p = 1, 2,...).

  In addition, there are directed edges and undirected edges. A directed edge is an edge that can trace data in only one direction, and an undirected edge is an edge that can trace data in both directions. A technique for performing a search using graph structure data (undirected graph) expressed by an undirected edge is disclosed (see Patent Document 1).

Japanese Patent No. 5208001

  When an undirected graph is used, since there are many patterns of search paths, a more comprehensive search can be performed. On the other hand, since there are many opportunities to perform a search using a useless route, the search accuracy over time is not always higher than when a directed graph is used.

  On the other hand, when a directed graph is used, data that is not referred to by other data may appear depending on how the graph is created. In this case, in the search process, there is a high possibility that the data cannot be reached, and an exhaustive search may not be performed.

  The present invention has been made in consideration of such circumstances, and a search data management device, a search data management method, and a search data management program capable of generating a directed graph that enables high-speed and high-precision search Is one of the purposes.

  One aspect of the present invention is a storage unit that stores a plurality of nodes to be searched for data, and data having a graph structure in which a directed edge is set for each neighboring node from each node stored in the storage unit. A primary graph generation unit that generates a certain primary graph and a transposed graph that is data of a graph structure in which the direction of the directed edge in the primary graph stored in the storage unit is reversed is generated as data for data search And a transposed graph generation unit.

  According to one embodiment of the present invention, it is possible to provide a search data management device, a search data management method, and a search data management program that can generate a directed graph that enables high-speed and highly accurate search.

It is a block diagram centering on the search data management apparatus 1 of embodiment. 2 is a diagram illustrating an example of a hardware configuration of a control unit 20. FIG. It is a figure which shows an example of the content of the existing data object. 4 is a diagram illustrating an example of the contents of a graph index 44. FIG. It is a flowchart which shows an example of the flow of a process by 26 A of primary graph production | generation parts. It is a figure which shows a mode that a near object is updated. It is a figure which shows a mode that the transposed graph Gr is produced | generated based on the primary graph G. FIG. It is a figure which shows a mode that the transposition graph Gr ⁺ is produced | generated based on the transposition graph Gr. It is a diagram showing how the transposition graph Gr ⁺⁺ is generated based on the transposed graph Gr ^+. It is a flowchart which shows an example of the flow of the process performed by the transposed graph production | generation part 26B. It is a figure which shows the result of the simulation which searches using each graph. It is a flowchart which shows an example of the process which produces | generates the undirected graph Ga. It is a flowchart which shows an example of the process which produces | generates the undirected graph Ga. It is a figure for demonstrating the content of the process of the index search part 24 which concerns on 2nd Embodiment.

  Hereinafter, embodiments of a search data management device, a search data management method, and a search data management program according to the present invention will be described with reference to the drawings.

<First Embodiment>
The first embodiment will be described below.
[overall structure]
FIG. 1 is a configuration diagram centering on a search data management apparatus 1 according to the embodiment. The search data management device 1 is connected to one or more client terminals CL via a network NW. The client terminal is a personal computer, a mobile phone such as a smartphone, a tablet terminal, or another terminal device. The network NW includes a wireless base station, a public line, a dedicated line, a provider terminal, the Internet, and the like. When the search data management device 1 receives the query data from the client terminal CL, the search data management device 1 searches for data similar to the query data and returns the search result to the client terminal CL. The data returned by the search data management device 1 may be the data itself (for example, image data generated by jpg or the like) or an identifier (URL or the like) for referring to the data. Further, the query data and the search target data may be any kind of data such as images, sounds, text data, and the like. In the following description, it is assumed that the search data management device 1 searches for images.

  The search data management device 1 includes, for example, a network interface 10, a control unit 20, an input / output device 30, and a data server 40. The network interface 10 is, for example, a NIC (Network Interface Card).

  The control unit 20 includes, for example, a data object generation unit 22, an index search unit 24, and a graph index editing unit 26. The graph index editing unit 26 includes a primary graph generation unit 26A and a transposed graph generation unit 26B. These components of the control unit 20 are realized, for example, when a processor such as a CPU (Central Processing Unit) executes a program. Some or all of these functional units may be realized by hardware such as LSI (Large Scale Integration), ASIC (Application Specific Integrated Circuit), FPGA (Field-Programmable Gate Array), or software. And hardware may be implemented in cooperation. The contents of processing by these functional units will be described later.

  FIG. 2 is a diagram illustrating an example of a hardware configuration of the control unit 20. The control unit 20 has, for example, a configuration in which a CPU 20A, a RAM (Random Access Memory) 20B, and a program memory 20C are connected by an internal bus. Various interfaces such as a network interface 10, an input / output interface, and a memory interface are connected to the internal bus. The RAM 20B stores data to be processed by the CPU 20A, data of processing results, and the like. The program memory 20C includes a part or all of a storage device such as a ROM (Read Only Memory), a HDD (Hard Disk Drive), and a flash memory. The program memory 20C stores programs such as a data object generation program 20Ca, an index search program 20Cb, and a graph index editing program 20Cc. These programs do not need to be clearly separated, and some or all of them may be shared.

  Returning to FIG. 1, the input / output device 30 includes an input device such as a mouse, a keyboard, and a touch panel that accepts an input operation by an administrator of the search data management device 1, an LCD (Liquid Crystal Display), an organic EL (Electroluminescence) display device, Output devices such as speakers.

  The data server 40 is realized by a storage device such as an HDD or a flash memory. The data server 40 may be shared with the program memory 20C of the control unit 20, or may be realized by a storage device separate from the program memory 20C. The data server 40 may be realized by an external storage device such as a NAS (Network Attached Storage) device that can be accessed from the search data management device 1 via various networks. In this case, the “storage unit” in the claims may be interpreted to indicate the RAM 20B in which data acquired from the data server 40 is temporarily stored.

[Control unit]
Hereinafter, the contents of processing by each functional unit of the control unit 20 will be described. Note that the control unit 20 does not need to be realized by a single processor, and may perform distributed processing for each function. For example, the data object generation unit 22, the index search unit 24, and the graph index editing unit 26 may be realized by separate processors.

  The data object generation unit 22 generates an input data object based on the input data received from the client terminal CL or the like. When the input data is an image, the object is, for example, a local feature amount, BoF (Bag of Features), a color histogram, or a combination thereof. In addition, when the input data is text data, the object is, for example, vector data on the appearance frequency of words, a semantic vector extracted using a neural network, or a vector based on the frequency or other relative relation that appears together with other words. Etc. An object is an example of a “node” that is a target of data search.

  The index search unit 24 searches the data server 40 using the object (hereinafter referred to as a new object) generated by the data object generation unit 22 as query data, and extracts an object similar to the new object from the existing data object 42. . For example, an existing data object 42 and a graph index 44 are stored in the data server 40.

  The existing data object 42 is data of an object generated in advance from data to be searched. The existing data object 42 is associated with data used to generate the existing data object 42 or an identifier that refers to the data. The search data management device 1 transmits data associated with an existing object obtained by using a new object as a query, that is, data associated with an object similar to the new object, or an identifier referring to the data to the client terminal CL. FIG. 3 is a diagram illustrating an example of the contents of the existing data object 42. As shown in the figure, the existing data object 42 refers to the object identification information (object ID in the figure), the object (vector data in the figure), and the data or data from which the object is generated. Data associated with the identifier to be associated.

  The graph index 44 is information regarding edges connecting a plurality of objects, and is data having a graph structure formed by a set of directed edges connecting a reference source object and a reference destination object. FIG. 4 is a diagram illustrating an example of the contents of the graph index 44.

  The graph index 44 is, for example, a reference source object ID that is identification information of a reference source object, a reference destination object ID that is identification information of a reference destination object, and an edge that is identification information of a directed edge connecting them Information such as the ID and the distance between the reference source object and the reference destination object is associated. If the object is a vector, their distance is defined as, for example, the Lp norm for the difference between vector elements (p = 1, 2,...). Note that the data structures shown in FIGS. 3 and 4 are merely examples, and other data structures may be employed. For example, the graph index 44 may be one in which other information is associated with the edge ID. In other words, the format of the data structure is not an essential problem in the present embodiment, and data of any data structure may be stored in the data server 40 as long as the distance is defined. The distance originally means that the distance axiom is satisfied, but may be a pseudo distance that does not satisfy the distance axiom. In the case of a pseudo distance, the search performance is lowered, but the pseudo distance may be used if there is a merit such as easy handling.

  Of the objects that can be traced according to the direction from the reference source object to the reference destination object by the edge defined by the graph index 44, the index search unit 24 selects an object within a predetermined distance from the new object. Extract as an object similar to a new object. In addition, the index search unit 24 uses a predetermined number in order from the shortest distance to the new object among the objects that can be traced according to the direction from the reference source object to the reference destination object by the edge defined by the graph index 44. These objects may be extracted as objects similar to the new object. Then, the index search unit 24 transmits the data associated with the extracted object in the existing data object 42 or its identifier to the client terminal CL via the network interface 10 and the network NW.

  Note that the search processing by the index search unit 24 is realized using, for example, the processing of the flowchart of FIG. In the flowchart of FIG. 13, an object set R obtained from a new object as an object y is an example of a search result by the index search unit 24. In this case, the number of objects included in the search result can be adjusted by adjusting the predetermined number ks to a desired value.

  With the functions of the data object generation unit 22 and the index search unit 24, the client terminal CL can acquire data similar to the transmitted data from the search data management device 1. Note that the role of the search data management apparatus 1 may be up to extracting an object similar to a new object. In this case, data corresponding to the extracted object or an identifier referring to the data is given to the client terminal CL. The transmission function may be provided by a device different from the search data management device 1.

  The primary graph generation unit 26 </ b> A of the graph index editing unit 26 generates a directed graph (primary graph) G that is the basis of the graph index 44. The primary graph generation unit 26A stores the primary graph in a storage unit such as the RAM 20B or the data server 40. In the following description, “the distance between the objects is short” and “the objects are close”, and “the distance between the objects is long” and “the object is far” have the same meaning.

  FIG. 5 is a flowchart illustrating an example of a flow of processing by the primary graph generation unit 26A. As a premise of the processing of this flowchart, it is assumed that object IDs 1 to n are assigned to objects included in the existing data object 42. Arguments i and j used in the flowchart are sequentially selected from 1 to n and executed. That is, the primary graph generation unit 26A first sets the argument i to 1, and repeatedly performs the processing of S100 to S106 until the argument j reaches n while incrementing the argument j one by one. Next, the primary graph generation unit 26A sets the argument i to 2, and repeats the processes of S100 to S106 until the argument j reaches n while incrementing the argument j one by one. This is repeated until the argument i reaches n.

  First, the primary graph generation unit 26A determines whether the object i (the object whose object ID is i; hereinafter the same) is an element of the neighborhood object set N (G, j) of the object j or i = j. Is determined (S100). The neighborhood object set N (G, j) of the object j is a set of objects that are selected by a predetermined number kp in order from the shortest distance when viewed from the object j (an example of the target node). Is a set of reference destination objects. Hereinafter, an edge having the object j as a reference source and an object included in the neighborhood object set N (G, j) as a reference destination may be referred to as an “edge given to the object j”. “G” is a code indicating data having a graph structure. Each of the objects that are elements of the neighborhood object set N (G, j) of the object j and the object j are connected by a directed edge. Therefore, at least an object that is an element of the neighborhood object set N (G, j) of the object j is an object that can be traced from the object j through one edge. Note that the object j may be an element of a neighboring object set N (G, u) of another object (for example, u) that is not an element of the neighboring object set N (G, j) of the object j. Hereinafter, this will be described on the assumption. When the object i is an element of the neighborhood object set N (G, j) of the object j, or when i = j, the processing of S102 to S106 is skipped.

  If the object i is not an element of the neighboring object set N (G, j) of the object j and i = j is not satisfied, the primary graph generation unit 26A sets the object i to the neighboring object set N (G, j) of the object j. It adds to an element (S102). Next, the primary graph generation unit 26A determines whether or not the number of objects that are elements of the neighborhood object set N (G, j) of the object j exceeds a predetermined number kp (S104). The predetermined number kp is an arbitrary natural number. For example, kp = 40. When the number of objects that are elements of the neighborhood object set N (G, j) of the object j exceeds the predetermined number kp, the primary graph generation unit 26A determines that the object j from the neighborhood object set N (G, j) of the object j Are excluded (S106).

  FIG. 6 is a diagram illustrating a state in which the neighborhood object set is updated. In the illustrated example, when the objects (1) to (3) were originally set in the neighborhood object set N (G, j) of the object j, the object i was added and the object (3) was excluded. . As a result, the neighborhood object set N (G, j) of the object j is updated to N (G, j) *. By repeating such processing, the neighborhood object set N (G, x) is set for all of the objects x = 1 to n. As a result, a directed graph (primary graph) G that is the basis of the graph index 44 is generated.

  The transposed graph generation unit 26B generates a transposed graph Gr in which the edge direction is reversed (that is, the reference source data and the reference destination data are switched) with respect to the primary graph G generated by the primary graph generation unit 26A. To do. FIG. 7 is a diagram illustrating how the transposed graph Gr is generated based on the primary graph G.

  Here, in the primary graph G, there is a possibility that “data that is not referred to by other data or that has very little reference source data” exists. On the other hand, in the transposed graph Gr, each data is guaranteed to be referred to from a predetermined number kp of data. As a result, search omissions can be eliminated.

Further, the transposed graph generation unit 26B may add a predetermined number kr (or a predetermined ratio) of edges in the opposite direction to the edges given to each object in the transposed graph. The predetermined number kr is a number smaller than the predetermined number kp, and as an example, kr = 20. Hereinafter, a result obtained by adding a predetermined number kr of opposite edges is referred to as a transposed graph Gr ⁺ . FIG. 8 is a diagram illustrating a state in which a transposed graph Gr ⁺ is generated based on the transposed graph Gr. In the figure, AE is an edge added to the transposed graph Gr.

Further, the transposed graph generation unit 26B sorts the edges given to each object in the order of length with respect to the transposed graph Gr ^{+ obtained by} adding a predetermined number kr of opposite edges, and the predetermined number km (or a predetermined ratio) in short order The long edge may be deleted while leaving the edge. As an example, km = 60. Hereinafter, a graph obtained by deleting a long edge while leaving a predetermined number of km edges in short order is referred to as a transposed graph Gr ⁺⁺ . Figure 9 is a diagram showing how the transposition graph Gr ⁺⁺ is generated based on the transposed graph Gr ^+. In the figure, an arrow indicated by a broken line is an edge deleted from the transposed graph Gr ⁺ . Note that the transposed graph generation unit 26B does not generate the transposed graph Gr ⁺ and sorts the edges assigned to the objects in the transposed graph Gr in the order of length, and leaves the predetermined number km of edges in the shortest order to generate long edges The transposed graph Gr ⁺⁺ may be generated by deleting.

The graph index 44 illustrated in FIG. 1 is, for example, one of a transposed graph Gr, a transposed graph Gr ⁺ , and a transposed graph Gr ⁺⁺ .

FIG. 10 is a flowchart illustrating an example of a flow of processing executed by the transposed graph generation unit 26B. The process of this flowchart does not clearly separate the process shown in FIG. 8 and the process shown in FIG. 9 and includes these processes in the process for each object. The graph Gr ⁺⁺ is the same.

  First, the transposed graph generation unit 26B selects one edge from the primary graph stored in the RAM 20B or the data server 40 (S200), and switches the reference source and the reference destination (S202). Next, the transposed graph generation unit 26B determines whether or not all edges have been selected in S200 (S204). If all the edges have not been selected, the process returns to S200 and the next edge is selected. If all edges have been selected, the process proceeds to S206. Thereby, a transposed graph Gr is generated. The transposed graph G is stored in the RAM 20B or the data server 40.

  The transposed graph generation unit 26B selects one object in the transposed graph G (S206). Hereinafter, the object selected in S206 is referred to as a selected object. Next, the transposed graph generation unit 26B determines whether or not there is an edge given to the selected object (S208). The edge given to the selected object is an edge having the selected object as a reference source, as described above. If there is no edge given to the selected object, the transposed graph generation unit 26B gives a predetermined number of edges to the selected object (S210). For example, the transposed graph generation unit 26B selects a predetermined number of edges in order from the shortest edge among the edges having the selected object as a reference destination, and assigns edges opposite to these to the selected object. Note that the processing of S208 and S210 is not essential, and may be omitted when there is a low possibility that an object without an added edge will occur.

  Next, the transposed graph generation unit 26B sorts the edges given to the selected object in the order of length (S212), and adds reverse edges to the transposed graph G by a predetermined number kr in order from the shortest edge (S214). ). In addition, the transposed graph generation unit 26B performs deletion so as to leave a predetermined number of km edges in order from the longest edge (S216).

Then, the transposed graph generation unit 26B determines whether all objects have been selected in S206 (S218). If all the objects have not been selected, the process returns to S206 and the next object is selected. When all the objects have been selected, the process of this flowchart ends. As a result, a transposed graph Gr ⁺⁺ is generated. The transposed graph Gr ⁺⁺ is stored in the data server 40 as the graph index 44.

FIG. 11 is a diagram showing the results of a simulation for performing a search using each of the above graphs. This simulation is a simulation in which the local feature amount SIFT of an image is an object, and 20 neighboring objects are searched from 10 million SIFTs using the various graphs described above. As described above, this simulation was performed with kp = 40, kr = 20, and km = 60. FIG. 11 shows the relationship of accuracy with respect to search time as the simulation result. In the figure, the vertical axis represents accuracy (ratio of the number of correct answers in 20 cases), and the horizontal axis represents search time. For this reason, the simulation result is better as the characteristic line is biased to the upper left. As shown in the figure, the best simulation result was obtained when the transposed graph Gr ⁺⁺ was used, and then the transposed graph Gr ⁺ , the transposed graph Gr, and the primary graph G were in this order.

  According to the search data management apparatus 1 of the first embodiment described above, the transposed graph Gr, which is graph structure data in which the direction of the directed edge in the primary graph G is reversed, is generated as data for data search. Therefore, it is possible to generate a directed graph that enables a high-speed and highly accurate search.

Further, according to the search data management device 1 of the first embodiment, in the transposed graph Gr, the transposed graph Gr ⁺ is generated by adding a predetermined number kr of opposite edges to the edges given to each object. Thus, a directed graph that enables a faster and more accurate search can be generated.

Further, according to the search data management device 1 of the first embodiment, in the transposed graph Gr ⁺ , the edges assigned to each object are sorted in length order, and long edges are deleted while leaving a predetermined number of kilometers in short order. By generating the transposed graph Gr ⁺⁺ , it is possible to generate a directed graph that enables a faster and more accurate search.

  In the first embodiment (or in the second embodiment described later), the primary graph G is not directed to the undirected graph Ga generated by the processing described below, instead of the processing of the flowchart described in FIG. The edge may be regarded as two directed edges, and an upper limit is provided for the edge given to each object, and the portion exceeding the upper limit is reduced from the edge having a long distance.

  12 and 13 are flowcharts illustrating an example of processing for generating the undirected graph Ga. As a premise of the processing of this flowchart, it is assumed that object IDs 1 to m are assigned to the existing data object 42. The argument y used in the flowchart is selected in order from 1 to m and the process is executed. Here, the neighborhood object set N (G, y) is a set of objects that mutually refer to the object y.

  The primary graph generation unit 26A executes a K neighborhood search process (S300). The K neighborhood search process will be described with reference to FIG. As shown in FIG. 13, the primary graph generation unit 26A sets the radius r of the hypersphere to ∞ (infinity) (S400), and extracts the subset S from the existing object set (S402). The hypersphere is a virtual sphere indicating a search range (a range that can be included in the elements of the neighborhood object set N (G, y) of the input object y if the range is included). Note that the objects included in the object set S extracted in S402 may be included in the initial set of the object set R at the same time.

  Next, the primary graph generation unit 26A extracts the object having the shortest distance from the object y from the objects included in the object set S and sets it as the object s (S404). Next, the primary graph generation unit 26A excludes the object s from the object set S (S406).

  Next, the primary graph generation unit 26A determines whether or not the distance d (s, y) between the object s and the object y exceeds r (1 + ε) (S408). Here, ε is an expansion element, and r (1 + ε) is a search range (whether it is included in the elements of the neighborhood object set N (G, y) of the input object y for the neighborhood objects of the objects in the range) This is a value indicating the radius of the range in which to determine. When the distance d (s, y) between the object s and the object y exceeds r (1 + ε), the primary graph generation unit 26A outputs the object set R as a neighborhood object set N (G, y) of the object y ( S410), the process of the flowchart of FIG.

  When the distance d (s, y) between the object s and the object y does not exceed r (1 + ε), the primary graph generation unit 26A selects the object that is an element of the neighboring object set N (G, s) of the object s. Then, one object not included in the object set C is selected, and the selected object u is stored in the object set C (S412). The object set C is provided for convenience in order to avoid duplicate search, and is reset to an empty set when the flowchart of FIG. 13 is started.

  Next, the primary graph generation unit 26A determines whether or not the distance d (u, y) between the object u and the object y is equal to or less than r (1 + ε) (S414). When the distance d (u, y) between the object u and the object y is equal to or less than r (1 + ε), the primary graph generation unit 26A adds the object u to the object set S (S416).

  Next, the primary graph generation unit 26A determines whether or not the distance d (u, y) between the object u and the object y is equal to or less than r (S418). If the distance d (u, y) between the object u and the object y exceeds r, the process proceeds to S430.

  When the distance d (u, y) between the object u and the object y is equal to or less than r, the primary graph generation unit 26A adds the object u to the object set R (S420).

  Then, the primary graph generation unit 26A determines whether or not the number of objects included in the object set R exceeds ks (S422). The predetermined number ks is a natural number that is arbitrarily determined. For example, ks = 3.

  When the number of objects included in the object set R exceeds ks, the primary graph generation unit 26A excludes the object having the longest distance from the object y from the object set R among the objects included in the object set R (S424). ).

  Next, the primary graph generation unit 26A determines whether or not the number of objects included in the object set R matches ks (S426). When the number of objects included in the object set R coincides with ks, the primary graph generation unit 26A determines the distance between the object with the longest distance from the object y and the object y among the objects included in the object set R. A new r is set (S428).

  Then, the primary graph generation unit 26A determines whether all objects have been selected from the objects that are elements of the neighboring object set N (G, s) of the object s and stored in the object set C (S430). . If all objects have not been selected from the objects that are elements of the neighboring object set N (G, s) of the object s and stored in the object set C, the process returns to S412.

  When all the objects are selected from the objects that are elements of the neighboring object set N (G, s) of the object s and stored in the object set C, the primary graph generation unit 26A determines that the object set S is an empty set. Is determined (S432). When the object set S is not an empty set, the process is returned to S404. When the object set S is an empty set, the primary graph generation unit 26A sets the object set R as a neighboring object set N (G, y) of the object y. To output the processing of the flowchart in FIG. 13 (S434).

  Returning to FIG. When the neighborhood object set N (G, y) of the object y is obtained, the primary graph generation unit 26A selects one object that is an element of the neighborhood object set N (G, y) of the object y, and the object z and (S302). Next, the primary graph generation unit 26A adds the object y as an element of the neighborhood object set N (G, z) of the object z (S304).

  Next, the primary graph generation unit 26A determines whether or not the number of objects that are elements of the neighborhood object set N (G, z) of the object z exceeds kp (S306). When the number of objects that are elements of the neighborhood object set N (G, z) of the object z exceeds the predetermined number kp, the primary graph generation unit 26A determines from the neighborhood object set N (G, z) of the object z that the object z Are excluded (S308).

  Then, the primary graph generation unit 26A determines whether or not all the objects z that are elements of the neighborhood object set N (G, y) of the object y have been selected (S310). If all the objects z that are elements of the neighboring object set N (G, y) of the object y have not been selected, the process returns to S302, and the objects that are elements of the neighboring object set N (G, y) of the object y If all z are selected, one loop of S300 to S308 is completed. Thereby, the undirected graph Ga is generated.

Second Embodiment
Hereinafter, a second embodiment will be described. In the second embodiment, the index search unit 24 performs the following process to reduce the number of objects to be searched and realize a faster search process.

  FIG. 14 is a diagram for explaining the processing contents of the index search unit 24 according to the second embodiment. This will be described with reference to the process of FIG. 13 that is also adopted as the process of the index search unit 24. In the figure, Q is an object corresponding to the query data, and O1 corresponds to the object u selected in S412 in the search process (process shown in FIG. 13). The distance D1 between the object u and the object Q has already been calculated at the time of S412. On the other hand, the objects O2, O3, and O4 are elements of the neighborhood object set N (G, u) of the object u. D0 is a virtual radius of the search range (r in S418) or a virtual radius of the search range (r (1 + ε) in S414) with the object Q as a reference. Similar to the description of FIG. 13, the search range is a range that is determined not to be similar to the query data unless it is within the range, and the search range is an object that is not within the range in the process of tracing the object. It is a range that is not referenced. Originally, the distance between the object Q and each of the objects O2, O3, and O4 is calculated and the determination process of S414 or S418 is performed. However, the determination process of S414 or S418 is not performed without calculating this distance. There is a state where it is possible to perform.

  In the state shown in FIG. 14, first, the distance between the object Q and the object O1 is calculated. Since distance D1> distance D0, it is determined that the data represented by the object O1 is not similar to the data represented by the object Q. Here, for each of the objects O2, O3, and O4, the distance from the object Q has not yet been calculated, but the distance between the object O1 and the object Q has been calculated.

  In this case, it is clear that the object O2 does not fall within the search range or the search range because [D2 <(D1-D0)]. Therefore, it is not necessary to calculate the distance between the object Q and the object O2, and it is determined that the data represented by the object O2 is not similar to the query data represented by the object Q.

  Since the object O3 is [D3> (D1-D0)], there is a possibility of entering the search range or the search range. Accordingly, the distance between the object Q and the object O3 is calculated, and it is determined whether or not the data represented by the object O3 is similar to the query data represented by the object Q.

  It is clear that the object O4 does not fall within the search range or the search range because [D4> (D1 + D0)]. Accordingly, without calculating the distance between the object Q and the object O4, it is determined that the data represented by the object O4 is not similar to the query data represented by the object Q.

  As described above, the index search unit 24 according to the second embodiment calculates the distance of an object (O1 in FIG. 14) from the object representing the query data, and may not enter the search range or the search range. If it is found, only objects included in the range A0 or A1 in the figure are subject to distance calculation, and objects that are clearly included in A2 or A3 are rejected without being subject to distance calculation. As a result, a higher-speed search process can be realized.

  According to the search data management device 1 of the second embodiment described above, a higher-speed search process can be realized.

In the case of executing the processing of the second embodiment, by obtaining the transposed graph Gr ^+, it can exert transposed graph Gr ⁺⁺ and comparable performance in the first embodiment.

  As mentioned above, although the form for implementing this invention was demonstrated using embodiment, this invention is not limited to such embodiment at all, In the range which does not deviate from the summary of this invention, various deformation | transformation and substitution Can be added.

DESCRIPTION OF SYMBOLS 1 ... Search data management apparatus, 10 ... Network interface, 20 ... Control part, 22 ... Data object generation part, 24 ... Index search part, 26 ... Graph index edit part, 26A ... Primary graph generation part, 26B ... Transposed graph generation part , 30 ... I / O device, 40 ... Data server, 42 ... Existing data object, 44 ... Graph index

Claims (10)

A storage unit for storing a plurality of nodes to be searched;
A primary graph generating unit that generates a primary graph that is data of a graph structure in which a directed edge is set with respect to neighboring nodes from each node stored in the storage unit;
A transposed graph generating unit that generates a transposed graph, which is data of a graph structure in which the direction of the directed edge in the primary graph stored in the storage unit is reversed, as data for data search;
A search data management device comprising: The primary graph generation unit selects data of a graph structure in which a predetermined number of nodes are selected in order of short distance from the target node, and directed edges are set for the predetermined number of selected nodes from the target node. Generating as the primary graph,
The search data management device according to claim 1. The primary graph generation unit regards undirected edges as two directed edges for data having a graph structure in which undirected edges are set for a plurality of nodes, and determines the edges from each node toward another node . Each of the numbers has an upper limit, and the linear graph is generated by reducing the amount exceeding the upper limit in order from the edge having a long distance,
The search data management device according to claim 1. The transposed graph generation unit generates a graph obtained by adding a predetermined number or a predetermined ratio of edges opposite to the edge for each node to which an edge is given as the transposed graph that is data for data search. ,
The search data management device according to any one of claims 1 to 3. The transposition graph generation unit for each node that has been granted edges, the graph deleting the granted edges as Tokoro constant or a predetermined ratio of the edge remains in the ascending order is the data for data retrieval Generating as the transposed graph ,
The search data management device according to any one of claims 1 to 4. A search unit that searches for data similar to the query data by calculating a distance between a query object obtained from query data and an object corresponding to a node included in the transposed graph;
A search range based on the query object or a virtual radius of the search range; a first distance between the first object corresponding to the first node included in the transposed graph and the query object; The similarity between the second node and the query data is determined based on the relationship between the second object and the second distance corresponding to the second node included in the transposed graph. A search unit for determining whether or not to
The search data management device according to any one of claims 1 to 5. In the case where the first object is not similar to the query object, the search unit determines that the second distance when the distance obtained by subtracting the virtual radius from the first distance is larger than the second distance. Decide not to determine the similarity between the node and the query data;
The search data management apparatus according to claim 6. In the case where the first object is not similar to the query object, the search unit adds the first radius to the first distance and the second distance is smaller than the second distance. Decide not to determine the similarity between the node and the query data;
The search data management device according to claim 6 or 7. Computer
Generate a primary graph that is data of a graph structure in which a directed edge is set for a neighboring node from each node included in a plurality of nodes to be searched for data,
Generating a transposed graph, which is data of a graph structure in which the direction of the directed edge in the generated primary graph is reversed, as data for data search;
Search data management method. On the computer,
Generate a primary graph that is data of a graph structure in which a directed edge is set for a neighboring node from each node included in a plurality of nodes to be searched for data,
Generating a transposed graph, which is data of a graph structure in which the direction of the directed edge in the generated primary graph is reversed, as data for data search;
Search data management program.

Images