JP5953262B2 - DATA INDEX DEVICE, DATA INDEX METHOD, AND PROGRAM - Google Patents

Description

  The present invention relates to a data index device, a data index method, and a program for inserting and retrieving data using a tree structure index.

  Conventionally, various index techniques having a tree structure such as B-Tree and R-Tree have been proposed in the database technical field as techniques for speeding up the search. For example, UBI-Tree (indexing technology for data including one or more pairs of attribute and attribute values (also called key-value pairs) such as sensor measurement data, that is, sensor information, etc. There exists patent document 1). When UBI-Tree is used, for example, “sensor ID = 1, time = 3, temperature = 20”, which includes data including three attributes of sensor ID, time and temperature, “sensor ID = 3, time = 7, Data including four attributes such as sensor ID, time, illuminance, and volume, such as “illuminance = 6, volume = 4”, can be efficiently indexed into one index.

  By the way, in UBI-Tree, when indexing new data, that is, when inserting new data into the UBI-Tree tree structure, the root is the same as in many other tree structure index technologies. The node is traced while selecting a child node that holds similar data based on the insertion destination node selection algorithm from the node, and new data is held in the arrived leaf node. Here, similar data refers to data that is close to each other in attribute type and attribute value with new data.

  In addition, if new data is inserted into the tree structure of UBI-Tree and the number of data to be retained or the number of child nodes to be retained exceeds the upper limit, the node is determined based on the node division algorithm. The data is divided into two and data or child nodes are distributed to the two divided nodes. At this time, similar data or child nodes holding similar data in the lower order are distributed to the same node. In this way, similar data can be classified and held in the same leaf node or the same subtree. As a result, conditions for acquiring similar data are often set in the search, and therefore, data that matches the search conditions exists in one leaf node or one subtree, and the data is Even when a large amount exists, only specific nodes can be traced and data matching the search conditions can be efficiently searched.

  The above insertion destination node selection algorithm and node split algorithm are called ChooseSubtree and Split in the R-Tree, respectively. Both algorithms use an index called a penalty. The insertion destination node selection algorithm is an algorithm for selecting a node having the smallest penalty increment when new data is inserted. The node division algorithm is an algorithm that performs a division method that minimizes the sum of the penalty of two nodes after division.

In the UBI-Tree, “probability that the node is searched” or “the number of attribute types included in the node” or a combination thereof is used as a penalty. When the “probability that the node is searched” is used as a penalty, the number of nodes to be traced can be reduced and search efficiency can be improved by suppressing the penalty in the insertion destination node selection algorithm or the node division algorithm. . In addition, when “the number of attribute types included in the node” is used as a penalty, the number of nodes to be traced at the time of search based on the attribute type specified in the search condition can be reduced by similarly reducing the penalty. Efficiency can be increased. When the combination of “probability of searching for the node” and “number of attribute types included in the node” is used as a penalty, both effects can be expected. The “probability that the node is searched” is calculated from the statistical information of the data inserted so far. The statistical information is recorded in an attribute table. For each attribute, the appearance frequency in the inserted data and the maximum and minimum values of the corresponding attribute value are recorded. Each time new data is inserted, the attribute table is updated. The “probability that the node is searched” is calculated by the following equation using the attribute table.
Probability that the node is searched = ΣXi Yi (i∈A for all attribute sets A)
i
However, Xi indicates the probability that the node is searched when the attribute i is searched, and Yi indicates the probability that the attribute i is used as a search condition.

  In addition, when a combination of “probability of searching for the node” and “number of attribute types included in the node” is used as a penalty, for example, first, “number of attribute types included in the node” is used as a penalty. When the node selection algorithm is applied and the insertion destination node cannot be narrowed down to one, the insertion destination node selection algorithm is further applied with the “probability that the node is searched” as a penalty, and a plurality of candidates are selected. It is sufficient to narrow down the insertion destination node to one.

JP 2011-170461 A

