JP2011170461A - Information accumulation retrieval method and information accumulation retrieval program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To perform efficient retrieval with respect to various kinds of multidimensional tuples. <P>SOLUTION: In an information accumulation retrieval method, a retrieval key is indexed from a tuple that is a unit of information of an accumulation retrieval target, and a retrieval tree is constructed. When an entry B is inserted into an existing entry A already included by an operation target node, when an existing entry having a smallest "penalty when inserting an entry X into an existing entry already included by the operation target node" is selected in the operation target node, when a slave node or the entry X comprising a tuple identifier and a key is inserted into a node of an index in construction of the index, penalty is defined as a value indicating increment of a value corresponding to probability that the entry A is retrieved, when the entry A prior to an entry B is inserted and the entry A after the insertion, when the entry B is inserted into the existing entry A already included by the operation target node. <P>COPYRIGHT: (C)2011,JPO&INPIT

Description

  The present invention relates to an information storage search method and an information storage search program suitable for use in the construction of an indexing method for searching for target data at a high speed from multi-dimensional and various types of data.

  In the field of database technology, various indexing technologies have been devised in order to retrieve target data from a large amount of data at high speed. Hereinafter, each piece of data is referred to as a tuple, as is a name in a relational database (RDB). A tuple is assumed to be composed of one or more attribute-value pairs (AV pairs (attribute-value pairs)). A tuple table represents a set of tuples as a table.

  In the most widely used RDB at present, a data structure called a B-tree is often used as an index. In particular, in RDB that is put into practical use, B + trees and B * trees, which are improved types of B trees, are often used. These technologies are also used in file systems.

  These are data structures (tree structures) in the form of a tree constructed for a set of attribute values (values that fall within one column in RDB) for one type of attribute in each tuple. Also called. By constructing this search tree for each attribute for which a search condition is desired at the time of search, high-speed search is possible.

  These B-trees or their improved types are indexes built for one attribute, but there are other indexes built for two or more attributes and the values of two or more attributes or It is used to realize a search with a specified range of values at high speed. Since such an index is for a tuple having a plurality of attributes, that is, a tuple containing multidimensional data, it is called a multidimensional index. The most typical multidimensional index is an R-tree. The R tree has a tree structure similar to the B tree, and there are many improved types such as an R * tree and an R + tree.

  Many of these conventional search trees have the following characteristics in common as described in Non-Patent Document 1.

Contains one or more nodes,
The node includes a number of entries from 0 to a predetermined threshold;
The node is a leaf node or an inner node,
The entry of the leaf node is
It consists of a tuple identifier and a tuple key pair.
The entry of the inner node is
A pointer to another node,
A key set obtained by summing the keys of the entry set included in the other node,
The key is a sequence of attribute-value or attribute-value range pairs having one or more lengths (ie, one or more data string lengths; the same shall apply hereinafter);
From the first layer node called the root node,
This is a tree-structured search tree in which nodes are hierarchically connected by the pointer.

  Similarly, as described in Non-Patent Document 1, the tuple insertion method to these search trees, that is, the tuple indexing method, includes the following procedures in common.

A procedure called Split in Non-Patent Document 1:
For one node and one entry in the search tree,
A node splitting procedure in which a key set in the node and a key set including a key in the entry are divided into two groups, one of them is put into a new node, and the new node is inserted into the parent node of the node.

A procedure called “AdjustKeys” in Non-Patent Document 1:
For one node in the search tree,
A key set information adjustment procedure for recursively performing an operation for transmitting the key set information included in the node to the parent node and holding the key set information included in the node as a child node from the node to the root node.

A procedure called ChooseSubtree in Non-Patent Document 1:
For one entry X and number of levels L,
In each node from the root node to the node of level number L,
Among the entries included in the node, the entry included in the node is an existing entry,
When the entry X is an entry to be inserted, an entry included in the node having the smallest penalty is selected,
Recursively perform the operation that sets the child node indicated by the pointer included in the entry as the next operation target,
A subtree selection procedure for finally selecting one node of level number L.

  Here, the penalty is an index indicating the efficiency in finding a tuple satisfying a desired search condition using a search tree constructed through each procedure in indexing. It becomes an index showing.

A procedure called Insert in Non-Patent Document 1:
For one entry and the number of levels L,
Performing a subtree selection procedure for the entry and the level number L;
For the selected number of level L nodes,
If the node contains less than a predetermined number of entries,
Add the entry to the node,
If the node contains more than a predetermined number of entries,
Perform node splitting procedure for the node and the entry,
An entry insertion procedure for performing a key set information adjustment procedure for the node.

  Similarly, as described in Non-Patent Document 1, the tuple search method from these search trees includes the following procedures in common.

A procedure called “Search” in Non-Patent Document 1:
For one node to be searched and a search key that is a key as a search expression,
If the node is not a leaf node, for each entry contained in the node:
The key of the entry includes all the attributes included in the search key, and the value or value range corresponding to each attribute included in the search key matches the value or value range corresponding to the attribute included in the key of the entry Or check for partial matches,
If there is a match or partial match, the node connected by the entry pointer is searched, the node search procedure is performed recursively using the search key as a search key,
If the node is a leaf node, for each entry contained in the node,
Check whether the key of the entry includes all the attributes included in the search key and whether the value or value range corresponding to each attribute included in the search key includes the value corresponding to the attribute included in the key of the entry ,
If included, a node search procedure for adding the tuple identifier of the entry to the search result tuple identifier set.

  As the penalty, for example, in an R-tree, an increase amount of an object size generally called a minimum bounding rectangle or a minimum bounding rectangle (MBR) is used. If it is a tuple set indicating coordinate data in a three-dimensional space, the key of each entry is also three-dimensional, and the minimum circumscribed rectangle of the entry is any surface that contains all the tuple sets included in the lower hierarchy. The smallest cuboid parallel to the axis. In tuple insertion, a node that minimizes the volume increase of the rectangular parallelepiped is selected as a tuple insertion destination by the subtree selection procedure. This corresponds to clustering in which tuples that are close to each other in the three-dimensional space are put into the same node, and thereby, tuples that satisfy the search condition can be found efficiently. Also, the penalty is used as an index of whether or not the division is good in the node division procedure.

Joseph M.M. Hellerstein, Jeffrey F .; Naughton and Avi Pfeffer, “Generalized Search Trees for Database Systems,” Proc. 21st Int'l Conf. on Very Large Data Bases, Zürich, September 1995, pp. 562-573.

  With the development of MEMS (Micro-Electro-Mechanical Systems) technology, power storage technology, communication technology, and the like, various small sensor devices are becoming available at low cost. It is expected to realize such a ubiquitous environment where many such various sensors are placed around us and various applications using them support our lives. Sensor data output from such a sensor device can usually be expressed in the form of the tuple.

  In a ubiquitous environment in which various sensors and applications exist, sensor data (tuples) including various attributes are accumulated, and a search specifying various attributes is performed. For example, when a tuple obtained from a two-dimensional acceleration sensor in the x, y direction and a tuple obtained from a three dimensional acceleration sensor in the x, y, z direction are mixed, an application that wants to know the acceleration in the x, y direction is: Both types of tuples should be available. That is, when “acceleration data in x and y directions” is used as a search condition, it is necessary to search for both types of tuples. In such a search of sensor data that is often indicated by a numerical value, a range search is important. In order to realize range search for such multi-dimensional tuples as efficiently as possible, when using conventional index technology, a method using a B-tree (or an improved version thereof) and an R-tree (or an improved version thereof) are used. The method of using can be considered.

  In the method using the B-tree, an index based on the B-tree is constructed for each attribute, and for each attribute specified by the search condition, the condition of the attribute is set using the B-tree index corresponding to the attribute. After searching for the tuples that satisfy the condition, an AND (logical product) of all the results is obtained (that is, only the tuples included in any result are extracted), and this is used as the final search result.

  However, since the method using the B-tree accesses a plurality of B-trees, the total number of access nodes at the time of search increases. The number of access nodes is an important parameter that determines the search processing amount and speed. Further, the amount of processing of AND processing depends not on the amount of final search results but on the amount of intermediate results obtained by searching with each B-tree, and therefore tends to increase according to the number of tuples. In other words, the method using the B-tree has a problem that the processing amount and processing time of the entire search process are likely to increase.

  The method using the R-tree is to construct an index by the R-tree for each tuple type, that is, in the case of the acceleration sensor described above, for each of the x, y2 dimensional tuple and the x, y, z3 dimensional tuple. After searching for tuples that satisfy the search condition using the R-tree index corresponding to the tuple type including all attributes specified by the search condition, OR (logical sum) of all results is taken (summarizing each result) This is the final search result.

  However, in the method using the R-tree, too, since a plurality of R-trees are accessed, when the number of tuple types increases, the total number of access nodes at the time of R-tree search increases. In addition, preprocessing for determining which R-tree should be searched is also necessary. In other words, this method also has a problem that the processing amount and processing time of the entire search process tends to increase.

  Therefore, it is conceivable to insert various multi-dimensional tuple sets, that is, tuple sets having different numbers and types of attributes, into one search tree. However, the conventional tree structure index includes all target tuple sets. It is assumed that they are the same dimension. In other words, it is assumed that an index is constructed for a set of tuples having the same number and type of attributes. For example, consider a case where a tuple set indicating coordinate data in a two-dimensional space is indexed by an R-tree. At this time, the minimum circumscribed rectangle of the entry including the tuple set in the lower hierarchy is represented by the minimum rectangle including all the tuple sets. When indexing a multi-dimensional tuple, a new three-dimensional tuple may be inserted here. In this case, the minimum circumscribed rectangle is a rectangular parallelepiped. By definition, the penalty is a value obtained by subtracting the rectangular area from the volume of the rectangular parallelepiped, but the value obtained by subtracting values of different dimensions has no logical meaning and cannot be a good clustering index. As a result, good search efficiency cannot be realized with the R-tree for various multidimensional tuple sets. In other words, in the conventional tree structure index, it is necessary to be able to determine the magnitude relation for each dimension for all dimensions included in the key of the entry in calculating the penalty with two entries as inputs. However, because the dimension that the key contains is different between the entries that contain multi-dimensional tuples at the lower level, the size relationship for each dimension cannot always be determined, and an efficient index for multi-dimensional multi-tuples must be constructed. I could not.

  On the other hand, it is conventionally known that there is a problem that a search for multidimensional data having a very large number of dimensions cannot be performed efficiently (a problem called “dimension curse”). This is a specific example of the “dimensional curse” problem. When the points are uniformly distributed in the n-dimensional space, the distance from one point to the other points increases as n increases. It gets smaller. Due to such a phenomenon, even when clustering is performed by a technique such as R-tree, only clusters that are largely overlapped with each other are formed, and the effect of clustering is not exhibited. That is, it is necessary to trace many nodes on the search tree at the time of search, and efficient search cannot be performed.

  In the ubiquitous environment, various devices (sensors and actuators) are used, and accordingly, the types of data are varied, and the number of dimensions is expected to be very large. In other words, in the search for the ubiquitous environment, the number of dimensions of the search data increases according to various devices, so it is considered that the “dimension curse” problem may occur.

  The present invention has been made to solve the above-mentioned problems in consideration of such circumstances, and its purpose is to search for various multi-dimensional tuples when the number of tuples and the number of included attribute types are large. In addition, it is to realize efficiently. Another object of the present invention is to enable an efficient search while avoiding the problem of “curse of dimension” in a search for various multidimensional tuples.

  In order to solve the above problem, the invention according to claim 1 is characterized in that a tuple as a unit of information to be stored and searched has one or more lengths including at least an array of attribute-value pairs. A plurality of one or more tuples having the same type or the same or different length are stored, a search key is indexed from the tuples, and a search tree is constructed. The node has a hierarchical structure, and the leaf node at the lowest layer of the node has a tuple identifier and key for identifying the tuple as an entry, and an inner node higher than the leaf node of the node It has a pointer and a key which are position information of child nodes which are lower nodes as an entry, and when the entry is inserted into the node in the construction of the index, one entry When the entry X to be entered and the number L of levels to insert the entry (the number of hierarchies incremented by 1 each time the hierarchy is increased with the leaf node set to 0), the root node is first set as the operation target node, and the operation target In the node, one existing entry is selected based on “the penalty when the entry X is inserted into the existing entry already included in the operation target node”, and the child node indicated by the pointer included in the existing entry is selected. When the next operation target node is selected, and the number of levels of the next operation target node is greater than L, it is recursively repeated to select the next operation target node from the next operation target node. When the number of levels of the operation target node reaches L, the step of determining this node as a selection node and the selection node are acceptable In the case of not having a large number of entries, the step of adding the entry X to the selected node; and in the case where the selected node already has the maximum allowable number of entries, the entry X is added. An information storage and retrieval method, comprising: dividing the selected node; and updating an entry of an upper node of the selected node when the division is performed.

  According to a second aspect of the present invention, in the step of performing the division according to the first aspect, when each entry obtained by adding the entry X to a plurality of entries included in the selection node is sequentially allocated to two groups, each group Selecting the distribution destination group based on each penalty obtained for each group, with the entry that is the sum of the entries already included as the existing entry A and the entry to be distributed as the entry B; Each entry distributed to one of the two groups as an entry of the selected node, and each entry distributed to another group as an entry of a newly generated node; Inserting the generated node entry into the parent node of the node; The information storage retrieval method characterized.

  The invention according to claim 3 is characterized in that the step of determining the selection node according to claim 1 or 2 selects the existing entry having the smallest penalty in the operation target node. It is.

