[0001]The present invention relates to the management of tree structure data.
Background technology
[0002]Tree structure data is one of the data structures for managing data. For example, tree-structured data is used as an index tree in a database. For example, Patent Document 1 discloses a similarity tree in which feature data is treated as an element and the arrangement of each element is determined based on the similarity of the feature data.
Prior art literature
Patent documents
[0003]
Patent Document 1: International Publication No. 2014/109127
Outline of the invention
Problems to be solved by the invention
[0004]
　The present inventor has found that when dealing with a set as an element of tree structure data, it is necessary to devise the insertion of the element into the tree structure data. The present invention has been made in view of this problem, and one of the objects thereof is to provide a technique for appropriately inserting an element in a tree structure data having a set as an element.
Means to solve problems
[0005]
　The data management device of the present invention has a first storage area for storing tree structure data which is tree structure data having a data set as a node, and a second storage area for storing data sets not included in the tree structure data. Is accessible to.
　The data management device 1) acquires the data to be inserted into the data set, inserts the acquired data into the data set already stored in the first storage area or the second storage area, or inserts a new data set. In the data insertion unit that generates data in the second storage area and inserts the acquired data into the data set, and 2) If the predetermined conditions for the data set stored in the second storage area are satisfied, the second storage area It has a set insertion unit that inserts one or more of the data sets stored in the tree structure data into the tree structure data.
[0006]
　The control method of the present invention is executed by a computer. The computer accesses a first storage area for storing tree-structured data, which is tree-structured data having a data set as a node, and a second storage area for storing data sets not included in the tree-structured data. It is possible.
　The control method is as follows: 1) Acquire the data to be inserted into the data set, insert the acquired data into the data set already stored in the first storage area or the second storage area, or insert a new data set. When the data insertion step of generating the data in the second storage area and inserting the acquired data into the data set and 2) the predetermined conditions for the data set stored in the second storage area are satisfied, the data set is stored in the second storage area. It has a set insertion step that inserts one or more of the stored data sets into the tree structure data.
[0007]
　The program of the present invention causes a computer to execute each step of the control method of the present invention.
The invention's effect
[0008]
　According to the present invention, there is provided a technique for appropriately inserting an element in a tree structure data having a set as an element.
A brief description of the drawing
[0009]
　The above-mentioned objectives and other objectives, features and advantages are further clarified by the preferred embodiments described below and the accompanying drawings below.
[0010]
[Fig. 1] Fig. 1 is a diagram for explaining an outline of the data management device of the present embodiment.
FIG. 2 is a diagram illustrating a functional configuration of the data management device of the first embodiment.
[Fig. 3] Fig. 3 is a diagram illustrating a computer for realizing a data management device.
FIG. 4 is a flowchart illustrating a flow of processing executed by the data management apparatus of the first embodiment.
[Fig. 5] Fig. 5 is a diagram illustrating a more specific usage scene of a data management device.
[Fig. 6] Fig. 6 is a diagram illustrating tree structure data realized as a similarity tree.
Embodiment for carrying out the invention
[0011]
　Hereinafter, embodiments of the present invention will be described with reference to the drawings. In all drawings, similar components are designated by the same reference numerals, and the description thereof will be omitted as appropriate. Further, in each block diagram, unless otherwise specified, each block represents a configuration of a functional unit rather than a configuration of a hardware unit.
[0012]
[Embodiment 1]

　FIG. 1 is a diagram for explaining an outline of the data management device 2000 of the present embodiment. Note that FIG. 1 is an example for facilitating the understanding of the data management device 2000, and the functions of the data management device 2000 are not limited to those shown in FIG.
[0013]
　The data management device 2000 manages the tree structure data 10, which is the tree structure data. For example, the data management device 2000 inserts data into the tree structure data 10. The tree structure data 10 has a tree structure formed by a plurality of nodes 12. For example, the tree structure data 10 has a similarity tree structure disclosed in International Publication No. 2014/109127.
[0014]
　The tree structure data 10 has a data set 20 as a node. The data set 20 is a set containing one or more data 40. Any kind of data can be adopted as the data 40. For example, as the data 40, image features (features on the image) of an object such as a person extracted from a moving image frame can be adopted. It is preferable that one data set 20 contains data 40 similar to each other. For example, it is assumed that the image feature of the object is used as the data 40. In this case, a plurality of image features obtained from the same object are gathered in one data set 20.
[0015]
　The tree structure data 10 is stored in the first storage area 50. The first storage area 50 is a storage area of ​​a part or all of any storage device. Further, the first storage area 50 may be configured by a plurality of storage devices. Further, a second storage area 60 is also prepared as another storage area for storing the data set 20 that does not constitute the tree structure data 10. The second storage area 60, like the first storage area 50, is also a part or all of the storage area of ​​any storage device. Further, the second storage area 60 may be configured by a plurality of storage devices. The same storage device may be used for the first storage area 50 and the second storage area 60, or different storage devices may be used.
[0016]
　When the data management device 2000 acquires the new data 40 to be managed, the data management device 2000 inserts the data 40 into any one of the existing data sets 20 or generates a new data set 20 in the second storage area 60. Then, the data 40 is inserted into the second storage area 60. Further, the data management device 2000 is one of the data sets 20 stored in the second storage area 60 when a predetermined condition is satisfied for the data set 20 stored in the second storage area 60. The above is inserted into the tree structure data 10. By being inserted into the tree structure data 10, the data set 20 is stored in the first storage area 50 instead of the second storage area 60. Hereinafter, the predetermined condition described above is referred to as an insertion condition.
[0017]