However, the conventional UBI-Tree has the following problems to be solved.
That is, the conventional UBI-Tree calculates in consideration of all attributes of data inserted into the UBI-Tree when calculating the “probability that the node is searched” used as a penalty. For this reason, calculation for all the attributes requires a large amount of calculation, which requires much time for data insertion processing.

  Also, the conventional UBI-Tree calculates a predicted value of “probability that the node is searched” from statistical information of data inserted so far. For this reason, the predicted value is not necessarily the same as the true value. If there is an error between the predicted value and the true value, the search efficiency is deteriorated.

  Furthermore, in the conventional UBI-Tree, when a combination of “number of attribute types included in the node” and “probability that the node is searched” is used as a penalty, attributes included in most of the inserted data are included. Even if the number of attribute types included in each node is reduced with the “number of attribute types included in the node” as a penalty for the search as a search condition, the search should be followed based on the type of attribute specified in the search condition. The number of nodes cannot be reduced and search efficiency deteriorates.

  The present invention has been made paying attention to the above circumstances, and the object of the present invention is to reduce the amount of calculation necessary for calculating the penalty so that the new data can be inserted at high speed and to be followed at the time of retrieval. An object of the present invention is to provide a data indexing device, a data indexing method, and a program in which the number of nodes is suppressed and search efficiency is increased.

  To achieve the above object, according to a first aspect of the present invention, there is provided a data indexing apparatus for storing and managing a data set having at least one set of attributes and attribute values by a UBI-Tree structure. The data set, the UBI-Tree structure, and at least the attribute list of interest in which attributes used for calculating the penalty are stored in advance, and when inserting new data into the UBI-Tree structure, Among the attributes of the new data, a penalty is calculated using only the attributes corresponding to the attributes defined in the target attribute list, and the new data is inserted.

  The second aspect of the present invention further stores a dimension suppression penalty invalidation flag for designating whether or not to use the number of attribute types included in the target node as a penalty, and adds a new one to the UBI-Tree structure. When inserting data, refer to the dimension suppression penalty invalidation flag, and if the flag is set to ON, the number of attribute types included in the target node and the probability that the target node will be searched The value is calculated using only the probability that the target node is searched as a penalty, and the number of attribute types included in the target node and the probability that the target node is searched when the flag is set to off. Both are used as penalties and their values are calculated.

  According to the first aspect of the present invention, when new data is inserted into the UBI-Tree structure, it corresponds to an attribute defined in the attention attribute list stored in advance among the attributes of the new data. Penalties are calculated using only the attributes to be processed. In general, the attribute set used for the search condition is often known in advance. Therefore, if the attribute set used for the search condition in such a case is defined in the attribute list of interest, the penalty calculation is performed compared with the case where the penalty is calculated for all the attributes of the new data while maintaining the search accuracy. The amount can be reduced, thereby reducing the time required to insert new data and reducing the processing load on the apparatus.

  According to the second aspect of the present invention, when new dimension insertion penalty invalidation flag stored in advance is set to ON when inserting new data into the UBI-Tree structure, the target node The penalty calculation is performed using only the probability that the target node is searched as a penalty without using the number of attribute types included in the as a penalty. As described above, the attribute set used for the search condition is often known in advance. If the attribute is an attribute that is included in most of the data to be inserted, the number of attribute types included in the target node can be invalidated in advance using the dimension suppression penalty invalidation flag to maintain search accuracy. Thus, it is possible to reduce the amount of penalty calculation, thereby reducing the time required for inserting new data and reducing the processing load of the apparatus.

  In other words, according to the first and second aspects of the present invention, the amount of calculation required for calculating the penalty is reduced, the new data insertion process can be performed at high speed, and the number of nodes to be traced at the time of retrieval is suppressed. Thus, it is possible to provide a data indexing device, a data indexing method, and a program capable of improving the search efficiency.