In the invention according to claim 4, when the penalty according to claim 3 inserts the entry B into the existing entry A already included in the operation target node, the entry A before the entry B is inserted; When compared with the entry A after insertion, it is defined as a value indicating an increment of a value corresponding to the probability that the entry A is searched, and as a value corresponding to the probability that the entry A is searched, The sum of the weighted normalized searched areas for the attributes included in the key included in the entry A is used. The weighted normalized searched area is used as the normalized searched area and the attribute is used as the search expression. a value obtained by multiplying the probabilities, the normalized target search area, the formula ((q-a) (b -p) - (q-p) 2/2) / ((b-a) 2/2 ) (Where p and q are each the genus included in the key) Minimum and maximum values of the sex, a and b are defined by the minimum and maximum values of the attributes included in all tuple sets inserted in the search tree until then. It is an accumulation search method.

  In the invention according to claim 5, when the penalty according to claim 3 inserts the entry B into the existing entry A already included in the operation target node, the entry A before the entry B is inserted; The information storage and retrieval method is characterized in that the value indicates an increase in the number of attribute types included in the key included in the entry A when compared with the entry A after insertion.

  According to a sixth aspect of the present invention, the step of determining the selection node according to the first or second aspect uses the two types of penalties, and selects the existing entry having the smallest first penalty in the operation target node. At this time, when there are a plurality of the smallest existing entries, the information storage and retrieval method is characterized in that, among the smallest existing entries, an existing entry having the smallest second penalty is selected. .

  According to a seventh aspect of the present invention, in the sixth aspect, the entry before the entry B is inserted when the first penalty inserts the entry B into the existing entry A already included in the operation target node. A is a value indicating an increase in the number of attribute types included in the key included in the entry A when comparing the entry A after insertion, and the second penalty indicates that the operation target node Probability that the entry A is searched when the entry A is inserted into the existing entry A that is already included and the entry A before the entry B is inserted is compared with the entry A after the insertion. This is an information storage and retrieval method characterized by being a value indicating an increment of a value corresponding to.

  The invention according to claim 8 provides the sum of the weighted normalized search areas for each attribute included in the key included in the entry as a value corresponding to the probability that the entry is searched. This is an information storage and retrieval method characterized by being used.

  The invention according to claim 9 uses the value obtained by dividing the number of occurrences of the attribute by the total number of tuples as the probability that the attribute is used in the search formula according to claim 4 or 8, and the number of occurrences of the attribute is The number of appearances of the attribute in all tuple sets inserted in the tree, and the total number of tuples is the number of elements in all tuple sets inserted in the search tree so far It is.

  A tenth aspect of the present invention is the retrieval using the retrieval tree according to any one of the first to ninth aspects, wherein the retrieval key which is the key as a retrieval formula is retrieved from the root node to the lower node. While changing the target, if one of the nodes is a search target and the node is the inner node, for each entry included in the node, the key of the entry includes all the attributes included in the search key. And the value or value range corresponding to each attribute included in the search key and the value or value range corresponding to the attribute included in the key of the entry match or partially match (one value or value) Search procedure to find out if the range is included or partially overlaps the other value range, and if it matches or partially matches, it is connected by the pointer of the entry The node search procedure is recursively performed using a search key as a search target and the search key as a search key. If the node is the leaf node, the key of the entry is set for each entry included in the node. Check whether all the attributes included in the search key are included, and whether the value corresponding to each attribute included in the search key or the value range corresponding to the attribute included in the key of the entry is included in the value range, And a node search step of adding the tuple identifier of the entry to a search result tuple identifier set if it is included.

  According to the eleventh aspect of the present invention, a tuple which is a unit of information to be stored and searched has one or more lengths including at least an array of attribute-value pairs. The type of attribute and the length of the array A plurality of one or more tuples having the same or different lengths are stored, a search key is indexed from the tuples, and a search tree is constructed, and the search tree has nodes hierarchically The leaf node at the lowest layer of the node has a tuple identifier and key for identifying the tuple as an entry, and an inner node higher than the leaf node of the node is a child that is a lower node as an entry. A pointer and a key that are position information of the node, and when the entry is inserted into the node in the construction of the index, one entry X to be inserted; When the number L of levels to insert the entry (the number of hierarchies that increases by 1 every time the hierarchy is increased with the leaf node being 0) is given, the root node is first set as the operation target node. One existing entry is selected based on the penalty when the entry X is inserted for an existing entry already included in the node, and the child node indicated by the pointer included in the existing entry is selected as the next operation target node If the number of levels of the next operation target node is greater than L, recursively repeating the selection of the next operation target node from the next operation target node, and the number of levels of the next operation target node If L reaches L, the step of determining this node as the selected node and having the maximum number of entries allowed by the selected node If there is not, the step of adding the entry X to the selected node; and if the selected node already has the maximum allowable number of entries, dividing the selected node while adding the entry X An information storage / retrieval program for executing, using a computer, a step of performing and a step of updating an entry of an upper node of the selected node when the division is performed.

  According to a twelfth aspect of the present invention, in the step of performing the division according to the eleventh aspect, when each entry obtained by adding the entry X to a plurality of entries included in the selection node is sequentially allocated to two groups, each group Selecting the distribution destination group based on each penalty obtained for each group, with the entry that is the sum of the entries already included as the existing entry A and the entry to be distributed as the entry B; Each entry distributed to one of the two groups as an entry of the selected node, and each entry distributed to another group as an entry of a newly generated node; Inserting the generated node entry into the parent node of the node. The information storage retrieval program characterized and.

  According to a thirteenth aspect of the present invention, the step of determining a selection node according to the eleventh to twelfth aspects selects the existing entry having the smallest penalty in the operation target node. It is.