　When an element (corresponding to data 40) is inserted into the data of a tree structure, an appropriate position in the tree structure is determined according to the nature of the element, and the element is determined at that position. Is inserted. In addition, the tree structure will be reconstructed as needed.
[0018]
　However, when a data set is treated as an element, it is difficult to determine an appropriate position of the data set immediately after the data set is generated. Because, while there is little data in the data set or the data set is updated frequently, the properties of the data set (for example, the mean or distribution of the data contained in the data set) are newly inserted. This is because it may change significantly under the influence of data. If the data set cannot be inserted at an appropriate position, the performance of subsequent data retrieval may deteriorate.
[0019]
　According to the data management device 2000 of the present embodiment, the data set 20 has tree-structured data according to the condition that the insertion condition (a predetermined condition for the data set 20 stored in the second storage area 60) is satisfied. It is inserted in 10. In other words, the data set 20 is not inserted into the tree structure data 10 immediately after being generated, but is temporarily stored in the second storage area 60. Therefore, after the position in the tree structure data 10 can be appropriately determined by setting an appropriate insertion condition so that the property of the data set 20 is satisfied to some extent, the data set 20 becomes the tree structure data 10. Will be inserted in. Therefore, in the tree structure data that treats a set of data as an element, the element can be inserted at an appropriate position. As a result, for example, it is possible to improve the performance of data retrieval using the tree structure data 10.
[0020]
　Hereinafter, the present embodiment will be described in more detail.
[0021]

　FIG. 2 is a diagram illustrating the functional configuration of the data management device 2000 of the first embodiment. The data management device 2000 has access to the first storage area 50 and the second storage area 60. Further, the data management device 2000 has a data insertion unit 2020 and a set insertion unit 2040. The data insertion unit 2020 acquires the data 40. Further, the data insertion unit 2020 1) inserts the data 40 into the data set 20 already stored in the first storage area 50 or the second storage area 60, or 2) inserts a new data set 20. 2 Generated in the storage area 60, and inserts the data 40 into the data set 20. When the insertion condition is satisfied, the set insertion unit 2040 inserts one or more of the data sets 20 stored in the second storage area 60 into the tree structure data 10.
[0022]
Each functional component of the data management device 2000 may be realized by hardware (eg, hard-wired electronic circuit, etc.) that realizes each functional component. , May be realized by a combination of hardware and software (eg, a combination of an electronic circuit and a program that controls it). Hereinafter, a case where each functional component of the data management device 2000 is realized by a combination of hardware and software will be further described.
[0023]
　FIG. 3 is a diagram illustrating a computer 1000 for realizing the data management device 2000. The computer 1000 is an arbitrary computer. For example, the computer 1000 is an arbitrary computer. For example, the computer 1000 is a stationary computer such as a server machine or a PC (Personal Computer). In addition, for example, the computer 1000 may be a portable computer such as a smartphone or a tablet terminal.
[0024]
　The computer 1000 may be a dedicated computer designed to realize the data management device 2000, or may be a general-purpose computer. When the computer 1000 is a general-purpose computer, it is preferable to install a predetermined program on the computer 1000 so that the computer 1000 functions as a data management device 2000.
[0025]
　The computer 1000 includes a bus 1020, a processor 1040, a memory 1060, a storage device 1080, an input / output interface 1100, and a network interface 1120. The bus 1020 is a data transmission path for the processor 1040, the memory 1060, the storage device 1080, the input / output interface 1100, and the network interface 1120 to transmit and receive data to and from each other. However, the method of connecting the processors 1040 and the like to each other is not limited to the bus connection.
[0026]
　The processor 1040 is various processors such as a CPU (Central Processing Unit), a GPU (Graphics Processing Unit), and an FPGA (Field-Programmable Gate Array). The memory 1060 is a main storage device realized by using RAM (Random Access Memory) or the like. The storage device 1080 is an auxiliary storage device realized by using a hard disk, an SSD (Solid State Drive), a memory card, a ROM (Read Only Memory), or the like.
[0027]
　The input / output interface 1100 is an interface for connecting the computer 1000 and the input / output device. For example, an input device such as a keyboard and an output device such as a display device are connected to the input / output interface 1100.
[0028]
　The network interface 1120 is an interface for connecting the computer 1000 to the network. The method of connecting the network interface 1120 to the network may be a wireless connection or a wired connection.
[0029]
　The computer 1000 is connected to the first storage area 50 and the second storage area 60 via the network interface 1120. However, the method of connecting the computer 1000 to the first storage area 50 and the second storage area 60 is not limited to the method via the network interface 1120. For example, the first storage area 50 and the second storage area 60 may be connected to the computer 1000 via the input / output interface 1100. Further, the first storage area 50 and the second storage area 60 may be provided inside the computer 1000 (for example, inside the storage device 1080).
[0030]
　The storage device 1080 stores a program module that realizes each functional component of the data management device 2000. The processor 1040 reads each of these program modules into the memory 1060 and executes them, thereby realizing the functions corresponding to each program module.
[0031]