The block diagram which shows the function structure of the data index apparatus which concerns on one Embodiment of this invention. The figure which shows an example of the data memorize | stored in the memory | storage unit of the data index apparatus shown in FIG. The figure which shows an example of the tree structure information memorize | stored in the memory | storage unit of the data index apparatus shown in FIG. The figure which shows an example of the attribute table information memorize | stored in the memory | storage unit of the data index apparatus shown in FIG. The figure which shows an example of attention attribute list information memorize | stored in the memory | storage unit of the data index apparatus shown in FIG. The figure which shows an example of the dimension suppression penalty flag memorize | stored in the memory | storage unit of the data index apparatus shown in FIG. The figure which shows an example of the data of new insertion object. The figure which shows an example of the attribute table information updated with the new insertion of data.

Embodiments according to the present invention will be described below with reference to the drawings.
[One Embodiment]
FIG. 1 is a block diagram showing a functional configuration of a data indexing apparatus according to an embodiment of the present invention.
The data index device according to the present embodiment includes, for example, a database server, and includes a control unit 1, a communication interface unit 2, and a storage unit 3. The communication interface unit 2 has a function of receiving measurement data with a sensor group (not shown), for example, according to a communication protocol defined by the network NW.

  The storage unit 3 uses, for example, an HDD (Hard Disc Drive) or an SSD (Solid State Drive) as a storage medium, and serves as a storage area for storing tree structure information necessary for realizing an embodiment of the present invention. A data set storage unit 31, a tree structure storage unit 32, an attribute table storage unit 33, a target attribute list storage unit 34, and a dimension suppression penalty flag storage unit 35.

  The data set storage unit 31 stores a set of measurement data received by the communication interface unit 2. Each measurement data has at least one set of attributes and attribute values. Reference numerals 201 to 205 in FIG. 2 show examples of measurement data. For example, the measurement data 201 has “sensor ID”, “time”, “temperature”, and “humidity” as attributes, and “1”, “3”, “20.3”, and “60” as attribute values, respectively. Have The measurement data 202 has “sensor ID”, “time”, and “illuminance” as attributes, and has “3”, “7”, and “6” as attribute values. That is, each measurement data has a set of one or more attributes and attribute values, and the number and types of attributes may differ between the data.

  The tree structure storage unit 32 stores a tree structure for managing the data set in an indexed state by UBI-Tree. The tree structure of UBI-Tree uses a combination of “probability that the node is searched” and “the number of attribute types included in the node” as a penalty. FIG. 3 shows an example of a UBI-Tree tree structure. In this example, the tree structure includes a plurality of nodes 301 to 306 and a plurality of measurement data 201 to 205. The measurement data 201 to 205 correspond to the data shown in FIG.

  The node 301 located at the root of the tree is called a root node, and the nodes 304 to 306 corresponding to the leaves of the tree are called leaf nodes. Each node 301 to 306 holds a pointer to another node or data. For example, the root node 301 holds a pointer to the node 302 and a pointer to the node 303. This is simply expressed as the node 301 holding the child node 302. It is assumed that there is a parent-child relationship between the nodes connected by the pointer. For example, for the root node 301, the node 302 is called a child node. Conversely, the root node 301 is called a parent node with respect to the node 302. The upper limit value of the number of child nodes or data held by each node is set to “2”.

  Although not shown in FIG. 3, for each child node, the parent node holds information indicating a range related to data existing under the child node. For example, the root node 301 has a “sensor ID” of 1 to 10, a “time” of 3 to 10, a “temperature” of 20.3 to 21.1, and a “humidity” of 60 to 90 with respect to the child nodes 302 and below. It holds information that data exists. Similarly, the root node 301 also holds data range information existing below the child node 303. When performing a search, it is possible to efficiently find data satisfying the search condition by tracing only nodes satisfying the search condition using the range information.