In the invention described in claim 14, when the penalty described in claim 13 inserts the entry B into the existing entry A already included in the operation target node, the entry A before the entry B is inserted; When compared with the entry A after insertion, it is defined as a value indicating an increment of a value corresponding to the probability that the entry A is searched, and as a value corresponding to the probability that the entry A is searched, The sum of the weighted normalized searched areas for the attributes included in the key included in the entry A is used. The weighted normalized searched area is used as the normalized searched area and the attribute is used as the search expression. a value obtained by multiplying the probabilities, the normalized target search area, the formula ((q-a) (b -p) - (q-p) 2/2) / ((b-a) 2/2 ) (However, p and q are included in the key. Minimum value and maximum value of the attribute, a and b are defined by the minimum value and maximum value of the attribute included in all tuple sets inserted in the search tree until then. This is an information storage and retrieval program.

  In the invention of claim 15, when the penalty of claim 13 inserts the entry B into the existing entry A already included in the operation target node, the entry A before the entry B is inserted; An information storage and retrieval program characterized in that the value indicates an increment of the number of attribute types included in a key included in the entry A when compared with the entry A after insertion.

  According to a sixteenth aspect of the present invention, the step of determining the selection node according to the eleventh to twelfth aspects uses the two types of penalties and selects the existing entry having the smallest first penalty in the operation target node. At this time, when there are a plurality of the smallest existing entries, the information storage and retrieval program is characterized in that, among the smallest existing entries, an existing entry having the smallest second penalty is selected. .

  According to a seventeenth aspect of the present invention, in the sixteenth aspect, the entry before the entry B is inserted when the first penalty inserts the entry B into the existing entry A already included in the operation target node. A is a value indicating an increase in the number of attribute types included in the key included in the entry A when comparing the entry A after insertion, and the second penalty indicates that the operation target node Probability that the entry A is searched when the entry A is inserted into the existing entry A that is already included and the entry A before the entry B is inserted is compared with the entry A after the insertion. An information storage and retrieval program characterized by being a value indicating an increment of a value corresponding to.

  The invention according to claim 18 is the sum of the weighted normalized search areas for each attribute included in the key included in the entry as a value corresponding to the probability that the entry is searched. An information storage and retrieval program characterized by being used.

  The invention according to claim 19 uses the value obtained by dividing the number of occurrences of attributes by the total number of tuples as the probability that the attribute is used in the search expression according to claim 14 or 18, wherein the number of occurrences of attributes An information storage and retrieval program characterized in that the number of occurrences of the attribute in all tuple sets inserted in the tree, and the total number of tuples is the number of elements in all tuple sets inserted in the search tree so far It is.

  The invention according to claim 20 is the search using the search tree according to any one of claims 11 to 19, wherein the search key which is the key as a search expression is searched from the root node to the node below it. While changing the target, if one of the nodes is a search target and the node is the inner node, for each entry included in the node, the key of the entry includes all the attributes included in the search key. And the value or value range corresponding to each attribute included in the search key and the value or value range corresponding to the attribute included in the key of the entry match or partially match (one value or value) The search procedure is performed to check whether the range is included or partially overlaps the other value range. If the range matches or partially matches, the pointer of the entry is connected. If the node is a search target and the search key is a search key, the node search procedure is recursively performed. If the node is the leaf node, the key of the entry is set for each entry included in the node. Check whether all the attributes included in the search key are included, and whether the value corresponding to each attribute included in the search key or the value range corresponding to the attribute included in the key of the entry is included in the value range, If it is included, a node search step of adding the tuple identifier of the entry to a search result tuple identifier set is an information storage search program.

  According to the present invention, when constructing a single tree structure index uniformly for various multidimensional tuples, in the operation target node, “the entry X is assigned to the existing entry already included in the operation target node. One existing entry is selected based on the “penalty for insertion” and the entry is inserted into the node. As this penalty, for example, an increase in the number of attribute types included in the key included in the entry, and a value corresponding to the search probability before and after the entry insertion (that is, a search probability or an approximate value of the search probability) By using this increase amount, it is not necessary to determine the magnitude relationship for each dimension, and the penalty can be defined even if the number of key dimensions and types included in the entry are different. This suppresses the overhead caused by using multiple indexes when accumulating / retrieving various multi-dimensional tuple sets, that is, the amount of processing, storage capacity, and processing speed, and increases the number of multi-dimensional tuple sets. On the other hand, it is possible to realize clustering that improves search efficiency.

In calculating the penalty, the sum of the weighted normalized search areas for each attribute included in the key included in the entry is used as a value corresponding to the probability that the entry is searched, and the weighted normalized search target is used. The search area is a value obtained by multiplying the normalized search area by the probability that the attribute is used in the search formula, and the normalized search area is expressed by the formula ((q−a) (b−p) − ^{(q-p) 2/2} ) / ((b-a) 2/2) ( where, p, respectively q is the attribute minimum value of which is included in the key, the maximum value .a, b, respectively, it Until it is specified by the minimum and maximum values of the attributes included in all the tuple sets inserted in the search tree until, or as a penalty for the existing entry A already included in the operation target node When entry B is inserted, entry B When the entry A before the insertion is compared with the entry A after the insertion, a value indicating the increment of the number of attribute types included in the key included in the entry A is obtained. Even if an attribute that was not included in the previous is newly added to the entry by inserting a tuple, a penalty will occur, so the state transition that increases the number of attribute types, that is, the dimension of the entry The increase can be suppressed and the problem of “curse of dimension” can be avoided.

It is a schematic diagram for demonstrating the penalty calculation method characterized by the present invention. It is a figure which shows the information storage search system whole figure for performing the information storage search method of this invention. It is a figure which shows the example of the tuple used with the system of FIG. It is a figure which shows the example of the search formula used with the system of FIG. FIG. 3 is a block diagram illustrating a configuration example of a server computer apparatus 201 in FIG. 2. It is a figure which shows the example of the data structure of the index used with the system of FIG. It is a figure which shows the example of the tuple table used with the system of FIG. It is a figure which shows the example of the entry table of the leaf node used with the system of FIG. It is a figure which shows the example of the entry table of the inner node used with the system of FIG. It is a figure which shows the example of the attribute table used with the system of FIG. FIG. 3 is a block diagram illustrating a configuration example of a client computer device 301 in FIG. 2. 3 is a flowchart of an entry insertion procedure (Insert) in the system of FIG. 3 is a flowchart of a subtree selection procedure (ChooseSubtree) in the system of FIG. 2. 17 is a flowchart showing a node division procedure (Split) in the system of FIG. 2 together with FIGS. 15 and 16. 17 is a flowchart showing a node division procedure (Split) in the system of FIG. 2 together with FIGS. 14 and 16. 16 is a flowchart showing a node division procedure (Split) in the system of FIG. 2 together with FIGS. 14 and 15. It is a figure which shows the node division example 1 by the node division | segmentation procedure in the system of FIG. It is a figure which shows the node division example 2 by the node division | segmentation procedure in the system of FIG. It is a flowchart of the key set information adjustment procedure (AdjustKeys) in the system of FIG. It is a flowchart of the node search procedure (Search) in the system of FIG.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings. In the information storage and retrieval method of the present invention, when the penalty used when constructing the retrieval tree is to insert the entry B into the existing entry A that is already included in the node to be operated in the case of node selection processing or the like, It is defined as a value indicating an increment of a value corresponding to the probability that the entry A is searched when the entry A before the entry B is inserted and the entry A after the insertion B are compared. It is a feature. In the present embodiment, as the value indicating the increment of the value corresponding to the probability that this entry is searched, an increase amount of the sum of the weighted normalized search area for each attribute included in the key included in the entry is used. It is said. First, the penalty calculation method in this embodiment will be described in detail with reference to FIG.

  In this embodiment, as the penalty of the search tree, an increase amount of the sum of the weighted normalized search areas for each attribute included in the key included in the entry is used. An increase amount of the sum of the weighted normalized search areas for the attributes included in the key included in the entry will be described with reference to mathematical expressions.

(Formula definition)
Consider a case where the domain of a certain attribute xa is from RA to RB, and the attribute xa is included in a key held by a certain entry E as a value range from p to q. In this case, the search condition specifying the value range of the attribute xa corresponds to one point in the triangle of FIG. 1 if the specified value range is within the domain of the attribute xa. FIG. 1 is a coordinate system for schematically explaining the probability that an entry E is searched by specifying a value range of the attribute xa. The search condition specifying the attribute xa is the start point of the value range on the horizontal axis. The vertical axis represents the end point of the value range, and represents the coordinates corresponding to the search condition. For example, if the search condition specifies the value range of xa1 to xa2, it corresponds to the point Xa in FIG. At this time, a search condition that can include a tuple corresponding to the entry E or lower, that is, a search condition that needs to access the entry E corresponds to one point in the shaded portion in FIG.

  Here, Formula I is defined as follows.

((Q-a) (b -p) - (q-p) 2/2) / ((b-a) 2/2) ( Formula I)

  p and q are the minimum value and maximum value of the attribute included in the key, respectively, and a and b are the minimum value and maximum value of the attribute included in all tuple sets inserted in the search tree until then. Is expressed. Formula I represents the normalized search area.

  When a search specifying the attribute xa is performed, if the probability that the value range is xstart to xend is given by the probability density function Xp (xstart, xend), the entry E is accessed in the search specifying the attribute xa Is equal to the value obtained by integrating the probability density function Xp across the shaded area.

  However, it is usually difficult to know the probability density distribution Xp in advance. Therefore, assuming that the search condition corresponding to any point in the triangle in FIG. 1 can occur with an equal probability, the probability that the entry E is accessed is ((shaded area) / (triangle area)). Become. That is, the probability is given by

((Q-RA) (RB -p) - (q-p) 2/2) / ((RB-RA) 2/2)

  When the definition areas RA and RB are unknown, it is considered that the minimum value a and the maximum value b for the attribute xa in the tuple set registered in the index so far are used instead of RA and RB, respectively. . At this time, the area of the shaded area is given by the following equation S.

((Q-a) (b -p) - (q-p) 2/2) / ((b-a) 2/2) ( Equation S)

  The expression S is an expression equal to the expression I, and a value obtained by this is called a normalized search area.

(Explanation of effect)
When a certain attribute is used in the search expression and a range condition specifying the value range of the attribute is used in the search expression, two values indicating the start point and end point of the value range are identical in the definition area of the attribute. Assuming that it is chosen with a similar probability, the probability that the entry needs to be accessed is approximated by Equation I. The value obtained by Expression I is the normalized search area. The weighted normalized search area is obtained by multiplying the normalized search area by the probability that the attribute is used in the search expression.

  Therefore, the sum of the weighted normalized search area for each attribute included in the key included in the entry is an approximation of the probability that the entry must be accessed in order to search for a tuple that matches the search condition. Corresponds to the value. By using the sum of the weighted normalized search areas as a penalty and constructing a search tree under the strategy of reducing the penalty as much as possible, the number of entries that must be accessed during the search can be reduced as a whole. . That is, it is possible to improve the search processing amount and processing speed.

  In Equation I, when p = q, that is, when the start point and end point of the value range of the attribute xa held by the entry E are equal,

((Q-a) (b -p) - (q-p) 2/2) / ((b-a) 2/2)
= (P-a) (b -p) / ((b-a) 2/2) ( Equation T)

  It becomes. Usually, b> a, and in many cases p> a and b> p, so in many cases (right side of Expression T)> 0. That is, even when the start point and the end point of the value range of the attribute xa are equal, a penalty occurs due to the presence of the attribute.

  If an attribute that was not previously included in an entry is newly added to the entry by inserting a tuple, and if the attribute of the tuple is a value rather than a value range, the entry The start point and end point of the value range are equal. Since the change to this state is accompanied by a penalty as described above, in the present invention, such a state transition in which the number of attribute types increases, that is, an increase in the dimension of an entry is suppressed.

  On the other hand, the penalty used in the R-tree is an increase in the length of the value range of the attribute held by the entry, or an increase in the volume of a hypercube with one side as a side, so that the start point and end point of the value range are equal. Will have a penalty of zero. That is, when the attribute of the tuple to be inserted has a value rather than a value range, the suppression force to the dimension increase does not work at all.

  As described above, the present invention can suppress the increase in the dimension of each entry, thereby preventing the problem of “curse of dimension” due to an increase in the number of dimensions.

  Further, in the following embodiment, as the penalty of the search tree, in addition to the penalty based on the increase amount of the sum of the weighted normalized search areas, the increase amount of the attribute type included in the key included in the entry is used. It was decided. As a result, the dimensionality of the entry can be suppressed more strongly and the problem of “curse of dimension” can be suppressed more than when only the increased amount of the sum of the weighted normalized search areas is used as a penalty. .

  In the following embodiments, one or two search tree penalties are used. That is, as the first penalty, the “increase in the number of attribute types included in the key included in the entry” is used, and as the second penalty, the search probability before and after the entry insertion or an approximation of the search probability The amount of increase in value, that is, “the amount of increase in the sum of the weighted normalized search areas for each attribute included in the key included in the entry” is used. Since the first penalty has a strong dimensional increase reduction effect and the second penalty has a certain dimensional increase reduction effect, even if any penalty is used in the subtree selection procedure or node splitting procedure, It can suppress the “curse” problem. Further, in the subtree selection procedure, when there are a plurality of entries having the smallest first penalty, the second penalty is compared among them, and the entry having the smallest second penalty is selected. In the node splitting procedure, the entry is classified using the first penalty as the classification index, and if the first penalty index is the same value, the entry is further classified using the second penalty as the classification index. Specifically, for each entry, the entry having the largest difference between the first penalty when entering the group G1 and the first penalty when entering the group G2 is classified into the group having the smallest first penalty. If there are multiple entries with the largest difference, classify them into groups with the smallest first penalty between them. If the second penalty is compared, and the entries with the smallest second penalty are sorted into the group with the smallest first penalty, the dimensional increase reduction effect by the first penalty and the second penalty This is a search tree construction method that combines the search efficiency improvement effects of the penalty. In particular, when the “increase in the sum of weighted normalized search areas for each attribute included in the key included in the entry” is used as the second penalty, the first penalty is only the attribute type. Is more effective because it can be said to be a search tree construction method that combines the "search efficiency improvement effect by considering the value of each attribute (dimension)" by the second penalty. .

  FIG. 2 is a schematic block diagram showing an information storage / retrieval system according to an embodiment of the present invention. The information storage / retrieval system includes a server / computer device 201 that stores and retrieves information, that is, tuples, and a tuple / search formula between the server / computer device 201 and the creation of tuples / search formulas. Or a client computer 301 that transmits and receives search results. The network 101 includes a public network such as the Internet, a private network such as a LAN (Local Area Network), a dedicated line. In FIG. 2, only one client computer device 301 is shown for simplicity, but a plurality of client computer devices 301 may be provided.

  The server computer device 201 and the client computer device 301 can be realized using a computer and its peripheral devices and a program executed by the computer. The program can be provided via a computer-readable recording medium or a communication line.

  In the present embodiment, tuples are accumulated, and tuples are searched using a search formula. A tuple is composed of one or more attribute / value pairs (AV pairs). The number of tuple AV pairs to be stored and the types of their attributes vary. FIG. 3 shows an example of a tuple. FIG. 3A is an example of a tuple of three-dimensional data. In this example, “PC”, “XX” are assigned to the “device type”, “user”, and “use start date” attributes. Tuples are configured by pairs (or sets) of values of “Taro” and “2005/04/01”. FIG. 3B is an example of a 7-dimensional data tuple. In this example, “device type”, “user”, “latitude”, “longitude”, “sensing time”, “sensor ID”, and For each attribute of “sensor value”, “temperature sensor”, “Taro XX”, “126030”, “501018”, “2008/11/11 12:34:56”, “123456”, and “23.5” Tuples are formed by pairs of values. Here, in the tuple of FIG. 3B, the unit of latitude and longitude is seconds, and north latitude and east longitude are expressed as positive, and south latitude and west longitude are expressed as negative.

  The search expression is composed of one or more attributes and a value or value range pair. FIG. 4 shows an example of a search expression. The search formula is a description for obtaining a tuple satisfying the search condition as a search result. In the example shown in FIG. 4, the value of the attribute “device type” is “temperature sensor”, and the value of the attribute “latitude” is a value. Tuples that are in the range “126000 to 127000” and whose attribute “longitude” value is in the value range “501000 to 501100” are used as the search results. When searching, tuples that include all the attributes included in the search expression and whose attribute value is within the attribute value or value range included in the search expression are used as search results. For example, in the search using the search formula of FIG. 4, the tuple of FIG. 3B matches the search formula and is included in the search result.

Next, the internal configuration of the server computer apparatus 201 will be described.
FIG. 5 is a block diagram showing a configuration of the server computer apparatus 201. The server computer apparatus 201 receives a tuple accumulation request / tuple search request from the client computer apparatus 301 or transmits a search result, and builds an index in response to a request from the client computer apparatus 301. And a storage unit 204 that stores an index, an attribute table, a total number of tuples, and a tuple table.

  Further, in the present embodiment, a file access method using an index is adopted when determining the storage position of the tuple satisfying the search condition indicated by the search formula in the storage unit 204. As the data structure of the index, various search trees as described in the background art can be used. An example of an index data structure used in this embodiment is shown in FIG. The data structure of the index is a tree structure represented by a plurality of nodes and branches that connect them hierarchically. The highest node is called a root node, and the lowest node is called a leaf node. Nodes other than leaf nodes are called inner nodes. In the example illustrated in FIG. 6, a search tree is configured by four inner nodes 402 and seven leaf nodes 403. The top node of the inner node 402 is the root node 401. Each inner node 402 holds pointers to other nodes connected by branches and an entry table 502 described later. Each leaf node 403 holds a pointer to another inner node 402 connected by a branch and an entry table 503 described later.

  Next, an example of a tuple table stored in the storage unit 204 is shown in FIG. The tuple table stores a tuple ID (tuple identifier) and information on the tuple. The tuple table 501 shown in FIG. 7 includes two tuple IDs “000000001” and “000000002”, and two tuples “device_type =“ PC ”, user =“ mike ”, date_of_first_use =“ 2005 ”respectively corresponding to each tuple ID. / 04/01 ”and“ device_type = “temperature sensor”, user = “mike”, lat = “126030”, long = “501018”, time = “2008/11/11 12:34:56”, sensor_id = Information of “123456” and temperature_value = “23.5” is stored.

  The leaf node 403 holds a pointer to a node (parent node) in the hierarchy one level higher and a leaf node entry table 503 shown in FIG. A pointer to a node means a storage address of the node, and corresponds to a branch connecting the nodes. The entry of the leaf node 403 is composed of a tuple ID and tuple key pair, and the key is composed of a sequence of attribute-value pairs having a length of 1 or more. That is, one entry corresponds to one vertical column (one column) in the entry table 503. The leaf node entry table 503 holds the number of leaf node entries from T1 to T2. T1 and T2 are predetermined constants, both of which are positive integers, and T1 <T2.

  In the example illustrated in FIG. 8, the entry table 503 includes an entry including a tuple ID “00000008129” and a tuple key pair corresponding to the tuple ID, and a tuple ID “000000045” and a tuple key corresponding to the tuple ID. , An entry including a tuple ID “0000000082” and a tuple key set corresponding to the tuple ID, and a tuple key set corresponding to the tuple ID “000003581” and the tuple ID. 4 entries are included. In this case, for example, the tuple key pair corresponding to the tuple ID “0000008129” is “PC” (value for the attribute “device_type”), “mike” (value for the attribute “user”), “2007/11/23”. (Value for attribute “date_of_first_use”), “103456” (value for attribute “lat”), and “218234” (value for attribute “long”). In addition, for example, the tuple key pair corresponding to the tuple ID “000000045” includes “temperature sensor” (value for the attribute “device_type”), “mike” (value for the attribute “user”), “132210” (attribute “ lat ”),“ 501222 ”(value for attribute“ long ”),“ 2002/01/01 12:34:56 ”(value for attribute“ time ”),“ 11983 ”(value for attribute“ sensor_id ”) And “15.4” (value for the attribute “sensor_value”). The symbol “NULL” (null value) indicates the end of the entry. The symbol “-” indicates that the key for the attribute is a null value.

  The inner node 402 holds a pointer to the parent node and the entry table 502 of the inner node shown in FIG. An entry of the inner node is composed of a pair of a pointer to the child node and a key of the child node, and the key is composed of a sequence of attribute-value range pairs having a length of 1 or more. Represents the minimum value to the maximum value for each attribute in the tuple set included in the lower level. The inner node entry table holds the number of inner node entries from T1 to T2. In the entry table 502, one entry corresponds to one vertical column (one column) of the entry table 502. For example, in FIG. 9, “device_type” of “address of child node 1” and “address of child node 2” are “a” to “k” and “h” to “q”, respectively. Yes. This means that tuples starting with “device_type” starting with “a” to “k” may be stored in child node 1, and tuples starting with “h” to “q” are child node 2. Indicates that it may be stored. That is, tuples whose initial letters “device_type” begin with “h” to “k” are stored in either the child node 1 or the child node 2. The inner node entry table holds the number of inner node entries from T1 to T2. In this case, the entry table 502 includes an entry including a pointer “child node 1 address” to the child node and a key set of the child node, and a pointer “child node 2 address” to the child node and its child. An entry consisting of a node key pair, a child node pointer "child node 3 address" and its child node key pair entry, a child node pointer "child node 4 address" and its children Four entries are included, an entry consisting of a key set of nodes. In FIG. 9, the notation of the format “M1 to M2” indicates that “M1” is the minimum value and “M2” is the maximum value.

  In FIG. 6, the root node 401 is an inner node, but the root node 401 is a special node. When the entire index is composed of only one node, the root node 401 is also the lowest node, Become. If the root node 401 is a leaf node, 0 to T2 leaf node entries are held in the entry table. When the root node 401 is an inner node, the number of inner node entries from 2 to T2 is held. Since the root node 401 does not have a parent node, it does not hold a pointer to the parent node.

  Next, the attribute table stored in the storage unit 204 is shown in FIG. The attribute table holds the number of times included, the minimum value, and the maximum value for all attributes included in the tuple set accumulated so far. The attribute table 504 illustrated in FIG. 10 includes the occurrence frequencies of tuple attributes “device_type”, “user”, “date_of_first_use”, “lat”, “long”, “time”, “sensor_id”, and “sensor_value”. The minimum and maximum attribute values are preserved. The minimum value and the maximum value of the tuple values can be obtained, for example, by converting the tuple values into predetermined numerical values by a predetermined conversion process set in advance for each attribute. For example, when the tuple value is a character string, the conversion processing is performed by converting the character string into a character code and then performing a predetermined arithmetic processing such as four arithmetic operations to obtain a numerical value, or by expressing in hours, minutes, and seconds. A process for obtaining a numerical value by expressing the value to be expressed in units of seconds can be used.

Next, the internal configuration of the client computer device 301 will be described.
FIG. 11 is a block diagram showing the configuration of the client computer device 301. The client computer device 301 includes a communication unit 302 that transmits a tuple accumulation request / tuple search request to the server computer device 201 or receives a search result, and a tuple included in the tuple accumulation request that is transmitted to the server computer device 201. And a tuple / search formula creation display unit 303 for displaying a tuple set that is a search result received from the server / computer apparatus 201 and a search formula included in the tuple search request. There are two methods for creating a tuple / search expression: a method in which a user inputs data using an input device, and a method in which data is created from sensor data obtained from a sensor device.

  In this embodiment, when accumulating tuples, in response to a tuple accumulation request received from the client computer apparatus 301, the arithmetic unit 203 of the server computer apparatus 201 first refers to the tuple table 501 held in the storage unit 204. Then, an unused new tuple ID is determined, and the tuple ID and the tuple included in the tuple accumulation request are added to the tuple table 501. Further, the attribute table 504 is updated and the total number of tuples (that is, the total number of tuples accumulated) is increased by one. Further, an entry corresponding to the tuple is inserted into the index held by the storage unit 204. The entry insertion procedure flow at this time is shown in FIG. The entry X of the argument and the number of levels L in the processing shown in FIG. Here, the number of levels is assumed to be 0 for the level of the leaf node hierarchy, and the level number is increased by 1 each time the level is increased by one. The entry X is data corresponding to one of the four entries shown in the entry table 503 in FIG. 8, for example.

  As shown in FIG. 12, first, a subtree selection procedure is performed with the entry 0 as an input (step S11-1). In the subtree selection procedure (step S11-1), the node having the level number L where the entry X is to be inserted is selected as a selection node (that is, an address indicating the node to be inserted when returning from the subroutine of step S11-1) Is returned as the return value). This subtree selection procedure will be described later.

  Next, it is determined whether the number of entries described in the entry table of the node selected in step S11-1 is less than the maximum value T2 of the number of entries in the entry table (step S11-2). If it is less than T2, the entry is added to the entry table of the node (step S11-3). If it is not less than T2 in step S11-2, a node division procedure is performed in which the node and the entry are input (step S11-4). The node division procedure will be described later. Next, a key set information adjustment procedure using the node as an input is performed (step S11-5), and the process ends. The key set information adjustment procedure will be described later.

  FIG. 13 shows a subtree selection procedure flow called in step S11-1 in FIG. In the subtree selection procedure, first, the address of the root node is substituted into the variable current (current), the number of levels of the root node is substituted into the variable lv, and the list min_child_list is emptied (step S12-1). The variable current is a variable to which the address of the operation target node is substituted. In this case, the address of the root node is first substituted in step S12-1. Thereafter, each time the level number lv of the operation target node changes, it is updated by substituting the address of the child node in step S12-18. The list min_child_list is a variable in which one or a plurality of entry numbers having the lowest value of a function P1 described later are stored.

  Next, lv is compared with the input level number L (step S12-2). If lv is smaller, 1 is substituted into variable child_num, and the number in child_num is added to list min_child_list. (Step S12-3). Next, a penalty value is calculated by the function P1 having the child node's child_num-th entry and the input entry X as arguments, and is substituted into the variable min_penalty (step S12-4).

  The function P1 is defined as follows. A and B indicate entries.

  P1 (A, B) = Q1 (A + B) -Q1 (A)

  Here, Q1 (C) indicates the number of attribute types included in the key included in the entry C. A + B indicates an entry having a new key obtained by adding the key of the entry A and the key of the entry B. Here, the key obtained by summing two keys includes all the attributes included in the two keys, and when the attribute is included in one of the two keys as the value of each attribute, If the attribute has the same value or value range as the attribute or value range included in the one key, and the attribute is included in both of the two keys, the attribute 2 included in both keys Means a key with a minimum value or value range that contains both values or value ranges. For example, a key obtained by summing a key (a = 3, b = 2-4) and a key (a = 4-5, b = 3-5, c = 1) is (a = 3-5, b = 2-5, c = 1). However, the present invention is not limited to this. For example, the value of the attribute included in the key obtained by summing two keys is a value including both the value of the attribute or the value range of the two keys. It is possible to use a value range and not necessarily a minimum value or value range.

  As described above, in step S12-4, the value of P1 ((child_num-th entry), X) (= P1 (A, B)) is substituted into the variable min_penalty. That is, when the entry X is inserted into the child_num-th entry of the node whose address is specified by the variable current, the number of attribute types included in the key included in the child_num-th entry before the entry X is inserted; The difference when comparing the number of attribute types included in the key included in the child_num-th entry after insertion (that is, the entry having a new key obtained by adding the child_num-th entry and the entry X) is a variable. It will be assigned to min_penalty.

  After step S12-4, it is determined whether or not the child_num-th entry of the node corresponding to the current (current node) exists (step S12-5). If there is, the child_num-th entry of the current node is input. The penalty value is calculated by the function P1 using the entry X as an argument, and the penalty value is compared with the magnitude of min_penalty (step S12-6).

  If min_penalty is greater or equal, the penalty value is again calculated by the function P1 using the child_num-th entry of the current node and the input entry X as an argument, and the magnitude of the penalty value and min_penalty are compared. However, if they are not equal, the list min_child_list is emptied, and the penalty value calculated from the function P1 is substituted for min_penalty using the child node's child_num-th entry and the input entry X as arguments (step S12-7). Step S12-8).

  Further, the value of child_num is added to the list min_child_list (step S12-9), child_num is incremented by 1 (step S12-10), and the process returns to step S12-5.

  In step S12-6, if min_penalty is smaller, the process proceeds to step S12-10.

  In step S12-7, if they are equal as a result of the comparison, the process proceeds to step S12-9.

  By repeatedly executing these steps S12-5 to S12-10, the function P1 is obtained for all entries of the current node, and the number of entries having the lowest function P1 in the list min_child_list is one or more. Will be stored.

  If it does not exist in step S12-5, 1 is substituted for variable i, i-th (that is, first) number of list min_child_list is substituted for variable child_num, and child_num is substituted for variable min_child (step S12). -11).

  A penalty value is calculated by the function P2 using the child_num-th entry of the current node and the input entry X as an argument, and is substituted for the variable min_penalty (step S12-12).

  The function P2 is defined as follows. A and B indicate entries.

  P2 (A, B) = Q2 (A + B) -Q2 (A)

  Here, Q2 (C) is the sum of the weighted normalized search area for each attribute included in the key included in entry C, and indicates the probability that entry C is searched. A + B indicates an entry having a new key obtained by adding the key of the entry A and the key of the entry B. This function P2 is a function representing “a penalty when the entry X is inserted with respect to the existing entry already included in the operation target node”, and the entry B is set to the existing entry A already included in the operation target node. At the time of insertion, the value corresponding to the probability that the entry A is searched when the entry A before the insertion of the entry B is compared with the entry A after the insertion (that is, the probability or It is defined as a value indicating an increase in the approximate value of the probability to be searched).

  Q2 (C) is defined as follows.