　FIG. 4 is a flowchart illustrating a processing flow executed by the data management device 2000 of the first embodiment. The data insertion unit 2020 acquires the data 40 (S102). The data insertion unit 2020 determines whether or not the data set 20 into which the data 40 is to be inserted exists in the data set 20 already stored in the first storage area 50 or the second storage area 60 (S104). ). When there is a data set 20 into which the data 40 is to be inserted (S104: YES), the data insertion unit 2020 inserts the data 40 into the data set 20 (S106). On the other hand, when the data set 20 into which the data 40 is to be inserted does not exist (S104: YES), the data insertion unit 2020 generates a new data set 20 in the second storage area 60, and the data is stored in the data set 20. 40 is inserted (S108).
[0032]
　The set insertion unit 2040 determines whether or not the insertion condition is satisfied (S110). If the insertion condition is not satisfied (S110: NO), the process of FIG. 4 ends. On the other hand, when the insertion condition is satisfied (S110: YES), the set insertion unit 2040 converts any one or more of the data sets 20 stored in the second storage area 60 into the tree structure data 10. Insert (S112).
[0033]

　FIG. 5 is a diagram illustrating a more specific usage scene of the data management device 2000. In this example, the information indicating the image characteristics of the object detected from the moving image data is treated as the data 40. Hereinafter, a more specific description will be given.
[0034]
　The analysis device 120 acquires the moving image data 112 generated by the camera 110, and performs image analysis on each moving image frame 114 constituting the moving image data 112. More specifically, the analysis device 120 detects an object from the moving image frame 114 and generates detection information which is information about the object. For example, the detection information is information including the detection time (the generation time of the moving image frame), the position of the object on the moving image frame 114, and the image feature of the object. The detection information is generated for each object detected from the moving image frame 114.
[0035]
　The analysis device 120 transmits the detection information to the data management device 2000. The data management device 2000 (data insertion unit 2020) acquires this detection information as data 40. The data management device 2000 manages the data 40 so that the data 40 for the same object is included in the same data set 20. The detection information acquired by the data management device 2000 as the data 40 may be limited to that for a specific type of object (for example, a human).
[0036]
　The data management device 2000 manages the data 40 so that a plurality of data 40 similar to each other are included in the same data set 20. Here, when the above-mentioned detection information is treated as the data 40, the similarity between the data 40s is calculated based on the image features indicated by the detection information. By doing so, it is possible to manage the detection information, which is information about the object extracted from the moving image data 112, so that those having similar image features are included in the same data set 20. That is, a plurality of image features obtained for the same person can be collected and managed in the same data set 20.
[0037]
　By managing the data in this way, for example, a person having the image feature can be found from the data managed by the data management device 2000 by a search by a search query including the image feature. The details of the data search will be described later.
[0038]
The
　data insertion unit 2020 acquires the data 40 to be inserted into the data set 20 (S102). Here, there are various methods for acquiring the data 40. For example, as illustrated in the above-mentioned usage scene, the data insertion unit 2020 acquires the data 40 by receiving the data 40 transmitted from another device. In addition, for example, the data insertion unit 2020 acquires the data 40 stored in the storage area by accessing the storage areas other than the first storage area 50 and the second storage area 60. For example, in the above-mentioned usage scene, a storage device shared by the analysis device 120 and the data management device 2000 is provided so that the analysis device 120 stores the detection information in the storage device. Then, the data insertion unit 2020 acquires the detection information stored in this storage device as the data 40. In addition, for example, the data insertion unit 2020 may acquire the data 40 input by the user.
[0039]
The
　data insertion unit 2020 determines whether or not there is a data set 20 into which the acquired data 40 should be inserted (S104). .. Various criteria can be used for this determination.
[0040]
　For example, for the existing data set 20, the representative data of the data set 20 is calculated in advance. For example, the representative data of the data set 20 is a statistical value (average value, etc.) of the data included in the data set 20. When the data 40 is vector data, the representative data is also vector data (for example, an average vector).
[0041]
　The data insertion unit 2020 identifies from the existing data set 20 that the similarity between the data 40 and its representative data is equal to or higher than a predetermined threshold value. For the similarity between data, for example, a value that increases as the norm between data becomes smaller (for example, the reciprocal of the norm) can be used. Any kind of norm (L1 norm, L2 norm, etc.) can be adopted as this norm.
[0042]
　When the existing data set 20 has a similarity with the data 40 of a predetermined threshold value or more, the data insertion unit 2020 uses the data set 20 as the data set 20 into which the data 40 should be inserted. Identify. On the other hand, when there is no existing data set 20 having a similarity with the data 40 equal to or higher than a predetermined threshold value, the data insertion unit 2020 determines that the data set 20 into which the data 40 should be inserted does not exist. do.
[0043]
　It is preferable that the search for data having a similarity to the data 40 having a degree of similarity equal to or higher than a predetermined threshold value is given priority over the tree structure data 10. This is because the data has a tree structure, so the search can be performed at high speed. The search for the tree structure data 10 can be performed according to an algorithm predetermined according to the type of the tree structure data 10. Hereinafter, the search for the similarity tree will be described as an example.
[0044]
　FIG. 6 is a diagram illustrating the tree structure data 10 realized as a similarity tree. In FIG. 6, the tree structure data 10 is a three-level similarity tree. From top to bottom, they are called the first layer, the second layer, and the third layer. In the third layer, all the data sets 20 inserted in the tree structure data 10 are arranged. In the second layer, one of a plurality of data sets 20 immediately below the data set 20 is arranged. Similarly, in the third layer, one of a plurality of data sets 20 immediately below the third layer is arranged.
[0045]
　Here, a data set 20 having a low degree of similarity to each other is arranged on the first layer. On the other hand, in the second layer, a plurality of data sets 20 having a medium degree of similarity to each other are arranged directly under the same data set 20. Further, in the third layer, a plurality of data sets 20 having high similarities to each other are arranged directly under the same data set 20.
[0046]
　First, the data insertion unit 2020 identifies the data set 20 showing the representative data having the highest degree of similarity to the data 40 from the data set 20 of the first layer. Further, the data insertion unit 2020 identifies the data set 20 showing the representative data having the highest degree of similarity to the data 40 from the data set 20 of the second layer directly under the specified data set 20. Further, the data insertion unit 2020 identifies the data set 20 having the highest degree of similarity to the data 40 from the data set 20 of the third layer directly under the specified data set 20. By comparing the data 40 and the data set 20 in this order, the data set 20 having the maximum similarity with the data 40 is specified by the number of comparisons equal to the depth of the hierarchy (three times in this example). can do.
[0047]
　When the similarity between the finally specified data set 20 and the data 40 is equal to or higher than a predetermined threshold value, the data insertion unit 2020 specifies the data set 20 as the data set 20 into which the data 40 should be inserted. On the other hand, when the similarity between the finally specified data set 20 and the data 40 is less than a predetermined threshold value, the data insertion unit 2020 inserts the data set 20 into the tree structure data 10. Judge that it does not exist.
[0048]
　If it is determined that the data set 20 into which the data 40 is to be inserted does not exist in the tree structure data 10, the data insertion unit 2020 represents the representative data and the data 40 of each data set 20 stored in the second storage area 60. Make a comparison with. If there is a data set 20 in the second storage area 60 whose similarity with the data 40 is equal to or higher than a predetermined threshold value, the data insertion unit 2020 inserts the data set 20 into the data set 20 into which the data 40 is to be inserted. Specify as. On the other hand, if there is no data set 20 in the second storage area 60 whose similarity with the data 40 is equal to or higher than a predetermined threshold value, the data insertion unit 2020 may use the data 40 in the second storage area 60. It is determined that the data set 20 to be inserted does not exist. In this case, neither the first storage area 50 nor the second storage area 60 has a data set 20 into which the data 40 should be inserted.
[0049]