The attribute table storage unit 33 stores information representing the appearance frequency, minimum value, and maximum value of the attributes of the measurement data set stored in the data set storage unit 31. FIG. 4 shows an example of this, and illustrates the case where the attributes of the data set shown in FIG. 2 are represented in a table.
The attention attribute list storage unit 34 stores in advance a list of attributes to be calculated when calculating “probability that the node is searched” as a penalty when inserting new data into the data set storage unit 31. It is remembered. FIG. 5 shows an example, and in this example, “time” and “temperature” are defined as the attributes of interest.

  The dimension suppression penalty invalidation flag storage unit 35 stores in advance the state (ON / OFF) of the dimension suppression penalty invalidation flag. The dimension suppression penalty invalidation flag is “the number of attribute types included in the node”. To invalidate this, “the probability that the node is searched” and “the number of attribute types included in the node” This means that only the “probability that the node is searched” is taken as a penalty. FIG. 6 illustrates a state in which the dimension suppression penalty invalidation flag is set to ON.

  The control unit 1 includes, for example, a CPU (Central Processing Unit), and includes a data search unit 11 and a data insertion unit 12 as control functions necessary for realizing one embodiment of the present invention. The data search unit 11 and the data insertion unit 12 are realized by causing the CPU to execute a program stored in a program memory (not shown).

  When a data search request transmitted from a search source device (not shown) is received by the communication interface unit 2 via the network NW, the data search unit 11 includes a search condition specified by the received data search request, Based on the tree structure information stored in the tree structure storage unit 32 and the attribute table information stored in the attribute table storage unit 33, the child node 302, 303 and the leaf nodes 304 to 306 are sequentially traced from the root node 301. To identify measurement data. Then, the specified measurement data is read from the data set storage unit 31, and the read measurement data is returned from the communication interface 2 to the requesting device via the network NW.

The data insertion unit 12 has the following processing functions.
(1) When new measurement data transmitted from a sensor (not shown) is received by the communication interface unit 2 via the network NW, among the types of attributes of the received new measurement data, the target attribute list storage unit A penalty is calculated only from the attributes included in the attribute list of interest stored in 34. Then, a process of tracing a node based on the calculated penalty and the tree structure information stored in the tree structure storage unit 32 and specifying the node into which the new measurement data is to be inserted.

  (2) When calculating the penalty, the dimension suppression penalty invalidation flag stored in the dimension suppression penalty invalidation flag storage unit 35 is referred to, and if the flag is ON, “attribute type included in the node” A process of calculating only “probability that the node is searched” as a penalty without using “number” as a penalty.

Next, the operation of the data indexing device IU configured as described above will be described.
Here, it is assumed that the dimension suppression penalty invalidation flag is set to “ON”, and “time” and “temperature” are described in the target attribute list. In the following description, it is assumed that the tree structure storage unit 32 of the storage unit 3 stores the UBI-Tree structure shown in FIG. 3, and the attribute table storage unit 33 stores the attribute table shown in FIG.

  Now, it is assumed that new measurement data is transmitted from a sensor (not shown) and this new measurement data is received by the communication interface unit 2 via the network NW. FIG. 7 shows the new measurement data received at this time.

  When the new measurement data is received, the control unit IU activates the data insertion unit 12 and executes the following data insertion process under the control of the data insertion unit 12. That is, first, the attribute table stored in the attribute table storage unit 33 is updated based on the received new measurement data. For example, since the received new measurement data includes “sensor ID”, “time”, “humidity”, “illuminance”, and “volume” as attributes, the appearance of the corresponding row in the pre-update attribute table shown in FIG. Since the frequency is increased by “1” and the values of “time”, “illuminance”, and “volume” are larger than the existing data values, the maximum value of the corresponding attribute is updated. FIG. 8 shows the updated attribute table.

  Next, an insertion destination node is selected from the tree-structured root node 301 using an insertion destination node selection algorithm. At this time, the dimension suppression penalty invalidation flag stored in the dimension suppression penalty invalidation flag storage unit 35 is examined. Then, it is determined whether the flag is set to ON or OFF, and both “the number of attribute types included in the node” and “probability that the node is searched” are determined according to the determination result. It is determined whether to use a penalty or only a “probability that the node is searched”. Further, when calculating the “probability that the node is searched”, among the attributes included in the received new measurement data, it is described in the target attribute list stored in the target attribute list storage unit 33. Penalties are calculated only for the attribute of interest.