Q2 (C) = _ΣCi (S (Ci) · R (Ci))

Ci indicates an attribute included in the key of entry C. Σ _Ci (D) means the sum of D for all Ci. S (Ci) is a normalized search area, and is defined by the following equation as in Equation I.

S (Ci) = ((qCi -aCi) (bCi-pCi) - (qCi-pCi) 2/2) / ((bCi-aCi) 2/2)

  The pCi and qCi are the minimum value and maximum value of the attribute Ci described in the key, respectively. The aCi and bCi are the minimum value of the attribute Ci in the entire tuple set Y that has been inserted into the search tree so far. The maximum value. aCi and bCi can be obtained from the attribute table. However, when bCi−aCi = 0, S (Ci) takes a preset constant value.

  R (Ci) is a probability that the attribute Ci is used in the search formula, and is defined as follows.

  R (Ci) = (Number of occurrences of Ci in all tuple sets Y) / (number of elements in all tuple sets Y)

  The number of occurrences of Ci in all tuple sets Y can be obtained from the attribute table.

  In step S12-12, the value of P2 ((child_num-th entry), X) is substituted into the variable min_penalty. That is, when the entry X is inserted into the child_num-th entry of the node whose address is specified by the variable current, the child_num-th entry before the entry X is inserted is compared with the child_num-th entry after the insertion. In this case, a value indicating the increment of the value corresponding to the probability that the child_num-th entry is searched is substituted into the variable min_penalty. However, since 1 is substituted into the variable i in step S12-11 and the i-th number of the list min_child_list, that is, the first number is substituted into the variable child_num, when obtaining the function P2 in step S12-12, When the entry X is inserted into the entry having the number indicated by the first number in the node list min_child_list whose address is specified by the variable current, the entry before the entry X is inserted, and the entry after the insertion , The value indicating the increment of the value corresponding to the probability that the entry is searched is substituted into the variable min_penalty.

  Next, it is determined whether or not the i-th number of the list min_child_list exists (step S12-13). If it exists, the i-th number of the list min_child_list is substituted for child_num (step S12-14). , The child node's child_num-th entry and the input entry X as an argument are compared with the penalty value calculated by the function P2 and the magnitude of min_penalty (step S12-15). If min_penalty is greater or equal, The value of child_num is substituted for min_child, and the penalty value calculated by the function P2 using the child node's child_num-th entry and the input entry X as an argument is substituted for min_penalty. (Step S12-16). Then, i is incremented by 1 (step S12-17), and the process returns to step S12-13.

  In step S12-15, if min_penalty is smaller, the process proceeds to step S12-17.

  By repeating this step S12-16, the variable min_penalty is updated with the calculation result of the smallest function P2, and the number of the entry from which the calculation result of the smallest function P2 is obtained is substituted into the variable min_child. become.

  In step S12-13, if it does not exist, the address of the child node included in the min_child-th entry of the current node is substituted into current, the child node becomes a new current node, and lv is reduced by 1 (step S12- 18) Return to step S12-2.

  By repeatedly performing the above steps S12-13, S12-14, S12-15, S12-16, and S12-17, the list min_child_list is listed in the list min_child_list by the determination process using the function P1 among all the entries included in the current node. For all entries that have been uploaded, the value of the function P2 when the entry X is inserted is obtained. Then, when the calculation for all the entries listed is completed, the number of the entry from which the calculation result of the smallest function P2 is obtained is substituted for the variable min_child. When the calculation and comparison of the function P2 for all the listed entries are completed, the address of the min_child-th child node of the current node is substituted into the variable current in step S12-18, and the size of lv is 1 It is decremented and it returns to step S12-2. Therefore, for the child node designated by the entry having the smallest value of the function P2, the list of entries having the small number of attribute types included in the key included in the entry after the insertion by the function P1 is similarly applied. Then, the function P2 is calculated for all the entries listed, and the process for obtaining the entry having the smallest value of the function P2 is performed based on the calculation result.

  In step S12-2, if L is larger or equal, the current node is selected, and current is returned as the return value (step S12-19), and the process is terminated. In this example, since L = 0 (that is, the number of leaf node levels is substituted for L), the address is specified by the variable current when the level number lv of the current node has reached 0. The process ends when the node becomes a leaf node.

  Next, FIG. 14 to FIG. 16 show the node division procedure flow called in step S11-4 in FIG. This node division procedure is a process called by using a node to be divided (node N and its address as N) and entry X as arguments. 14 to 16 are connected to each other by a connector S or T.

  First, the input entry X is added to the entry table of the node (node N) corresponding to the input node address N (step S13-1). When called from step S11-4 in FIG. 12, since the node to be divided is a leaf node, an entry X is added to the entry table of the leaf node.

  1 and 2 are substituted for variables i and j, respectively (step S13-2), and an initial value of d_max is calculated by the following equation (step S13-3). Here, the variables i and j are variables for temporarily storing the number of the processing target entry in the division target node. The variable d_max is a variable for temporarily storing the maximum value of the calculation result using the function P1 or the like. In these steps S13-2 to S13-3, those variables are initialized.

  d_max = P1 (i-th entry of node N, j-th entry of node N) −Q1 (j-th entry of node N)

  From the definition of the function P1 described above, the variable d_max is defined as d_max = P1 (i-th entry of node N, j-th entry of node N) −Q1 (j-th entry of node N) = Q1 (i of node N -Th entry + j-th entry of node N) -Q1 (i-th entry of node N) -Q1 (j-th entry of node N).

  Further, the list d_max_pairs is emptied (step S13-4), and it is determined whether or not the jth entry in the entry table of the node N exists (step S13-5). This list d_max_pairs is a variable in which the number of a set of one or a plurality of entries that maximizes d_max (the set of i and j described above) is stored.

  In step S13-5, if it exists, the magnitudes of i and j are compared (step S13-6). If they are not equal, the following d is calculated (step S13-7).

  d = P1 (i-th entry of node N, j-th entry of node N) −Q1 (j-th entry of node N)

  From the definition of the function P1, the variable d is d = P1 (i-th entry of node N, j-th entry of node N) −Q1 (j-th entry of node N) = Q1 (i-th entry of node N + j-th entry of node N) −Q1 (i-th entry of node N) −Q1 (j-th entry of node N)

  Next, the magnitudes of d and d_max are compared (step S13-8). If d_max is smaller or equal, the magnitudes of d and d_max are compared again (step S13-9). The list d_max_pairs is emptied and d is substituted for d_max (step S13-10). Further, a pair of values (i, j) is added to the list d_max_pairs (step S13-11), i is incremented by 1 (step S13-12), and the process returns to step S13-6.

  In step S13-8, when d_max is larger, the process proceeds to step S13-12.

  In step S13-9, if the result of comparison is equal, the process proceeds to step S13-11.

  In step S13-6, if they are equal as a result of the comparison, 1 is substituted for i (step S13-13), j is further increased by 1 (step S13-14), and the process returns to step S13-5.

  Through the processing of these steps S13-6 to S13-14, the value of d is maximized from all entries of the node N to be divided (that is, a set of entries in which the entry X is added to the existing entries of the node N). One or plural sets of two entries are selected, and a value (number) indicating a pair of selected entries is stored in the list d_max_pairs.

  If it does not exist in step S13-5, 1, 0, 0, and 0 are assigned to variables k, d_max, i_max, and j_max, respectively (step S13-15). Here, the variable k is a variable for temporarily storing a number indicating a storage position of a value (element) in the list d_max_pairs. Variables i_max and j_max are variables for temporarily storing a set of entry numbers having the maximum calculation result using the function P2 or the like. The variable d_max is a variable for temporarily storing the maximum value of the calculation result using the function P2 or the like. In step S13-15, these variables are initialized.

  The procedure from step S13-4 to step S13-15 is performed by examining “a pair of two entries having the smallest number of attribute types included in both entries among the entries included in node N”. Although it can be said that the number of the entry is entered in the list d_max_pairs, the scope of the present invention is not limited to this, and this procedure is defined as “the largest number of attribute types included in only one of the entries included in the node N 2. One entry pair "may be examined, and the number of the two entries may be replaced with a procedure for entering the list d_max_pairs. For this purpose, the following d may be used instead of d used in step S13-7.

  d = P1 (i-th entry of node N, j-th entry of node N) + P1 (j-th entry of node N, i-th entry of node N)

  Next, it is determined whether or not the k-th element of the list d_max_pairs exists (step S13-16). If there is, the two numbers constituting the pair that is the k-th element of the list d_max_pairs are respectively set to i. , J is substituted (step S13-17).

  Further, the following d is calculated (step S13-18).

  d = P2 (i-th entry of node N, j-th entry of node N) −Q2 (j-th entry of node N)

  From the definition of the function P2 described above, the variable d is d = P2 (i-th entry of node N, j-th entry of node N) −Q2 (j-th entry of node N) = Q2 (i of node N -Th entry + j-th entry of node N) -Q2 (i-th entry of node N) -Q2 (j-th entry of node N).

  The magnitudes of d and d_max are compared (step S13-19), and if d_max is smaller or equal, the values of i, j, and d are substituted for i_max, j_max, and d_max, respectively (step S13-20). . Further, k is incremented by 1 (step S13-21), and the process returns to step S13-16.

  In step S13-19, when d_max is larger, the process proceeds to step S13-21.

  By repeatedly executing the processing of these steps S13-6 to S13-21, in all the entry pairs stored in the list d_max_pairs, the number of a pair of entries maximizing the above d is the variables i_max and j_max. Will be assigned to.

  If it does not exist in step S13-16, the i_maxth entry of node N is put in the group G1 of entries, the j_maxth entry is put in group G2, and both are deleted from the entry table of node N (step S13-16). S13-22). Here, the entry set included in G1 and G2 is an empty set as an initial state, and includes one entry each when step S13-22 is completed.

  It is determined whether the value obtained by subtracting the number of entries in G1 from the minimum value T1 of the number of entries in the entry table at node N is equal to or greater than the number of entries remaining in the entry table of node N ( Step S13-23) If equal or larger, all entries remaining in the entry table of the node N are put into the group G1 and deleted from the entry table (step S13-24).

  If it is determined as NO in step S13-23, step S13-24 is not performed.

  Further, it is determined whether or not the value obtained by subtracting the number of entries in G2 from T1 is equal to or greater than the number of entries remaining in the entry table of node N (step S13-25). Puts all entries remaining in the entry table of the node N into the group G2 and deletes them from the entry table (step S13-26).

  If it is determined as NO in step S13-25, step S13-26 is not performed.

  In the processing of these steps S13-23 to S13-26, the number of entry sets to be assigned (distributed) to the group G1 and the group G2 from the entry table of the node N falls below the minimum entry value T1 at each node. This is a process for avoiding this. In step S13-47 or S13-48, which will be described later, the entries included in the entry table of node N are sequentially distributed to group G1 or group G2 and deleted from the entry table of node N. At this time, for example, even if there is a case where the distribution is biased to one group, at least T1 entries are assigned to the groups G1 and G2 by the processing of steps S13-23 to S13-26. It has become.

  1 and 0 are assigned to i and d_max, respectively, the list mas_entry is emptied (step S13-27), and it is determined whether or not the i-th entry Ei in the entry table of the node N exists (step S13-28). ). Here, the variable i is a variable for temporarily storing the number of the processing target entry in the division target node. The variable d_max is a variable for temporarily storing the maximum value of the calculation result in step S13-29 using the function P1 or the like. The list mas_entry is a variable that stores one or a plurality of entry numbers corresponding to the variable d_max. In step S13-27, these variables are initialized.

  If it exists in step S13-28, the following d is calculated (step S13-29). However, (G1) and (G2) indicate entries having new keys obtained by summing the keys of all the entries included in the groups G1 and G2.

  d = | P1 ((G1), Ei) −P1 ((G2), Ei) |

  This expression of d is obtained as an entry B having a new key obtained by summing the keys of all entries included in the group G1 in the function P1 defined above as an entry B into which the entry Ei is inserted. The difference between the value of the function P1 and the value of the function P1 obtained as the entry B having the new key obtained by adding the keys of all the entries included in the group G2 as the existing entry A and the entry B into which the entry Ei is inserted. This is an operation for substituting the absolute value into the variable d. That is, the magnitude of the difference between the penalty P1 when inserting into the group G1 and the penalty P1 when inserting into the group G2 for the i-th entry still remaining in the entry table of the node N is a variable. will be assigned to d.

  The magnitudes of d and d_max are compared (step S13-30). If d_max is smaller or equal, the magnitudes of d and d_max are compared again (step S13-31). The list max_entry is emptied, d is substituted for d_max (step S13-32), and i is further added to the list max_entry (step S13-33). i is increased by 1 (step S13-34), and the process returns to step S13-28. In step S13-30, if d_max is larger, the process proceeds to step S13-34.

  If equal in step S13-31, the process proceeds to step S13-33.

  By repeatedly executing the processes in steps S13-28 to S13-34, one or a plurality of entries having the maximum d is assigned to the list max_entry among all entries in the entry table of entry N. Will be.

  If it does not exist in step S13-28, first, 1, 1, and 0 are assigned to variables i, i_max, and d_max, respectively (step S13-35). Here, the variable i is a variable for temporarily storing a number indicating a storage position of a value (element) in the list max_entry. The variable i_max is a variable for temporarily storing the number of the entry having the maximum calculation result in step S13-38 using the function P2 or the like. The variable d_max is a variable for temporarily storing the maximum value of the calculation result in step S13-38 using the function P2 or the like. In step S13-35, these variables are initialized.

  Next, it is determined whether or not the i-th element (number) of the list max_entry exists (step S13-36). If it exists, the i-th number in the list max_entry is substituted into the variable c (step S13-37).

  Further, the following d is calculated (step S13-38). Ec indicates the c-th entry in the entry table of node N.

  d = | P2 ((G1), Ec) −P2 ((G2), Ec) |

  This expression of d is obtained as an entry B having the new key obtained by summing the keys of all the entries included in the group G1 in the function P2 defined above as an entry B into which the entry Ec is inserted. The difference between the value of the function P2 and the value of the function P2 obtained as the entry B having the new key obtained by adding the keys of all the entries included in the group G2 as the existing entry A and the entry B into which the entry Ec is inserted. This is an operation for substituting the absolute value into the variable d. That is, the difference between the penalty P2 when inserting into the group G1 and the penalty P2 when inserting into the group G2 for the cth entry among the entries still remaining in the entry table of the node N is a variable. will be assigned to d.

  Next, the magnitudes of d and d_max are compared (step S13-39). If d_max is smaller or equal, i and d are substituted for i_max and d_max, respectively (step S13-40). It is incremented by 1 (step S13-41) and the process returns to step S13-36.

  In step S13-39, when d_max is larger, the process proceeds to step S13-41.

  By repeatedly performing these steps S13-36 to S13-41, the value of the penalty P2 for all the entry numbers stored in the list max_entry is assigned to the group G1 and assigned to the group G2. The storage position (number) in the list max_entry of the entry number with the largest difference is stored in the variable i_max.

  In step S13-36, if it does not exist, it is determined whether or not the i_max-th element of the list max_entry exists (step S13-42). If it exists, the i_max-th number of the list max_entry is set as a variable c. (Step S13-43). Further, the magnitudes of P1 ((G1), Ec) and P1 ((G2), Ec) are compared (step S13-44), and if P1 ((G2), Ec) is greater or equal, The magnitudes of P1 ((G1), Ec) and P1 ((G2), Ec) are compared again (step S13-45).

  If P1 ((G2), Ec) is smaller or equal, the magnitudes of P2 ((G1), Ec) and P2 ((G2), Ec) are further compared (step S13-46). If P2 ((G2), Ec) is greater or equal, Ec is entered into G1, deleted from the entry table (step S13-47), and the process returns to step S13-23.

  In step S13-44, if P1 ((G2), Ec) is smaller, Ec is entered in G2, deleted from the entry table (step S13-48), and the process returns to step S13-23.

  In step S13-45, if P1 ((G2), Ec) is larger, the process proceeds to step S13-47.

  In step S13-46, if P2 ((G2), Ec) is smaller, the process proceeds to step S13-48.

  In steps S13-43 to S13-48, the value of the i_max-th element of the list max_entry is c, and all entries included in the entry B, group G1, or G2 into which the c-th entry Ec of the entry table of the node N is inserted Entry Ec is assigned to one of the groups with the smaller value of function P1 with entry A having a new key that is the sum of the two keys as entry A, and deleted from the entry table. That is, when the value of the function P1 obtained from the group G2 and the entry Ec is smaller than the value of the function P1 obtained from the group G1 and the entry Ec (in the case of “YES” in step S13-44). The entry Ec is put into the group G2. On the other hand, when the value of the function P1 obtained from the group G1 and the entry Ec is smaller than the value of the function P1 obtained from the group G2 and the entry Ec (in the case of “YES” in step S13-45). The entry Ec is put into the group G1. Further, when the value of the function P1 obtained from the group G1 and the entry Ec is equal to the value of the function P1 obtained from the group G2 and the entry Ec (in the case of “NO” in step S13-45), The entry P with the c-th entry Ec in the entry table of the node N and the entry having a new key obtained by summing the keys of all entries included in the group G1 or G2 are set as the entry A, and the value of the function P2 is The entry Ec is distributed to one of the smaller groups and deleted from the entry table. That is, when the value of the function P2 obtained from the group G2 and the entry Ec is smaller than the value of the function P2 obtained from the group G1 and the entry Ec (in the case of “YES” in step S13-46). The entry Ec is put into the group G2. On the other hand, if not (if “NO” in step S13-46), the entry Ec is placed in the group G1.

  If it does not exist in step S13-42, the G1 entry set is entered into the node N entry table, a new node N 'is generated, and the G2 entry set is entered into the entry table (step S13-49). After all the entries of the node N are distributed to the group G1 or the group G2, no entry exists in the entry table of the node N. In this case, since the determination results in steps S13-28, S13-36, and S13-42 are all “NO”, the process proceeds to step S13-49, and all of the nodes assigned to the group G1 in the entry table of node N are processed. An entry is entered, and all entries distributed to the group G2 are entered in the entry table of the newly generated node N ′.

  Next, it is determined whether or not the node N is a root node (step S13-50). If it is not the root node, it is determined whether or not the number of entries in the entry table held by the parent node of the node N is less than T2. (Step S13-51).

  If it is less than T2, the entry table of the parent node of the node N has an entry corresponding to the new node N ′, that is, a key obtained by summing the keys of all the entries in the entry table of the node N ′ as a key. In addition, an entry having a pointer to the node N ′ is added (step S13-52).

  In step S13-50, if node N is the root node, a new node N ″ is generated and set as the parent node of node N. That is, the node N holds a pointer to the node N ″ as a parent node. Further, an entry corresponding to the node N is added to the entry table of the node N ″ (step S13-53), and the process proceeds to step S13-52.

  After step S13-52, a key set information adjustment procedure using the parent node of node N as an input is performed (step S13-55), and the process ends.

  In step S13-51, if it is not less than T2, a node division procedure is performed in which the parent node of node N and the entry corresponding to N ′ are input (that is, the node division procedure shown in FIGS. 14 to 16 is recursively performed). Calling) (step S13-54), the process proceeds to step S13-55.

  An example of how a node is divided by the node dividing procedure is shown in FIG. In this example, T1 = 2 and T2 = 4. As shown on the left side of FIG. 17, let us consider a state in which entries E1 to E10 are held in the entry table of each node in a search tree composed of three nodes N1 to N3.

  The entry E10 is finally inserted into the search tree. When the number of entries held in the entry table of the node N3 becomes 5, which exceeds T2, the node division procedure is performed to reduce the number of entries. (Steps S11-2 and S11-4 in FIG. 12). As a result, as shown in the right of FIG. 17, the node N3 is divided into N3 and a new node N4, and a part of the entries held by N3 moves to N4 (steps S13-1 in FIGS. 14 to 15). -Step S13-49). Accordingly, the entry E11 corresponding to the new node N4 is added to the entry table of N1 which is the parent node of N3 (step S13-52 in FIG. 16).

  FIG. 18 shows another example of how a node is divided by the node dividing procedure. As in the example shown in FIG. 17, in the node division procedure, a new entry is added to the entry table of the parent node of the node to be divided. As a result, when the number of entries held by the parent node is T2 or more, the parent node is further subject to node division (steps S13-51 and S13-54 in FIG. 16).

  FIG. 18 shows an example where the parent node is the root node. As shown in FIG. 18, when the root node N1 is divided, not only is it divided into N1 and a new node N7, but a new node N8 is generated as a root node, and entries corresponding to N1 and N7 Are stored in the entry table (steps S13-50, S13-53, and S13-52 in FIG. 16). At this time, the hierarchy of the search tree increases by one, and the number of levels of the root node increases by one.

  Next, FIG. 19 shows a key set information adjustment procedure flow called in step S11-5 of FIG. 12 or step S13-55 of FIG. First, it is determined whether or not the node (node N) indicated by the node address N input as an argument is a root node (step S17-1).

  If it is not the root node, the key of the entry corresponding to the node N in the entry table of the parent node of the node N, that is, the entry holding the address of the node N as a pointer, is the key corresponding to the node N at that time That is, the key is overwritten with the key obtained by summing the keys of the entry set in the entry table of the node N (step S17-2).

  Further, a key set information adjustment procedure using the parent node of the node N as an input is performed (recursively called) (step S17-3), and the process ends.

  In step S17-1, if it is the root node, the process is finished as it is.

  In this embodiment, the tuple ID is included in the leaf node entry and the tuple itself is stored in the tuple table. However, the scope of the present invention is not limited to this, and the tuple itself is included in the leaf node entry. It is also possible to

  In this embodiment, the value obtained by dividing the number of appearances of the attribute by the total number of tuples is used as an approximate value of the probability that each attribute is used in the search formula. However, the scope of the present invention is not limited thereto, and each attribute is searched by the search formula. It is also possible for the database manager to input the probabilities used in the above in advance, or to calculate based on the statistical information of the search formula actually used by the user.

  In the present embodiment, in the penalty calculation by the function P2, all attributes included in the keys of the two entries to be input are considered. However, the scope of the present invention is not limited thereto, and the probability of being used in a search expression is high. It is also possible to consider only the terms for the top 10 attributes among the attributes. That is, other attribute terms may be regarded as 0.

  In this embodiment, the probability that each attribute is used in the search expression is treated as independent. However, the scope of the present invention is not limited to this, and the co-occurrence of each attribute, that is, the probability of appearing simultaneously in one search expression is considered. It is also possible to calculate a penalty. For example, when the probability that a search expression including the attribute aA and the attribute aB is used as a condition is R, the weighted normalized search area for the combination of attributes is (normalized search area of the attribute aA) × (attribute aB Normalization searched area) × R, and an increase in the sum of such weighted normalized searched areas for all combinations of all attributes may be used as a penalty.

  Further, in this embodiment, when a certain attribute is used in the search expression, it is assumed that two values indicating the start point and end point of the specified value range are selected with a uniform probability within the domain of the attribute. It is assumed that the output value of the probability density function that inputs the start point and the end point and outputs the probability that the value range is specified in the search formula is constant when the point in the domain of the attribute is input. The scope of the present invention is not limited thereto, and the probability density function can be input in advance by the database administrator, or can be calculated based on the statistical information of the search formula actually used by the user. Also, for example, if a value closer to the current time is more easily searched for a time attribute, another probability density function is assumed, such as using a probability density function that outputs a higher value as a value range closer to the current time is input. Is also possible.

  Next, search processing in the system of this embodiment will be described. In the search processing, in response to the tuple search request received from the client computer apparatus 301, the calculation unit 203 of the server computer apparatus 201 first satisfies the search condition indicated by the received search expression from the index held by the storage unit 204. Get the tuple ID set. Specifically, after the search result tuple ID list is emptied, a node search procedure is executed with the root node of the index held in the storage unit 204 as a search target node, whereby the ID set is included in the search result tuple ID list. Can be obtained. Further, the tuple table stored in the storage unit 204 is referred to, a tuple set corresponding to the ID set is extracted, and the tuple set is transmitted as a search result to the client computer apparatus 301 that is the tuple search request source.

  A node search procedure flow is shown in FIG. The flow shown in FIG. 20 is a flow of a node search procedure using the above search tree. For a search key that is a key as a search expression, while changing the search target from a root node to a lower node, 1 This is called when a search is performed using one node as a search target node, and is recursively called in step S18-7.

  First, it is determined whether or not the search target node is a leaf node (step S18-1). If the search target node is a leaf node, the entry satisfying the search condition is searched among the entries described in the entry table of the search target node. It adds to a result tuple ID list (step S18-2), and complete | finishes a process.

  If it is not a leaf node in step S18-1, first, 1 is substituted into variable i (step S18-3), and it is determined whether or not the i-th entry in the entry table included in the search target node exists. (Step S18-4). If not, the process ends.

  In step S18-4, if the i-th entry exists, whether or not a tuple satisfying the search condition can exist in a node below the child node indicated by the pointer included in the entry is included in the entry. It is determined from the key (step S18-5). If not, the variable i is incremented by 1 (step S18-6), and the process returns to step S18-4.

  In step S18-5, if it can exist, the node search procedure is recursively performed with the child node pointed to by the entry pointer as the search target node (step S18-7).

  According to the present embodiment, a single tree structure index is uniformly constructed for various multi-dimensional tuples, and as a penalty, a value corresponding to a search probability before and after entry insertion (that is, search probability) Or an approximate value of the probability of being searched). With this penalty, it is not necessary to determine the magnitude relationship for each dimension, and it can be defined even if the number of key dimensions and types included in the entry are different. This suppresses the overhead caused by using multiple indexes when accumulating / retrieving various multi-dimensional tuple sets, that is, the amount of processing, storage capacity, and processing speed, and increases the number of multi-dimensional tuple sets. On the other hand, it is possible to realize clustering that improves search efficiency.