　When there is a data set 20 into which the data 40 should be inserted (S104: YES), the data insertion unit 2020 inserts the data 40 into the data set 20. (S106). An existing technique can be used as a technique for inserting new data into a set of data.
[0050]
　Here, when the data 40 is inserted into the tree structure data 10, it may be necessary to reconstruct (change the structure) the tree structure data 10. For example, when the position of each data set 20 in the tree structure data 10 is determined based on the representative data of the data set 20, each data set 20 is changed by changing the representative data of the data set 20 into which the data 40 is inserted. The proper placement of can change.
[0051]
　In such a case, the data management device 2000 may or may not reconstruct the tree structure data 10. It should be noted that existing techniques can be used as techniques for reconstructing the tree structure in response to the addition of elements to the tree structure data.
[0052]
When the
　data set 20 into which the data 40 is to be inserted does not exist (S104: NO), the data insertion unit 2020 stores the new data set 20 in the second storage. The data 40 is inserted into the generated data set 20 generated in the region 60 (S108). Here, an existing technique can be used as a technique for generating a new data set in a specific storage area and inserting data into the data set.
[0053]
The
　set insertion unit 2040 determines whether or not the insertion condition is satisfied (S110). When the insertion condition is satisfied, the set insertion unit 2040 inserts one or more of the data sets 20 stored in the second storage area 60 into the tree structure data 10 (S112). That is, the insertion condition is a condition that triggers the addition of the data set 20 managed outside the tree structure data 10 to the tree structure data 10.
[0054]
　Here, it is assumed that the data set 20 in which the data 40 is inserted by the data insertion unit 2020 is the data set 20 included in the tree structure data 10. In this case, there is no change in the data set 20 stored in the second storage area 60. Therefore, it is considered that the insertion condition is not satisfied. Therefore, when the data set 20 in which the data 40 is inserted by the data insertion unit 2020 is the data set 20 included in the tree structure data 10, the data insertion unit 2020 determines whether or not the insertion condition is satisfied. The determination may not be performed (the processing of the flowchart of FIG. 4 may be terminated without executing S110).
[0055]
　Various conditions can be adopted as the insertion conditions. For example, the insertion condition is a condition that the size of the data set 20 of a certain data set 20 stored in the second storage area 60 is equal to or larger than the threshold value. Further, instead of the size of the data set 20, the number of data included in the data set 20 may be used. The threshold value is stored in advance in a storage device accessible from the set insertion unit 2040.
[0056]
　When this insertion condition is satisfied, the set insertion unit 2040 inserts the data set 20 having a size or the number of data equal to or larger than the threshold value into the tree structure data 10. The data set 20 whose size and number change by inserting the data 40 is the data set 20 in which the data 40 is inserted by the data insertion unit 2020. Therefore, when the above insertion condition is adopted, the set insertion unit 2040 compares the size and the number of data with the threshold value for the data set 20 into which the data 40 is inserted by the data insertion unit 2020, and if it is equal to or more than the threshold value, The data set 20 is inserted into the tree structure data 10.
[0057]
　In addition, for example, the insertion condition is a condition that the variance of the data 40 contained in a certain data set 20 stored in the second storage area 60 is equal to or less than a predetermined threshold value. When this insertion condition is adopted, the set insertion unit 2040 inserts the data set 20 in which the variance of the data 40 is equal to or less than a predetermined threshold value into the tree structure data 10. The data set 20 in which the variance of the data 40 changes by inserting the data 40 is the data set 20 in which the data 40 is inserted by the data insertion unit 2020. Therefore, even when this insertion condition is adopted, the set insertion unit 2040 calculates the distribution of the data 40 contained in the data set 20 into which the data 40 is inserted by the data insertion unit 2020, and the calculated distribution is calculated. If it is equal to or less than the threshold value, the data set 20 is inserted into the tree structure data 10.
[0058]
　However, when the amount of data 40 contained in the data set 20 is small, the value of the variance of the data 40 contained in the data set 20 is likely to change due to the influence of the newly inserted data 40. Therefore, the insertion condition is that both the condition that "the variance of the data 40 contained in the data set 20 is equal to or less than a predetermined threshold value" and the condition that "the number of data sets 20 is equal to or greater than the threshold value" are satisfied. May be. For example, the set insertion unit 2040 first determines whether or not the number of data 40 included in the data set 20 of the data set 20 into which the data 40 is inserted is equal to or larger than the threshold value. If it is determined that the number of data sets 20 is equal to or greater than the threshold value, the set insertion unit 2040 further determines whether or not the variance of the data 40 included in the data set 20 is equal to or less than the threshold value. Then, when it is determined that the variance of the data 40 included in the data set 20 is equal to or less than the threshold value, the set insertion unit 2040 inserts the data set 20 into the tree structure data 10.
[0059]
　In addition, for example, in the insertion condition, the number of data sets 20 stored in the second storage area 60 is equal to or larger than the threshold value, and the total size of the data sets 20 stored in the second storage area 60 is set. It can be adopted that the value is equal to or higher than the threshold value. When adopting these insertion conditions, the set insertion unit 2040 inserts one data set 20 to be inserted into the tree structure data 10 from the data sets 20 stored in the second storage area 60 based on the selection rule. Select the above. The selection rule is a rule that serves as a reference for selecting the data set 20 to be inserted into the tree structure data 10.
[0060]
　Here, it is preferable that the data set 20 inserted in the tree structure data 10 has a low probability that its properties will change in the future. This is because the insertion position of the data set 20 in the tree structure data 10 is determined by the property of the data set 20 (for example, representative data, data distribution, etc.), and if the property changes in the future, the tree structure data 10 will have the insertion position. This is because there is a high possibility that the position of the data set 20 will not be an appropriate position. In other words, if the probability that the properties of the data set 20 will change in the future is low, the insertion position of the data set 20 determined based on the properties of the current data set 20 is likely to continue to be an appropriate position for the data set 20 in the future. Can be said to be high. Although it is possible to reconstruct the tree structure data, it is preferable to reduce the frequency of reconstruction to reduce the calculation cost, so it can be said that the appropriateness of the insertion position is important.
[0061]
　Examples of the selection rule that realizes the selection of the data set 20 whose properties are unlikely to change in the future include the following rules.
(1) Select the data set 20 within the predetermined order in descending order of the number of data 40
(2) Select the data set 20 within the predetermined order in descending order of size
(3) The time when the data set is generated is early. Select the data set 20 that is within the predetermined order in order (4) Select the data set 20 that is within the
predetermined order in the order of the earliest last update
(5) The data 40 is specified in ascending order of dispersion size. Select the data set 20 that is within the rank
(6) Select the data set 20 that is within the predetermined rank in descending order of the scores calculated using multiple indicators.
[0062]
　Hereinafter, each of the above six examples will be described.
[0063]
<< About (1) >>
　The set insertion unit 2040 selects a data set 20 that is within a predetermined order in descending order of the number of data 40s. For example, assume that the predetermined rank is 2. In this case, the set insertion unit 2040 is a data set 20 having the largest number of data 40s among the data sets 20 stored in the second storage area 60, and a data set having the next largest number of data 40s. Select 20.
[0064]
　Here, it can be said that the larger the number of data 40 included in the data set 20, the higher the probability that the properties of the data set 20 are sufficiently expressed by the data 40. Therefore, by preferentially inserting the data set 20 having a large number of data 40 into the tree structure data 10, the data set 20 can be inserted into an appropriate position in the tree structure data 10.
[0065]
<< About (2) >>
　The set insertion unit 2040 selects a data set 20 that is within a predetermined order in descending order of size. For example, assume that the predetermined rank is 2. In this case, the set insertion unit 2040 has the maximum total size (size of each data 40 included in the data set 20) from the data sets 20 stored in the second storage area 60. And then the data set 20 having the largest total size of the data 40 is selected.
[0066]
　Here, it can be said that the larger the size of the data 40 included in the data set 20, the higher the probability that the properties of the data set 20 are sufficiently expressed by the data 40. Therefore, by preferentially inserting the data set 20 having a large total size of the data 40 into the tree structure data 10, the data set 20 can be inserted into an appropriate position in the tree structure data 10.
[0067]
<< About (3) >>
　The set insertion unit 2040 selects the data set 20 whose generation time is within a predetermined order in the order of earliest. For example, assume that the predetermined rank is 2. In this case, the set insertion unit 2040 has the earliest generation time (the longest elapsed time since generation) among the data sets 20 stored in the second storage area 60, and the set insertion unit 2040. Next, the data set 20 with the earliest generation time is selected.
[0068]
　Here, it is considered that the shorter the elapsed time from the generation of the data set 20, the higher the probability that the property of the data set 20 will change due to the insertion of new data 40 into the data set 20. In other words, it is considered that the longer the elapsed time since the data set 20 is generated, the lower the probability that the properties of the data set 20 will change due to the insertion of new data 40. Therefore, by preferentially inserting the data set 20 having a long elapsed time since it was generated into the tree structure data 10, the data set 20 can be inserted into an appropriate position in the tree structure data 10.
[0069]
<< About (4) >>
　The set insertion unit 2040 selects a data set 20 whose last update time point (time point when new data 40 is inserted) is within a predetermined order in the order of earliest. For example, assume that the predetermined rank is 2. In this case, the set insertion unit 2040 has the earliest updated time (the longest elapsed time since the last update) among the data sets 20 stored in the second storage area 60. , And the next data set 20 with the earliest update time.
[0070]
　Here, it is considered that the data set 20 having a longer elapsed time after being updated has a lower probability of being updated thereafter. Therefore, the longer the elapsed time from the update, the lower the probability that the properties of the data set 20 will change. Therefore, by preferentially inserting the data set 20 having a long elapsed time since being updated into the tree structure data 10, the data set 20 can be inserted into an appropriate position in the tree structure data 10.
[0071]
<< About (5) >>
　The set insertion unit 2040 selects a data set 20 having a predetermined order in ascending order of dispersion size of the data 40 contained therein. For example, assume that the predetermined rank is 2. In this case, the set insertion unit 2040 has the data set 20 having the smallest variance of the data 40 and the data set 20 having the next smallest variance of the data 40 among the data sets 20 stored in the second storage area 60. Select.
[0072]
　However, as described above, when the number of data 40 included in the data set 20 is small, the variance of the data 40 included in the data set 20 is likely to change due to the influence of the newly inserted data 40. That is, the data set 20 in which the number of data 40 contained therein is small may not be stable in its properties even if the variance of the data 40 is small.
[0073]
　Therefore, for example, the set insertion unit 2040 extracts from the data set 20 that the number of data 40 contained therein is equal to or greater than the threshold value, and distributes the data 40 only to the extracted data set 20. The data set 20 may be selected in consideration. That is, first, the set insertion unit 2040 extracts from the data set 20 that the number of data 40 contained therein is equal to or greater than the threshold value. Next, the set insertion unit 2040 selects a data set 20 from the extracted data sets 20 whose dispersion size of the data 40 is within a predetermined order in ascending order.
[0074]
<< About (6) >>
　In addition, for example, the set insertion unit 2040 includes the "number of data 40", "size", "generation time", "last update time", and "last update time" mentioned above. A plurality of indexes such as "dispersion of data 40" may be used to calculate the score of each data set 20, and the data set 20 having the calculated score within a predetermined order may be selected in descending order. For example, the set insertion unit 2040 calculates the score shown below by using the above-mentioned five indexes.
[Equation 1]