For example, as described above, it is assumed that the dimension suppression penalty invalidation flag is set to ON and “time” and “temperature” are described in the target attribute list. In this case, “the number of attribute types included in the node” is excluded from the penalty, and only the “probability that the node is searched” is used as the penalty. In addition, when calculating the “probability that the node is searched”, the received new measurement data includes “time”, “humidity”, “illuminance”, and “volume” as attributes, Since only “time” and “temperature” are described in the target attribute list, “probability that the node is searched” is calculated as a penalty only for “time”. The “probability that the node is searched” X and the probability Y when “time” is used as a search condition are calculated by the following equations.
Probability of searching for the node = XY
That is, the right side is not the sum of all attributes, but only the “time” that is the attribute used for calculating the penalty.

  In the root node 301, the data insertion unit 12 selects an insertion destination node using an insertion destination node selection algorithm as follows. That is, assuming that the new measurement data is inserted into the node 303, the value of “time” included in the node 303 is originally “7-9” and changes to “7-11”. That is, the value range is expanded by “2”. On the other hand, assuming that new measurement data is inserted into the node 302, the value of “time” included in the node 302 is originally “3 to 10” and changes to “3 to 11”. That is, the range of values is expanded by “1”. Here, when the “probability that the node is searched” is used as a penalty, the one with the smaller spread of the value range is selected as the insertion destination. Therefore, in this case, the node 302 having a small range of the “time” value is selected as the insertion destination.

  Next, in the node 302, the insertion destination node is similarly selected using the insertion destination node selection algorithm. In this case, the spread of the “time” value range is smaller in the node 305 than in the node 304. Therefore, the node 305 is selected as the insertion destination node, and the new measurement data is inserted into this node 305.

  However, when the new measurement data is inserted into the node 305, the number of data held by the node 305 becomes “3”, exceeding the upper limit “2” of the number of child nodes or data held by each node. End up. Therefore, the node 305 is divided by a node division algorithm. Note that when dividing a node, as in the insertion destination node selection algorithm described above, the attribute of interest is used when checking the dimension suppression penalty invalidation flag and calculating the “probability that the node is searched”. Only the attributes described in the list are subject to calculation.

  On the other hand, if the dimension suppression penalty invalidation flag is set to OFF when the new measurement data is inserted, “the number of attribute types included in the node” is used as a penalty. Then, the “number of attribute types included in the node” is calculated for the two nodes 302 and 302 connected to the root node 301 by the insertion destination node selection algorithm.

  For example, assuming that new measurement data is to be inserted into the node 303, the attributes included in the node 303 are originally four types of “sensor ID”, “time”, “illuminance”, and “volume”. There are five types of “sensor ID”, “time”, “illuminance”, “volume”, and “humidity”, and the number of attribute types increases by “1”. On the other hand, assuming that new measurement data is to be inserted into the node 302, the attributes included in the node 302 were originally “sensor ID”, “time”, “temperature”, and “humidity”. , “Sensor ID”, “time”, “temperature”, “humidity”, “illuminance”, “volume”, and the number of attribute types increases by “2”. Therefore, in this case, the node 303 with a small increase in the number of attribute types is selected as the insertion destination.

  As described above, if new measurement data is inserted into a node connected to the node 303 selected as the insertion destination, data having the “volume” attribute is narrowed down to nodes connected to the node 303, and therefore “volume” is set as a search condition. When this is used, only the subtree below the node 303 needs to be searched, and the search efficiency is improved.

  On the other hand, when the node 302 is selected as the insertion destination, measurement data having the attribute of “volume” is distributed to the node connected to the node 302 and the node connected to the node 303. Therefore, “volume = 0 to 10” is set. When used as a search condition, both the subtree connected to the node 302 and the subtree connected to the node 303 must be searched, and the search efficiency decreases.

  However, when the node 303 is selected as the insertion destination, the node 302 holds the measurement data having the “time” value “3 to 10” in the subordinate node, and the node 303 has the “time” value “7 to 11”. ”Is stored in a subordinate node. For this reason, for example, when “time = 10” is used as a search condition, it is necessary to search both subtrees. On the other hand, when the node 302 is selected as the insertion destination, only the subtree below the node 302 needs to be searched for the search condition “time = 10”. As described above, when the search condition is an attribute held by only a part of the inserted measurement data, such as “volume = 0 to 10,” “the attribute included in the node”. Search efficiency is improved by taking the number of types as a penalty. However, in the case where an attribute held by a lot of data such as “time” is used as a search condition, the search efficiency is lowered by setting “the number of attribute types included in the node” as a penalty. Therefore, when it is known in advance that the attribute held by a lot of data is often used as a search condition, the dimension suppression penalty invalidation flag is set to ON as in this embodiment, By not using the “number of included attribute types” as a penalty, search efficiency can be improved.

  Further, when new measurement data is inserted, if the “probability that the node is searched” is calculated using all the attributes included in the new measurement data by the insertion destination node selection algorithm at the node 302, the node 302 is not the node 305. 304 is selected as the insertion destination. Then, when new measurement data is inserted into the selected node 304, the range of the “time” value increases from “3 to 3” to “3 to 11” and the expansion width becomes “8”. The sensor ID ”increases from“ 1-1 ”to“ 1-2 ”, and the expansion width is only“ 1 ”. Further, the value range of “humidity” does not need to be increased. Conversely, when the node 305 is selected as the insertion destination, the range of the “time” value only increases from “8 to 10” to “8 to 11”, and the expansion width can be “1”, but “sensor ID”. And “humidity” value range increases.

  Considering the same as the selection algorithm of the insertion destination node in the root node 301, for example, when searching by “sensor ID”, the node 304 is selected as the insertion destination so that the expansion width of the value of “sensor ID” becomes small. This improves search efficiency. On the other hand, when searching by “time”, the search efficiency is improved by selecting the node 305 as the insertion destination so that the expansion range of the value of “time” is small.

  Therefore, when the attribute used for the search condition is known in advance, the attribute type used for the search condition is stored in advance in the focused attribute list storage unit 34 as in the present embodiment, and is included in the new measurement data. It is possible to increase the search efficiency by calculating “probability that the node is searched” as a penalty using only the attributes described in the attribute list of interest among the attributes.