In the present embodiment, in calculating the penalty, the weighted normalized search area for each attribute included in the key included in the entry is used as a value corresponding to the probability that the entry is searched, and the weight is calculated. The normalized normalized search area is a value obtained by multiplying the normalized search area by the probability that the attribute is used in the search expression, and the normalized search area is expressed by the formula ((q−a) ( ^{b-p) - (q-} p) 2/2) / ((b-a) 2/2) ( where, p, respectively q is the minimum value of the attribute included in the key, the maximum value .a, b is defined by (Expression I)) (minimum value and maximum value of the attribute included in all tuple sets that have been inserted into the search tree so far).

  When a certain attribute is used in the search expression and a range condition specifying the value range of the attribute is used in the search expression, two values indicating the start point and end point of the value range are identical in the definition area of the attribute. Assuming that it is chosen with a similar probability, the probability that the entry needs to be accessed is approximated by Equation I. The value obtained by Expression I is the normalized search area. The weighted normalized search area is obtained by multiplying the normalized search area by the probability that the attribute is used in the search expression. Therefore, the sum of the weighted normalized search area for each attribute included in the key included in the entry is the probability or probability that the entry must be accessed in order to search for a tuple that matches the search condition. Is an approximate value. By using the sum of the weighted normalized search areas as a penalty and constructing a search tree under the strategy of reducing the penalty as much as possible, the number of entries that must be accessed during the search can be reduced as a whole. . That is, it is possible to improve the search processing amount and processing speed.

  The correspondence relationship between the configuration characterized by the present invention and the configuration in the above embodiment is as follows.

  A feature of the present invention is that a tuple (FIG. 3), which is a unit of information to be stored and searched, has one or more lengths including at least an array of attribute-value pairs. A plurality of one or more tuples having the same or different lengths are stored, a search key is indexed from the tuples, and a search tree (FIG. 6) is constructed. (The root node 401, the inner node 402, and the leaf node 403 in FIG. 6) are hierarchically arranged, and the leaf node at the lowest layer among the nodes is a tuple identifier (tuple ID) and a key for identifying the tuple as an entry. (FIG. 8), and an inner node higher than the leaf node among the nodes has a pointer and a key as position information of a child node which is a lower node as an entry. (FIG. 9), in the construction of the index, when an entry is inserted into a node, one entry X to be inserted and the number of levels L to insert the entry (each time the hierarchy goes up with leaf nodes set to 0) Is given (step S11-1 in FIG. 12, flow in FIG. 13), the root node is first set as the operation target node (step S12-1 in FIG. 13). The existing entry having the smallest penalty when the entry X is inserted is selected from the existing entries already included in the operation target node (steps S12-13, S12-14, S12-15, S12-16 in FIG. 13). , S12-17), the child node indicated by the pointer included in the existing entry is selected as the next operation target node (step of FIG. 13). S12-18) If the number of levels of the next operation target node is larger than L (“NO” in step S12-2 in FIG. 13), the next operation target node is further selected from the next operation target node. This is repeated recursively (steps S12-13, S12-14, S12-15, S12-16, S12-17, S12-18 in FIG. 13), and the level number of the next operation target node has reached L. In this case (“YES” in step S12-2 in FIG. 13), the step of setting this node as the selected node (step S12-19 in FIG. 13) and the case where the selected node does not have the maximum number of allowable entries (“YES” in step S11-2 of FIG. 12), a step of adding entry X to the selected node (step S11-3 of FIG. 12), and the selected node is already allowed When the maximum number of entries is possible (“NO” in step S11-2 in FIG. 12), the step of dividing the selected node while adding entry X (step S11-4 in FIG. 12, FIG. 14 to FIG. 14) Steps after Steps S13-1 and S13-2 in FIG. 15), and the step of updating the entry of the upper node of the selected node in the case of division (Steps S11-5 in FIG. 12, the flow in FIG. 19) , Including. For example, when the entry B is inserted into the existing entry A already included in the operation target node, the penalty is compared between the entry A before the entry B is inserted and the entry A after the insertion. In this case, it can be defined as a value indicating an increment of a value corresponding to the probability that the entry A is searched (function P2, steps S12-12, 12-15, and S12-16 in FIG. 13).

  In another invention, the step of performing the above-described division is performed when each entry obtained by adding the entry X to a plurality of entries included in the selected node is sequentially allocated to two groups (steps S13-47 and S13- in FIG. 15). 48) Based on each penalty obtained for each group with the entry ((G1), (G2)) that is the sum of the entries already included in each group as the existing entry A and the distributed entry (Ec) as the entry B The step of selecting a group to be distributed (steps S13-36 to S13-48 in FIG. 15) and each entry distributed to one of the two groups as the entry of the selected node At the same time, each entry assigned to the other group is set as a newly created node entry. And (step S13-49 in FIG. 15), a step (step S13-52 in FIG. 16) for inserting an entry for the newly created node in the parent node of said node, characterized in that it comprises a.

  Another invention is characterized in that the step of determining the selected node selects an existing entry having the smallest penalty in the operation target node (step S12-18 in FIG. 13).