　Here, i is an identifier of the data set 20. xi1, xi2, xi3, xi4, and xi5 are the number, size, time of generation, last update, and variance of the data 40 in the data set 20 with the identifier i, respectively. f1 (xi1) is a monotonous non-decreasing function for the number of data 40 xi1. f2 (xi2) is a monotonous non-decreasing function for size xi2. f3 (xi3) is a monotonous non-increasing function for the time point xi3 generated. f4 (xi4) is a monotonous non-increasing function for xi4 at the time of the last update. f5 (xi5) is a monotonic non-increasing function for the variance xi5 of the data 40.
[0075]

　The set insertion unit 2040 inserts any one or more of the data sets 20 stored in the second storage area 60 into the tree structure data 10. .. Here, an existing technique can be used as a technique for inserting elemental data (data set 20 in the tree structure data 10) into the tree structure data. Hereinafter, a case where the data set 20 is inserted into the tree structure data 10 realized as a similarity tree will be illustrated.
[0076]
　For example, it is assumed that the tree structure data 10 is a similarity tree having the structure shown in FIG. 6 described above. In this case, the set insertion unit 2040 identifies the data set 20 having the representative data having the maximum similarity with the representative data of the data set 20 to be inserted from each data set 20 of the first layer. Further, the set insertion unit 2040 has a data set having representative data having the maximum similarity with the representative data of the data set 20 to be inserted from the data set 20 of the second layer directly under the specified data set 20. Identify 20. Then, the set insertion unit 2040 inserts the data set 20 to be inserted directly under the specified data set 20.
[0077]
　The data set 20 inserted into the tree structure data 10 is preferably deleted from the second storage area 60. However, instead of deleting the data set 20 immediately after inserting the tree structure data 10, the data set 20 may be deleted at an appropriate timing thereafter. For example, when a new data set 20 is generated in the second storage area 60, the data set 20 to be deleted is overwritten with the new data set 20 so that the data set 20 is deleted.
[0078]