[Other Embodiments]
The present invention is not limited to the above embodiment. For example, in the above-described embodiment, the upper limit value of the number of child nodes or data held by each node is set to “2”. However, the present invention is not limited to this and may be set to another positive value.

  In the above embodiment, when calculating the penalty, the attribute used for calculating the “probability that the node is searched” is selected with reference to the attribute list of interest. When updating, it is also possible to refer to the target attribute list and not add an attribute not described in the target attribute list to the attribute table. In this way, when calculating the penalty, since the attribute that does not exist in the attribute table is not described in the attribute list of interest, the “probability that the node is searched” is calculated simply by referring to the attribute table. It is possible to select an attribute to be used for. Further, the attribute table may be increased by one column and a flag indicating whether or not it is described in the target attribute list may be stored. By doing so, it is possible to select an attribute used for calculating the “probability that the node is searched” simply by referring to the attribute table.

  Furthermore, in the one embodiment, the penalty is calculated using only the attribute described in the target attribute list among the attributes included in the new measurement data to be inserted. However, the attribute included in the measurement data to be inserted Of these, the penalty may be calculated using an attribute other than the attribute described in the attribute list of interest. In this way, when it is known in advance that “do not search with this attribute”, it is possible to prevent the penalty from being used for calculating the penalty by describing the attribute in the attribute list of interest.

  Further, in the embodiment, the dimension suppression penalty invalidation flag and the target attribute list are stored in advance in the dimension suppression penalty invalidation flag storage unit 35 and the target attribute storage unit 34, respectively. It may be rewritable from a terminal or the like. This makes it possible to dynamically change these settings in accordance with changes in search requests.

  In the above-described embodiment, the case where measurement data such as temperature, humidity, illuminance, and volume obtained by a sensor is handled as data has been described as an example. However, the measurement data such as current, voltage value, fluid flow rate, substance concentration, brightness, noise level, position, acceleration, etc. may be dealt with, and it is obtained via other than sensors such as the Web or the Internet. It may be information. In addition to these values, information including metadata indicating sensor characteristics and states, measurement date and time, and the like may be handled. In addition, the configuration of the data indexing device, the procedure and processing contents of the data insertion processing, and the like can be implemented with various modifications without departing from the gist of the present invention.

  In short, the present invention is not limited to the above-described embodiment as it is, and can be embodied by modifying the constituent elements without departing from the scope of the invention in the implementation stage. Further, various inventions can be formed by appropriately combining a plurality of constituent elements disclosed in the embodiment. For example, some components may be deleted from all the components shown in the embodiment. Furthermore, you may combine suitably the component covering different embodiment.

  IU ... Data indexing device, NW ... Network, 1 ... Control unit, 2 ... Communication interface unit, 3 ... Storage unit, 11 ... Data search unit, 12 ... Data insertion unit, 31 ... Data set storage unit, 32 ... Tree structure storage , 33 ... attribute table storage unit, 34 ... attention attribute list storage unit, 35 ... dimension suppression penalty invalidation flag storage unit.