In another invention, when the entry B is inserted into the existing entry A already included in the operation target node, the penalty is compared between the entry A before the entry B and the entry A after the insertion. In this case, the entry A is defined as a value indicating an increment of a value corresponding to the probability that the entry A is searched (function P2, steps S12-12, 12-15, and S12-16 in FIG. 13), and the entry A is searched. As a value corresponding to the probability (Q2 (C)), a sum of weighted normalized search areas for each attribute included in the key included in entry A (Σ _Ci (S (Ci) · R (Ci))) The weighted normalized searched area is a value obtained by multiplying the normalized searched area (S (Ci)) by the probability that the attribute is used in the search formula (R (Ci)). Normalized search area is a formula ((Q-a) (b -p) - (q-p) 2/2) / ((b-a) 2/2) ( where, p, respectively q is the attribute minimum contained in the key Value and maximum value, a and b are respectively defined by the minimum value and the maximum value of the attribute included in all tuple sets inserted in the search tree. Note that the minimum value of the attribute included in the key corresponds to pCi, the maximum value corresponds to qCi, the minimum value of the attribute included in all tuple sets inserted in the search tree corresponds to aCi, and the maximum value corresponds to bCi. It is also a thing.

  In another invention, when the entry B is inserted into the existing entry A already included in the operation target node, the penalty is compared between the entry A before the entry B and the entry A after the insertion. In this case, it is a value indicating the increment (function P1) of the number of attribute types (Q1 (C)) included in the key included in the entry A.

  In another invention, the step of determining the selected node uses two types of penalties (function P1 and function P2), and selects an existing entry having the smallest first penalty (function P1) at the operation target node. (Steps S12-3 to 12-10 in FIG. 13) At this time, when there are a plurality of the smallest existing entries, the second penalty (function P2) is the smallest among the smallest existing entries. An existing entry is selected (steps S12-11 to 12-18 in FIG. 13).

  According to another invention, when the first penalty (function P1) inserts the entry B into the existing entry A already included in the operation target node, the entry A before the entry B is inserted, Is a value indicating the increment of the number of attribute types (Q1 (C)) included in the key included in the entry A when compared with the entry A after the operation is performed. Probability that the entry A is searched when the entry A is inserted into the existing entry A that is already included and the entry A before the entry B is inserted is compared with the entry A after the insertion. It is a value (function P2) indicating the increment of the value (Q2 (C)) corresponding to.

Also, other inventions? As a value (Q2 (C)) corresponding to the probability that the entry is searched, the sum of the weighted normalized search areas (Σ _Ci (S (Ci) · R ( Ci))) is used.

  Another invention uses a value obtained by dividing the number of attribute appearances by the total number of tuples as the probability (R (Ci)) that the attribute is used in the search expression, and the number of attribute appearances has been inserted into the search tree so far. The total number of tuples is the number of elements of all tuple sets that have been inserted in the search tree so far ((number of occurrences of Ci in all tuple sets Y) / (all The number of elements of the tuple set Y)).

  Further, in another search using the above-described search tree (the flow of FIG. 20), the search target is changed from a root node to a lower node with respect to a search key that is a key as a search expression. If one of the nodes is a search target and the node is an inner node (“NO” in step S18-1 in FIG. 20), for each entry included in the node, the key of the entry is included in the search key. A value or value range corresponding to each attribute included in the search key and a value or value range corresponding to the attribute included in the key of the entry match or partially match (including one attribute) A search procedure is performed to check whether the value or value range is included or partially overlaps the other value range (steps S18-4 and S18-5). "YES" in step S18-5), the node search procedure is performed recursively using the node connected by the pointer of the entry as a search target and the search key as a search key (step S18-7). If it is a leaf node (“YES” in step S18-1), for each entry included in the node, the key of the entry includes all the attributes included in the search key, and each attribute included in the search key Whether the value corresponding to the attribute or the value corresponding to the attribute included in the key of the entry is included, and if included, add the tuple identifier of the entry to the search result tuple identifier set (step S18- 2) and a node search step.

  Further, the present invention can also be regarded as other aspects as follows.

  According to another aspect of the present invention, as a penalty of a search tree, in addition to a penalty based on the sum of weighted normalized search areas (function P2), the number of attribute types included in a key included in an entry The increase amount (function P1) was used. As a result, the dimensionality of the entry can be suppressed more strongly and the problem of “curse of dimension” can be suppressed more than when only the increased amount of the sum of the weighted normalized search areas is used as a penalty. . That is, two search tree penalties are used, and the first penalty is the “increase in the number of attribute types included in the key included in the entry” (function P1), and the second penalty is entry insertion. The amount of increase in the search probability before and after or the approximate value of the search probability, that is, the “increase amount of the sum of the weighted normalized search areas for each attribute included in the key included in the entry” (function P2 ), In the subtree selection procedure, when there are a plurality of entries having the smallest first penalty (determined in step S12-13 in FIG. 13), the second penalty is compared between them (FIG. 13). In step S12-15), the entry having the smallest second penalty is selected (step S12-18 in FIG. 13). As a result, the search tree construction method has both the dimension increase reduction effect by the first penalty and the search efficiency improvement effect by the second penalty. In particular, when the “increase in the sum of weighted normalized search areas for each attribute included in the key included in the entry” is used as the second penalty, the first penalty is only the attribute type. In contrast, it can be said that this is a search tree construction method that combines “the effect of improving the search efficiency by considering the value of each attribute (dimension)” by the second penalty.