　An example of how to utilize the data managed by the data management device 2000 will be illustrated. For example, the data management device 2000 acquires a search query indicating the data set 20, and from the data sets 20 included in the first storage area 50 and the second storage area 60, the data set 20 and the properties shown in the search query. The data set 20 having a close proximity (similarity is equal to or higher than a predetermined threshold value) is specified and output. As a result, from the data set 20 managed by the data management device 2000, it is possible to easily search for a data set 20 having properties similar to those of the data set 20 indicated by the search query.
[0079]
　The search query is processed as follows, for example. First, the data management device 2000 searches the tree structure data 10 with the data set 20 shown in the search query. If the tree structure data 10 has a similarity with the data set 20 shown in the search query equal to or higher than a predetermined threshold value, the data set 20 is the data set 20 corresponding to the search query (shown in the search query). It is specified as a data set 20) whose properties are similar to those of the data set 20. On the other hand, if the tree structure data 10 does not have a similarity with the data set 20 shown in the search query equal to or higher than a predetermined threshold value, the data management device 2000 searches the second storage area 60.
[0080] [0080]
　If the second storage area 60 has a similarity with or more than a predetermined threshold value with the data set 20 shown in the search query, the data set 20 is specified as the data set 20 corresponding to the search query. .. On the other hand, if there is no data set 20 having a similarity with the data set 20 shown in the search query in the second storage area 60 of a predetermined threshold value or more, it is determined that there is no data set 20 corresponding to the search query.
[0081]
　The information output by the data management device 2000 as a result of the search is arbitrary. For example, the data management device 2000 outputs the data set 20 corresponding to the search query. In addition, for example, when some identification information is assigned to each data set 20 in advance, the data management device 2000 may output the identification information of the data set 20 corresponding to the search query.
[0082]
　For example, it is assumed that the data set 20 includes image features of the same person. In this case, the image feature included in the data set 20 is used to authenticate the person, and the authenticated person's identification information (name, identification number, etc.) is assigned to the data set 20. The data management device 2000 returns this identification information as an output for the search query. Thereby, it is possible to easily grasp which person's image feature is represented by the data set 20 to be searched.
[0083]
　The search query may be manually input or may be input from another device. Here, the timing at which a search is performed for a certain data set 20 (the timing at which a search query indicating the data set 20 is issued) is arbitrary. For example, the timing is such that when the data set 20 to be searched is generated (for example, when a set of image features of the same person is obtained by analyzing the video), the data 40 is inserted into the data set 20 to be searched. When the data set 20 to be searched is completed (for example, when it is determined that the data 40 has not been inserted into the data set 20 for a certain period of time), the number of elements of the data set 20 to be searched is a predetermined number. Is reached, or when the dispersion of the degree of similarity between the data 40 included in the data set 20 to be searched becomes a predetermined value or less. If the processing load of the data management device 2000 is high at each of the above timings (when the usage rate of computer resources such as the CPU is equal to or higher than the threshold value), the processing load of the data management device 2000 becomes low (the usage rate of computer resources). The search timing may be staggered (until is less than the threshold).
[0084]
　Here, the function of inserting the data set 20 into the data management device 2000 may be realized by the same method as the above-mentioned search. Specifically, the data management device 2000 acquires the data set 20 to be inserted. If the tree structure data 10 or the second storage area 60 has a similarity with the data set 20 to be inserted equal to or higher than a predetermined threshold value, the data management device 2000 sets the data set 20 and the data to be inserted. Merge with set 20. As a result, not only the data 40 can be inserted one by one, but also the data set 20 which is a set of the data 40 can be inserted at one time.
[0085]
　Although the embodiments of the present invention have been described above with reference to the drawings, these are examples of the present invention, and combinations of the above embodiments or various configurations other than the above can be adopted.
[0086]
　Some or all of the above embodiments may also be described, but not limited to:
1. 1. It is possible to access the first storage area for storing the tree structure data which is the data of the tree structure having the data set as a node and the second storage area for storing the data set not included in the tree structure data. ,
　Acquire the data to be inserted into the data set, insert the acquired data into the data set already stored in the first storage area or the second storage area, or insert a new data set into the data set. When a predetermined condition is satisfied for the data insertion unit generated in the second storage area and inserting the acquired data into the data set and the data set
　stored in the second storage area, the second storage A data management device having a set insertion unit that inserts one or more of the data sets stored in the area into the tree structure data.
2. 2. The data insertion unit
　　determines whether or not there is a data set into which the
　　acquired data should be inserted, and if there is a data set into which the acquired data should be inserted, the acquired data is used in the data set. When there is no data set to be inserted and the
　　acquired data is to be inserted, a new data set is generated in the second storage area, and the acquired data is inserted into the generated data set. The data management device described in.
3. 3. The plurality of data stored in one data set are image features of the same person extracted from different images. Or 2. The data management device described in.
4. The predetermined condition is that the number or total size of the data contained in the data set stored in the second storage area is equal to or larger than the threshold value, and the
　set insertion unit has the number or total size of data. 1. Insert the data set that exceeds the threshold into the tree structure data. 3. The data management device according to 3.
5. The predetermined condition is that the number or total size of the data sets stored in the second storage area is equal to or larger than the threshold value, and the
　set insertion unit determines a selection rule when the predetermined conditions are satisfied. 1. One or more of the plurality of data sets stored in the second storage area is selected, and the selected data set is inserted into the tree structure data. 3. The data management device according to 3.
6. The selection rule selects
　　the data set that is within a predetermined order in descending order of the number of data, selects the data set that is
　　within a predetermined order in descending order of size, and is
　　generated in the order of earliest. Select the data set that is
　　within the predetermined order in, select the data set that is within the predetermined order in the order of the earliest last update, or
　　within the predetermined order in the order of the smaller distribution of data.
　The rule is to select a certain data set . The data management device described in.
7. A control method performed by a computer
　The computer has a first storage area for storing tree structure data which is tree structure data having a data set as a node, and a second storage area for storing data sets not included in the tree structure data. The control method is accessible and the
　control method
　acquires data to be inserted into the data set and inserts the acquired data into the data set already stored in the first storage area or the second storage area. Alternatively, a data insertion step of generating a new data set in the second storage area and inserting the acquired data into the
　data set, and predetermined conditions for the data set stored in the second storage area. A control method comprising a set insertion step of inserting one or more of the data sets stored in the second storage area into the tree structure data when is satisfied.
8. In the data insertion step,
　　it is determined whether or not there is a data set into which the
　　acquired data should be inserted, and if there is a data set into which the acquired data should be inserted, the acquired data is used in the data set. If there is no data set to be inserted and the
　　acquired data should be inserted, a new data set is generated in the second storage area, and the acquired data is inserted into the generated data set. The control method described in.
9. 6. The plurality of data stored in the data set are image features of the same person extracted from different images. Or 8. The control method described in.
10. The predetermined condition is that the number or total size of the data contained in the data set stored in the second storage area is equal to or larger than the threshold value, and
　the number or total size of the data is set in the set insertion step. 2. Insert the data set that exceeds the threshold value into the tree structure data. 9. The control method according to 9.
11. The predetermined condition is that the number or total size of the data sets stored in the second storage area is equal to or larger than the threshold value, and
　if the predetermined condition is satisfied in the set insertion step, a selection rule 3. Select one or more of the plurality of data sets stored in the second storage area, and insert the selected data set into the tree structure data. 9. The control method according to 9.
12. The selection rule selects
　　the data set that is within a predetermined order in descending order of the number of data, selects the data set that is
　　within a predetermined order in descending order of size, and is
　　generated in the order of earliest. Select the data set that is
　　within the predetermined order in, select the data set that is within the predetermined order in the order of the earliest last update, or
　　within the predetermined order in the order of the smaller distribution of data.
　The rule is to select a certain data set , 11. The control method described in.
13. 7. To 12. A program that causes a computer to execute each step of the control method described in any one of them.
[0087]
　This application claims priority on the basis of Japanese Application Japanese Patent Application No. 2019-098792 filed on May 27, 2019 and incorporates all of its disclosures herein.