Claims (5)

A data indexing apparatus for storing and managing a set of data having at least one set of attributes and attribute values by a UBI-Tree structure,
Tree structure information storage means for storing at least the data set, the UBI-Tree structure, and an attribute list of interest in which attributes used for calculating penalties are defined in advance;
When inserting new data into the UBI-Tree structure, a penalty is calculated using only attributes corresponding to the attributes defined in the attribute list of interest among the attributes of the new data, and the new data A data indexing device comprising: data insertion means for performing insertion. The tree structure information storage means further stores a dimension suppression penalty invalidation flag that specifies whether or not to use the number of attribute types included in the target node as a penalty,
The data insertion means refers to the dimension suppression penalty invalidation flag when inserting new data into the UBI-Tree structure, and is included in the target node if the flag is set to ON. Among the number of attribute types and the probability that the target node is searched, the value is calculated using only the probability that the target node is searched as a penalty, and if the flag is set to off, the target node The data indexing device according to claim 1, wherein the value is calculated by using both the number of included attribute types and the probability that the target node is searched as a penalty. A data indexing method executed by a device that stores and manages a set of data having at least one set of attributes and attribute values by a UBI-Tree structure,
Storing the data set, the UBI-Tree structure, and an attribute list of interest in which attributes used for calculating penalties are defined in advance in at least a tree structure information storage unit;
When inserting new data into the UBI-Tree structure, the target attribute list is read, and only attributes corresponding to the attributes defined in the read target attribute list among the attributes of the new data are read. A data indexing method comprising: calculating a penalty using the data, and inserting the new data based on the calculation result. The storing step further stores a dimension suppression penalty invalidation flag that specifies whether or not to use the number of attribute types included in the target node as a penalty,
The process of inserting new data refers to the dimension suppression penalty invalidation flag when inserting new data into the UBI-Tree structure, and when the flag is set to ON, When the number of attribute types included in the node and the probability of searching for the target node is calculated using only the probability of searching for the target node as a penalty, and the flag is set to off The data indexing method according to claim 3, wherein the value is calculated using both the number of attribute types included in the target node and the probability that the target node is searched as a penalty.   A program for causing a computer included in the data indexing apparatus to execute processing by the data insertion unit included in the data indexing apparatus according to claim 1 or 2.

Images