DESCRIPTION OF SYMBOLS 101 Network 201 Server computer apparatus 202 Communication part 203 Operation part 304 Storage part 301 Client computer apparatus 302 Communication part 303 Tuple / retrieval expression display part 401 Root node 402 Inner node 403 Leaf node 501 Tuple table 502 Inner node entry table 503 Leaf node entry table 504 Attribute table

Claims (20)

A tuple that is a unit of information to be stored and searched has one or more lengths including at least a list of attribute-value pairs, and one or more types of the attributes and the lengths of the arrays are the same or different. A plurality of the tuples are stored, a search key is indexed from the tuples, and a search tree is constructed. The search tree has a structure having nodes in a hierarchy. The lower leaf node has a tuple identifier and key for identifying the tuple as an entry, and an inner node higher than the leaf node of the node has a pointer which is position information of a child node which is a lower node as an entry. Has a key,
In building the index, when inserting an entry into a node:
Given one entry X to be inserted and the number L of levels to insert the entry (the number of hierarchies that increases by 1 each time the hierarchy goes up with the leaf node as 0),
First, the root node is the operation target node,
In the operation target node, one existing entry is selected based on “the penalty when the entry X is inserted for the existing entry already included in the operation target node”,
The child node indicated by the pointer included in the existing entry is selected as the next operation target node,
If the number of levels of the next operation target node is greater than L, recursively repeating the selection of the next operation target node from the next operation target node,
When the number of levels of the next operation target node has reached L, determining this node as a selected node;
Adding the entry X to the selected node if the selected node does not have the maximum number of allowable entries;
Splitting the selected node while adding the entry X when the selected node already has the maximum number of allowable entries;
In the case of performing the division, updating the entry of the upper node of the selected node;
An information storage and retrieval method comprising: The step of performing the division according to claim 1,
When each entry obtained by adding the entry X to a plurality of entries included in the selected node is sequentially distributed to two groups, an entry obtained by summing the entries already included in each group is defined as an existing entry A, and the entries that are distributed Selecting a group as a distribution destination based on each penalty determined for each group as an entry B, and performing a distribution;
Each entry distributed to one of the two groups as an entry of the selected node, and each entry distributed to another group as an entry of a newly generated node;
Inserting the newly generated node entry into the parent node of the node;
An information storage and retrieval method comprising: The step of determining a selection node according to claim 1 or 2,
An information storage and retrieval method, wherein the existing entry having the smallest penalty is selected in the operation target node. The penalty of claim 3 is
When the entry B is inserted into the existing entry A already included in the operation target node, the entry A when the entry A before the entry B is inserted is compared with the entry A after the insertion. Is defined as a value indicating the increment in value corresponding to the probability of being searched,
As a value corresponding to the probability that the entry A is searched,
Using the sum of the weighted normalized search area for each attribute included in the key included in the entry A,
The weighted normalized search area is
It is a value obtained by multiplying the normalized search area by the probability that the attribute is used in the search formula,
The normalized search target area, the formula ((q-a) (b -p) - (q-p) 2/2) / ((b-a) 2/2)
(Where p and q are the minimum value and maximum value of the attribute included in the key, respectively. A and b are the minimum value of the attribute included in all tuple sets that have been inserted into the search tree so far. Maximum value.)
Stipulated in
An information storage and retrieval method characterized by the above. The penalty of claim 3 is
When the entry B is inserted into the existing entry A already included in the operation target node, the entry A when the entry A before the entry B is inserted is compared with the entry A after the insertion. A method for storing and retrieving information, wherein the value indicates an increment of the number of attribute types included in a key included in the key. The step of determining a selection node according to claim 1 or 2,
Using the two types of penalties,
In the operation target node, when the existing entry having the smallest first penalty is selected, and there are a plurality of the smallest existing entries at this time, the second penalty is further selected among the smallest existing entries. An information storage and retrieval method characterized by selecting the smallest existing entry. In claim 6,
When the entry B is inserted into the existing entry A already included in the operation target node, the first penalty compares the entry A before the entry B is inserted with the entry A after the insertion. Value indicating the increment of the number of attribute types included in the key included in the entry A,
When the entry B is inserted into the existing entry A already included in the operation target node, the second penalty compares the entry A before the entry B is inserted with the entry A after the insertion. In this case, the information storage retrieval method is characterized in that the value indicates an increment of a value corresponding to the probability that the entry A is retrieved. In claim 7,
As a value corresponding to the probability that the entry is searched,
A method for storing and retrieving information, wherein the sum of the weighted normalized search areas for each attribute included in the key included in the entry is used. In claim 4 or 8,
As a probability that the attribute is used in the search formula, a value obtained by dividing the number of attribute appearances by the total number of tuples,
The number of appearances of the attribute is the number of appearances of the attribute in all tuple sets inserted in the search tree so far.
The total number of tuples is the number of elements of all tuple sets that have been inserted into the search tree so far.
An information storage and retrieval method characterized by the above. In the search using the search tree according to claim 1 to 9,
For the search key that is the key as a search expression,
While changing the search target from the root node to the node below it,
One such node is the search target,
If the node is the inner node, for each entry included in the node, the key of the entry includes all the attributes included in the search key and corresponds to each attribute included in the search key The value or value range and the value or value range corresponding to the attribute included in the key of the entry match or partially match (one value or value range is included or partially overlaps the other value range) ), And if there is a match or partial match, the node search procedure is performed recursively using the node connected by the pointer of the entry as a search target and the search key as a search key. ,
If the node is the leaf node, for each entry included in the node, the key of the entry includes all the attributes included in the search key, and each attribute included in the search key includes A node search step of checking whether a corresponding value or value range includes a value corresponding to the attribute included in the key of the entry, and if included, adding the tuple identifier of the entry to a search result tuple identifier set;
An information storage and retrieval method characterized by comprising: A tuple that is a unit of information to be stored and searched has one or more lengths including at least a list of attribute-value pairs, and one or more types of the attributes and the lengths of the arrays are the same or different. A plurality of the tuples are stored, a search key is indexed from the tuples, and a search tree is constructed. The search tree has a structure having nodes in a hierarchy. The lower leaf node has a tuple identifier and key for identifying the tuple as an entry, and an inner node higher than the leaf node of the node has a pointer which is position information of a child node which is a lower node as an entry. Has a key,
In building the index, when inserting an entry into a node:
Given one entry X to be inserted and the number L of levels to insert the entry (the number of hierarchies that increases by 1 each time the hierarchy goes up with the leaf node as 0),
First, the root node is the operation target node,
In the operation target node, one existing entry is selected based on “the penalty when the entry X is inserted for the existing entry already included in the operation target node”,
The child node indicated by the pointer included in the existing entry is selected as the next operation target node,
If the number of levels of the next operation target node is greater than L, recursively repeating the selection of the next operation target node from the next operation target node,
When the number of levels of the next operation target node has reached L, determining this node as a selected node;
Adding the entry X to the selected node if the selected node does not have the maximum number of allowable entries;
Splitting the selected node while adding the entry X when the selected node already has the maximum number of allowable entries;
In the case of performing the division, updating the entry of the upper node of the selected node;
Information storage and retrieval program for executing the program using a computer. The step of dividing according to claim 11 comprises the steps of:
When each entry obtained by adding the entry X to a plurality of entries included in the selected node is sequentially distributed to two groups, an entry obtained by summing the entries already included in each group is defined as an existing entry A, and the entries that are distributed Selecting a group as a distribution destination based on each penalty determined for each group as an entry B, and performing a distribution;
Each entry distributed to one of the two groups as an entry of the selected node, and each entry distributed to another group as an entry of a newly generated node;
Inserting the newly generated node entry into the parent node of the node;
An information storage and retrieval program characterized by including: The step of determining a selection node according to claim 11 to 12,
The information storage / retrieval program, wherein the existing entry having the smallest penalty is selected in the operation target node. The penalty of claim 13 is
When the entry B is inserted into the existing entry A already included in the operation target node, the entry A when the entry A before the entry B is inserted is compared with the entry A after the insertion. Is defined as a value indicating the increment in value corresponding to the probability of being searched,
As a value corresponding to the probability that the entry A is searched,
Using the sum of the weighted normalized search area for each attribute included in the key included in the entry A,
The weighted normalized search area is
It is a value obtained by multiplying the normalized search area by the probability that the attribute is used in the search formula,
The normalized search target area, the formula ((q-a) (b -p) - (q-p) 2/2) / ((b-a) 2/2)
(Where p and q are the minimum value and maximum value of the attribute included in the key, respectively. A and b are the minimum value of the attribute included in all tuple sets that have been inserted into the search tree so far. Maximum value.)
Stipulated in
An information storage and retrieval program characterized by that. The penalty of claim 13 is
When the entry B is inserted into the existing entry A already included in the operation target node, the entry A when the entry A before the entry B is inserted is compared with the entry A after the insertion. An information storage / retrieval program characterized by being a value indicating an increase in the number of attribute types included in a key included in. The step of determining a selection node according to claim 11 to 12,
Using the two types of penalties,
In the operation target node, when the existing entry having the smallest first penalty is selected, and there are a plurality of the smallest existing entries at this time, the second penalty is further selected among the smallest existing entries. An information storage and retrieval program characterized by selecting the smallest existing entry. In claim 16,
When the entry B is inserted into the existing entry A already included in the operation target node, the first penalty compares the entry A before the entry B is inserted with the entry A after the insertion. Value indicating the increment of the number of attribute types included in the key included in the entry A,
When the entry B is inserted into the existing entry A already included in the operation target node, the second penalty compares the entry A before the entry B is inserted with the entry A after the insertion. In this case, the information storage retrieval program is characterized in that the entry A is a value indicating an increment of a value corresponding to the probability of retrieval. In claim 17,
As a value corresponding to the probability that the entry is searched,
A summation of the weighted normalized search area for each attribute included in the key included in the entry is used. In claim 14 or 18,
As a probability that the attribute is used in the search formula, a value obtained by dividing the number of attribute appearances by the total number of tuples,
The number of appearances of the attribute is the number of appearances of the attribute in all tuple sets inserted in the search tree so far.
The total number of tuples is the number of elements of all tuple sets that have been inserted into the search tree so far.
An information storage and retrieval program characterized by that. In the search using the search tree according to claim 11 to 19,
For the search key that is the key as a search expression,
While changing the search target from the root node to the node below it,
One such node is the search target,
If the node is the inner node, for each entry included in the node, the key of the entry includes all the attributes included in the search key and corresponds to each attribute included in the search key The value or value range and the value or value range corresponding to the attribute included in the key of the entry match or partially match (one value or value range is included or partially overlaps the other value range) ), And if there is a match or partial match, the node search procedure is performed recursively using the node connected by the pointer of the entry as a search target and the search key as a search key. ,
If the node is the leaf node, for each entry included in the node, the key of the entry includes all the attributes included in the search key, and each attribute included in the search key includes A node search step of checking whether a corresponding value or value range includes a value corresponding to the attribute included in the key of the entry, and if included, adding the tuple identifier of the entry to a search result tuple identifier set;
An information storage and retrieval program characterized by comprising:

Images