WE CLAIMS

It is possible to access the first storage area for storing the tree structure data which is the data of the tree structure having the data set as a node and the second storage area for storing the data set not included in the tree structure data. ,
　Acquire the data to be inserted into the data set, insert the acquired data into the data set already stored in the first storage area or the second storage area, or insert a new data set into the data set. When a predetermined condition is satisfied for the data insertion means generated in the second storage area and inserting the acquired data into the data set and the data set
　stored in the second storage area, the second storage A data management device comprising a set inserting means for inserting one or more of the data sets stored in an area into the tree structure data.
[Claim 2]
　The data inserting means
　　determines whether or not there is a data set into which the
　　acquired data should be inserted, and if there is a data set into which the acquired data should be inserted, the acquired data is used in the data set.
　　The first aspect of the present invention is to generate a new data set in the second storage area and insert the acquired data into the generated data set when the data set to be inserted and the acquired data does not exist . The data management device described.
[Claim 3]
　The data management device according to claim 1 or 2, wherein the plurality of data stored in one data set are image features of the same person extracted from different images.
[Claim 4]
　The predetermined condition is that the number or total size of the data contained in the data set stored in the second storage area is equal to or larger than the threshold value, and the
　set inserting means has the number or total size of data. The data management device according to claim 1 to 3, wherein the data set having become equal to or more than a threshold value is inserted into the tree structure data.
[Claim 5]
　The predetermined condition is that the number or total size of the data sets stored in the second storage area is equal to or larger than the threshold value, and the
　set insertion means determines a selection rule when the predetermined condition is satisfied. 1 to 3 in which one or more of the plurality of data sets stored in the second storage area is selected and the selected data set is inserted into the tree structure data. The data management device described in.
[Claim 6]
　The selection rule selects
　　the data set that is within a predetermined order in descending order of the number of data, selects the data set that is
　　within a predetermined order in descending order of size, and is
　　generated in the order of earliest. Select the data set that is
　　within the predetermined order in, select the data set that is within the predetermined order in the order of the earliest last update, or
　　within the predetermined order in the order of the smaller distribution of data.
　The data management device according to claim 5, which is a rule of selecting a certain data set .
[Claim 7]
　A control method executed by a computer,
　wherein the computer has a first storage area for storing tree-structured data, which is tree-structured data having a data set as a node, and a data set not included in the tree-structured data. The
　control method
　acquires data to be inserted into the data set and transfers the acquired data to the first storage area or the second storage area. A data insertion step of inserting into the already stored data set or generating a new data set in the second storage area and inserting the acquired data into the data set, and a data insertion step in
　the second storage area. A control method comprising a set insertion step of inserting one or more of the data sets stored in the second storage area into the tree structure data when a predetermined condition is satisfied for the stored data set. ..
[Claim 8]
　A computer that can access a first storage area that stores tree-structured data that has a data set as a node and a second storage area that stores data sets that are not included in the tree-structured data. The data to be inserted into the
　data set is acquired, and the acquired data is inserted into the data set already stored in the first storage area or the second storage area, or a new data set is inserted. When the data insertion step of generating in the second storage area and inserting the acquired data into the
　data set and the predetermined conditions for the data set stored in the second storage area are satisfied, the second A storage medium for storing a program for executing a set insertion step of inserting one or more of the data sets stored in the storage area into the tree structure data.