JP6683200B2 - Information processing apparatus, information processing method, and recording medium storing information processing program - Google Patents

Description

  The present invention relates to an information processing device, an information processing method, and an information processing program.

  In the above technical field, in Non-Patent Document 1, when managing data, by reusing a statistical value for each block calculated in advance at the time of statistical processing, scan of records is omitted and I / O (Input / Input) A technique for reducing the amount of output and the amount of calculation and speeding up statistical processing is disclosed.

Oyamada et al., "Achieving High-speed and Accurate Data Aggregation Processing by Partial Aggregation of Data", Database System Research Group Report 2014-DBS-160 (19), pp. 1-7, 2015 (http://ci.nii.ac.jp/naid/110009842514)

  However, in the technique described in the above-mentioned document, it is not possible to efficiently reuse the statistical value calculated in advance in block units unless the preset block unit is set, and the statistical processing can be speeded up. There wasn't.

  An object of the present invention is to provide a technique that solves the above problems.

In order to achieve the above object, the information processing apparatus according to the present invention,
Access frequency management means for storing and managing the access frequency to a set of data,
Dividing means for dividing the set having the access frequency equal to or higher than a first predetermined value into at least two subsets;
And a calculating means for calculating a statistical value for each of the divided subsets.

In order to achieve the above object, the information processing method according to the present invention,
An access frequency management step of storing and managing the access frequency to a set of data,
A dividing step of dividing the set having the access frequency of a first predetermined value or more into at least two subsets;
A calculation step of calculating a statistical value for each of the divided subsets.

In order to achieve the above object, the recording medium according to the present invention,
An access frequency management step of storing and managing the access frequency to a set of data,
A dividing step of dividing the set having the access frequency of a first predetermined value or more into at least two subsets;
An information processing program for causing a computer to execute a calculation step of calculating a statistical value for each of the divided subsets is stored.

  According to the present invention, the statistical value calculated in advance can be efficiently reused, and the statistical processing can be speeded up.

It is a block diagram which shows the structure of the information processing apparatus which concerns on 1st Embodiment of this invention. It is a figure explaining the construction of the partial aggregation tree by the information processing apparatus which concerns on 2nd Embodiment of this invention. It is a figure explaining the division | segmentation procedure of the leaf node in the partial aggregation tree by the information processing apparatus which concerns on 2nd Embodiment of this invention. It is a block diagram which shows the functional structure of the information processing apparatus which concerns on 2nd Embodiment of this invention. It is a figure explaining the holding content of the file holding part of the information processor concerning a 2nd embodiment of the present invention. It is a figure explaining the holding content of the partial aggregation tree holding part of the information processor concerning a 2nd embodiment of the present invention. It is a block diagram which shows the hardware constitutions of the information processing apparatus which concerns on 2nd Embodiment of this invention. It is a flowchart which illustrates the flow of the process performed when inputting data in the information processing apparatus which concerns on 2nd Embodiment of this invention. It is a flowchart which illustrates the flow of a process at the time of inquiry execution in the information processing apparatus which concerns on 2nd Embodiment of this invention. It is a flow chart explaining a division processing procedure of a leaf node by an information processor concerning a 2nd embodiment of the present invention. It is a figure explaining the merge procedure of the leaf node in the partial aggregation tree by the information processing apparatus which concerns on 3rd Embodiment of this invention. It is a figure explaining the merge procedure of the leaf node in the partial aggregation tree by the information processing apparatus which concerns on 3rd Embodiment of this invention. It is a block diagram which shows the functional structure of the information processing apparatus which concerns on 3rd Embodiment of this invention. It is a block diagram which shows the hardware constitutions of the information processing apparatus which concerns on 3rd Embodiment of this invention. It is a flowchart which illustrates the flow of a process at the time of execution of an inquiry in the information processing apparatus which concerns on 3rd Embodiment of this invention. It is a flowchart explaining the merge processing procedure of the leaf node in the partial aggregation tree by the information processing apparatus which concerns on 3rd Embodiment of this invention.

  Embodiments of the present invention will be illustratively described in detail below with reference to the drawings. However, the constituent elements described in the following embodiments are merely examples, and the technical scope of the present invention is not intended to be limited thereto.

[First Embodiment]
An information processing apparatus 100 according to the first embodiment of the present invention will be described with reference to FIG.
The information processing apparatus 100 includes an access frequency management unit 101, a division unit 102, and a statistical value calculation unit 103.

  The access frequency management unit 101 stores and manages the access frequency to a set of data.

  The dividing unit 102 generates, based on the access frequency managed by the access frequency managing unit 101, a subset obtained by dividing a set having an access frequency equal to or higher than a first predetermined value into at least two.

  The statistical value calculation unit 103 calculates a statistical value for each of the divided subsets.

  According to the present embodiment, the subset divided according to the access frequency is automatically generated, and the statistical value of the generated subset is automatically calculated. As a result, the statistical value calculated in advance can be efficiently reused even if it is not a block unit (subset unit) set in advance, and the statistical processing can be speeded up.

[Second Embodiment]
Next, an information processing apparatus according to the second embodiment of the present invention will be described with reference to FIGS. 2A to 8B. In all the drawings, the same constituents will be given the same reference numeral, and the description thereof will not be repeated.

<< Prerequisite technology >>
A relational database system (Relational DataBase Management System) holds tabular data (hereinafter referred to as a table) based on a relational model and provides a user with efficient retrieval and updating of data. A row in a table is called a record and represents one piece of data. The data can have several attributes, with a column in the table corresponding to each attribute. The <column name, data type> list of columns included in the table is called the table schema.

  A user of the relational database system instructs the relational database system by a programming language to perform a search process and an update process for a table. This instruction is called a query. A programming language called SQL (Structured Query Language) is used as a standard to describe a query. By using SQL, it is possible to easily and efficiently retrieve the records that satisfy the conditions from the table. Also, by specifying the column name, you can retrieve only the required attributes from the record.

  One of the processes frequently performed in relational database systems is attribute statistical processing. The attribute statistical processing is to calculate a certain statistical value from a value group of a predetermined attribute in the table, and examples of the statistical value include a maximum value, a minimum value, an average value and a standard deviation.

  Attribute statistics are often performed on all or most of the records in a table. Therefore, if the table is huge, a large number of records will be scanned, and a large amount of I / O processing and calculation processing will occur, resulting in a long processing speed.

<< Description of this embodiment >>
In the present embodiment, a set of data is divided, a statistic value is calculated for each divided subset, and when a query is made, the statistic value is used for calculation to speed up the calculation speed.
Further, in the present embodiment, a partial aggregation tree structure is used when dividing.

  FIG. 2A shows a set of data having three attributes, for example, age (age), weight (weight), and height (height), with age (age) as a key attribute and a height of 1 (meaning that division is performed in one step). ) Is a diagram showing a partial aggregation tree. In the figure, ellipses represent nodes 201, 202, and 203 of the partial aggregation tree, and rectangles represent actual divided data (subsets) 204 and 205. Each node 201, 202, 203 divides the value range of the key attribute into two, and the nodes 202, 203 (leaf nodes) at the bottom have pointers to the actual data 204, 205 and the statistical values calculated for that section. Hold. As a result, the data 204, 205 that is a subset and the leaf nodes 202, 203 are associated with each other. Further, the data which is the value range of the age as a key attribute is divided into two data, that is, data 0 to 49 years old 204 and data 50 to 100 years old 205. In addition, the statistical values (maximum value: max, minimum value: min, average value: mean, total value: sum, number of data: count) of the remaining attributes (weight: weight, height: height) are calculated in each section. ing.

  Furthermore, for a leaf node whose access frequency exceeds a predetermined threshold value, the tree grows as the leaf nodes 202 and 203 are repeatedly divided, and statistical values are calculated in smaller units. This increases the probability that the statistics will be reused. In other words, the leaf node division process divides the area of the key attribute value that a certain leaf node is responsible for into two, distributes the data group under the control of the original leaf node to each area, and then calculates the statistical values of those areas. Is recalculated and a new leaf node is generated. For example, in the partial aggregation tree of FIG. 2A, when the leaf node 202 in charge of the age of [0,49] is divided, the leaf node 206 in charge of the age of [0,24] and [25,49] as shown in FIG. 2B. ], Two leaf nodes 207 in charge of the age are generated. Data (subsets) 208 and 209 are generated corresponding to the leaf nodes 206 and 207, respectively.

  2A and 2B, the access frequency is represented as access count [count: x]. Further, when the leaf node is divided, the access frequency (access count [count: x]) of the newly generated leaf node is initialized to 0.

<< Functional configuration of this embodiment >>
FIG. 3 is a block diagram for explaining the functional configuration of the information processing apparatus according to this embodiment. In FIG. 3, each block does not represent a hardware-based configuration but a functional-based configuration.

  The information processing device 300 includes a data input unit 301, a file operation unit 302, a file holding unit 303, a partial aggregation tree management unit 304, a partial aggregation tree holding unit 305, an inquiry receiving unit 306, and an inquiry execution unit 307. Each will be described below.

<Data input section>
The data input unit 301 inputs data to be processed by the information processing device 300. An example of the data format is table data in a relational database system. The table data is tabular data, and each row of the table is one record (eg staff information), and each column of the table is an attribute value of the record (eg staff age, height, gender, etc.).

  There are various methods by which the data input unit 301 acquires data. For example, the data input unit 301 acquires data input from an external device. In addition, for example, the data input unit 301 manually inputs data. Furthermore, the data input unit 301 may access an external device by communication or the like and input data.

<File operation part>
The file operation unit 302 performs file generation processing and file reading processing.
The file generation process is a process of converting the data input from the data input unit 301 into a file for storage in a storage device such as a main storage device or a secondary storage device, and holding the data in the file holding unit 303. In the file reading process, the file operation unit 302 receives from the query execution unit 307 the file name in which the data is held, the offset value to start reading, and the size of the read data. Furthermore, the file operation unit 302 acquires the corresponding data from the file holding unit 303 and returns it to the query execution unit 307 in the file reading process.

<File holding section>
The file holding unit 303 holds the file generated by the file operation unit 302 in the storage device. The storage device may be a main storage device or a secondary storage device.

<Partially aggregated tree holding unit>
The partial aggregation tree holding unit 305 partially calculates a statistical value for the data held by the file holding unit 303, and holds the result. Here, the data structure used for holding the statistical values is referred to as a partial aggregation tree. The partial aggregation tree is a data structure based on a binary tree, and is used for speeding up the “processing for reusing a statistical value calculated in advance in statistical value processing” described in Non-Patent Document 1.

  The partial aggregation tree is a data structure that holds statistical data after partially dividing the data for data having at least two attributes (eg, age, weight, height). The partial aggregation tree uses arbitrary attribute values for data division. The attribute value used for division is called a key attribute.

  The partial aggregation tree divides the range of key attributes into two in order, and calculates and holds partial statistical values of the data group corresponding to each range. By increasing the number of divisions, that is, by increasing the height of the partial aggregation tree, it is possible to calculate the statistical value more finely, and it becomes easy to reuse the statistical value by the technique described in Non-Patent Document 1.

<< Partial Aggregation Tree Management Department >>
The partial aggregation tree management unit 304 includes a partial aggregation tree operation unit 341, a division instruction unit 342, and an access frequency management unit 343.

  The partial aggregation tree operation unit 341 divides the data set into two or more subsets, and calculates a statistical value of data for each of the divided subsets.

  Based on the access frequency managed by the access frequency management unit 343, the division instruction unit 342 instructs the partial aggregation tree operation unit 341 to generate a further divided subset for the subset with high access frequency.

  The access frequency management unit 343 stores and manages the access frequency to each subset. The access frequency managed by the access frequency management unit 343 is, for example, the number of accesses within a predetermined time.

The partial aggregation tree management unit 304 uses the partial aggregation tree operation unit 341 to operate the partial aggregation tree held in the partial aggregation tree holding unit 305 based on the inquiry from the query execution unit 307.
Further, the partial aggregation tree management unit 304 uses the access frequency management unit 343 to count the number of accesses from the query execution unit 307 to the subset including the data to be inquired and manage the counted value.

  The operations performed by the partial aggregation tree operation unit 341 include splitting of leaf nodes, merging of leaf nodes, and execution of statistical processing.

<< Inquiry reception section >>
The inquiry receiving unit 306 acquires a processing instruction for the data held in the file holding unit 303. As an example of the method used to describe the instruction, there is SQL (Structured Query Language), which is a type of programming language that describes a query for data.

  Examples of queries include processing that aggregates statistical values such as maximum value, minimum value, average value, and standard deviation from data, and selection, join, projection processing, and the combination of these processing that are used in relational databases. Information processing.

<< Inquiry execution unit >>
The inquiry execution unit 307 executes the inquiry acquired by the inquiry reception unit 306. At this time, the query execution unit 307, through the partial aggregation tree management unit 304, information about whether the statistical values calculated in advance in the query can be reused depending on the query range, and the range if reusable. To get the statistical value of. For the range in which the statistical value cannot be reused, the data in the file holding unit 303 is accessed through the file operation unit 302 to calculate the statistical value. Then, the query execution unit 307 constructs the final query result by merging the statistical values of each range.

<< Contents held by file holding unit >>
Next, the contents held in the file holding unit 303 will be described with reference to FIG.

  As shown in FIG. 4, the file holding unit 303 holds, for example, a table 400, and the table 400 includes an identifier (ID: Identifier) 401 of each element, data 402, and an identifier (ID) 403 of a block to which the element belongs. . The data 402 includes data such as age, height, and weight as in the above example.

<< Contents held by the partial aggregation tree holding unit >>
Next, the contents held in the partial aggregation tree holding unit 305 will be described with reference to FIG.

  As illustrated in FIG. 5, the partial aggregation tree holding unit 305 holds a table 500, and the table 500 includes a block ID 501, an active flag 502, the number of elements 503, a statistical value 504, a height (division level) 505, and a parent block. It has an ID 506 and an access count number 507.

<< Example of hardware configuration >>
Next, an example of the hardware configuration of the information processing apparatus according to the present embodiment will be described with reference to FIG.

  As illustrated, the information processing apparatus 300 includes a CPU (Central Processing Unit) 601, a ROM (Read Only Memory) 602, a communication control unit 603, and a RAM (Random Access Memory) 604. Further, the information processing unit 300 includes a storage 605, an output interface 606, a display unit 607, a printer 608, and an input unit 610. The CPU 601 is a central processing unit, and controls the entire information processing apparatus 300 by executing various programs.

  The ROM 602 is a read-only memory, and stores a boot program to be executed first by the CPU 601 and various parameters. Further, the communication control unit 603 controls communication with various devices via the network. The RAM 604 is a random access memory, and includes input data 641, division target block node (aggregation tree) 642, divided block (leaf node) 643, statistical value 644, inquiry information 645, response information 646, input / output data 647, and It includes transmission / reception data 648.

  Further, the storage 605 has a partial aggregation tree holding unit 305 and a file holding unit 303. Further, the storage 605 has a data input module 651, an inquiry reception module 652, an access frequency management module 653, and a file operation module 654. Furthermore, the storage 605 has a query execution module 655, a partial aggregation tree operation module 656, a division instruction module 657, a data output module 658, and the like.

  The input unit 610 also includes a reader 611, a keypad 612, a touch panel 613, and an input interface 615 that transfers inputs from these to the CPU 601. Here, the reader 611 is, for example, a barcode reader, but may be an RFID (Radio Frequency Identifier) tag reader or the like.

  On the other hand, the reply to the inquiry received by the inquiry receiving module 652 via the input unit 610 or the communication control unit 603 is transmitted to the external device via the communication control unit 603. Alternatively, it is output to the display unit 607 and the printer 608 via the output interface 606.

  The data input unit 301 includes a CPU 601, a ROM 602, a communication control unit 603, a RAM 604, an input unit 610, and a data input module 651.

  The file operation unit 302 includes a CPU 601, a ROM 602, a RAM 604, and a file operation module 654.

  The partial aggregation tree management unit 304 includes a CPU 601, a ROM 602, a RAM 604, an access frequency management module 653, a partial aggregation tree operation module 656, and a division instruction module 657.

  The inquiry receiving unit 306 includes a CPU 601, a ROM 602, a communication control unit 603, a RAM 604, an input unit 610, and an inquiry receiving module 652.

  The query execution unit 307 includes a CPU 601, a ROM 602, a RAM 604, and a query execution module 655.

<Process flow>
FIG. 7 is a flowchart illustrating the flow of processing executed when data is input in the information processing apparatus 300 of this embodiment. In step S701, the data input unit 301 acquires data. In step S703, the file operation unit 302 converts the data into a file. In step S705, the file operation unit 302 saves the file in the file holding unit 303.

  FIG. 8A is a flowchart exemplifying the flow of processing when an inquiry is executed in the information processing apparatus 300 of this embodiment. In step S801, the inquiry reception unit 306 acquires an inquiry. In step S <b> 803, the query execution unit 307, which receives the instruction from the query reception unit 306, searches the partial aggregation tree management unit 304 for the inquired partial aggregation tree. Further, in step S805, the query execution unit 307 determines whether or not the statistical value precalculated by the statistical processing of the partial aggregation tree obtained by the search can be reused.

  If the result of this determination is that reuse is possible, in step S807 the query execution unit 307 acquires the precalculated statistical value from the partial aggregation tree holding unit 305. If it cannot be reused, in step S809, the query execution unit 307 instructs the partial aggregation tree management unit 304 to reuse the query in the future, divides the leaf node into trees, and Perform growth process. As a result, the query execution unit 307 divides the data set corresponding to this leaf node into two or more subsets and grows the tree.

  In this way, when the query execution unit 307 finishes acquiring the statistical values necessary for executing the query, in step S811, the statistical values are integrated to calculate the query result. After that, in step S813, the query execution unit 307 updates the access frequency recorded in the leaf node of the partial aggregation tree through the partial aggregation tree management unit 304.

  Next, details of the processing in step S809 will be described with reference to FIG. 8B.

  In step 821, when the query execution unit 307 divides the data set corresponding to the leaf node into two or more subsets, the query execution unit 307 acquires the access frequency (count value of the number of accesses) of the leaf node. Next, in step S823, the query execution unit 307 determines whether or not the count value of any leaf node exceeds a predetermined threshold value α. If the result of this determination is that the count value exceeds the threshold value α, then in step S825, the query execution unit 307 divides the leaf nodes whose count value exceeds the threshold value α. Next, in step S827, the query execution unit 307 calculates the statistic value of the leaf node newly generated by the division, and proceeds to the processing of step S811.

  If the result of determination in step S823 is that the count value does not exceed the threshold value α, the query execution unit 307 moves to the processing in step S811.

  According to the information processing device 300 of the present embodiment, a subset of data having a statistical value with a high access frequency is automatically detected, a subset with a high access frequency is divided, and each obtained subset is divided. Statistics are newly calculated and stored. Therefore, the probability that the statistical value calculated in advance in the statistical processing can be reused is increased, and the performance of the statistical processing is improved. Furthermore, even if it is not a preset block unit, that is, a preset subset unit of data, it is possible to reuse the statistical value calculated automatically in advance, omitting the record scan and calculating the I / O amount. The amount can be reduced and the attribute statistical processing can be speeded up.

In the present embodiment, information processing is performed as a tree structure in which nodes are assigned to each of the data set and the subset obtained by dividing the data set, but the present invention is not limited to this.
For example, it goes without saying that the same effect can be obtained by processing information without using a tree structure.

  Further, in the present embodiment, the number of accesses within a predetermined time is taken as the access frequency, and a subset having a statistical value with a high access frequency is divided, but when the number of accesses to the subset exceeds a preset threshold, the access frequency is May be determined to be high, and this subset may be divided.

  Further, in the present embodiment, the subset with high access frequency is divided into two, but it may be divided into three or more.

[Third Embodiment]
Next, an information processing apparatus according to the third embodiment of the present invention will be described with reference to FIGS. 9A to 12B. The information processing apparatus according to the present embodiment is different from the above-described second embodiment in that a leaf node having the smallest access count value is merged with another leaf node. Since other configurations and operations are similar to those of the second embodiment, the same configurations and operations are denoted by the same reference numerals and detailed description thereof will be omitted.

  For example, for a set of data having three attributes of age (age), weight (weight), and height (height) as in the second embodiment, the partial aggregation tree shown in FIG. It was built. At this time, the leaf node 904 having the smallest access number is merged with the leaf node 903 having the second smallest access number. That is, in FIG. 9A, a leaf node 904 in charge of the age of [0,24], a leaf node 905 in charge of the age of [25,49], and a leaf node 903 in charge of the age of [50,100] are provided. Exists. The leaf node 904 has 8 accesses, the leaf node 903 has 10 accesses, and the leaf node 905 has 50 accesses. Therefore, the leaf node 904 has the smallest number of accesses, and the leaf node 903 has the second largest number of accesses. Therefore, the leaf node 903 and the leaf node 904 are merged, and the partial aggregation tree of FIG. 9B is constructed. When the leaf nodes are merged, the access count (access count [count: x]) of the newly generated leaf node is initialized to 0.

  By merging leaf nodes with a small number of accesses (access frequency) in this way, the number of statistical values can be reduced, and the storage area for storing the statistical values (holding size of the entire statistical values) can be reduced. it can.

<< Functional configuration of this embodiment >>
FIG. 10 is a functional block diagram for explaining the configuration of the information processing device according to the present embodiment. The information processing apparatus 1000 according to the present embodiment is different from that of the second embodiment in that it includes a partial aggregation tree management unit 1001 including a partial aggregation tree operation unit 1041 and a merge instruction unit 1044. Since other configurations and operations are similar to those of the second embodiment, the same configurations and operations are denoted by the same reference numerals and detailed description thereof will be omitted.

  The partial aggregation tree operation unit 1041 divides the data set into two or more subsets based on the instruction of the division instruction unit 342, and calculates a statistical value of data for each divided subset. Further, the partial aggregation tree operation unit 1041 merges two or more subsets into one based on the instruction of the merge instruction unit 1044, and calculates the statistical value of the subset obtained by the merge. Here, the leaf node and the data of this leaf node are called a subset.

  The merging instructing unit 1044 generates a partial aggregation tree based on the access frequency managed by the access frequency managing unit 343 so as to generate a subset merged with another subset having a low access frequency with respect to the subset having the lowest access frequency. Instruct the operation unit 1041. If both adjacent sub-sets have low access frequency, they are merged. When the access frequency of the subset adjacent to the subset with the lowest access frequency is larger than the predetermined value R, the subset with the lowest access frequency is merged with the non-adjacent subset. At this time, the subset having the lowest access frequency is merged with the subset having the access frequency equal to or lower than the predetermined value Q (<R). Further, the number of merged subsets may be three or more.

<< Hardware configuration of the present embodiment >>
FIG. 11 is a block diagram for explaining the hardware configuration of the information processing apparatus 1000 according to this embodiment. The information processing apparatus 1000 according to the present embodiment is different from the second embodiment in that the RAM 604 has a threshold value 1141 and the storage 605 has a merge instruction module 1151. Since other configurations and operations are similar to those of the second embodiment, the same configurations and operations are denoted by the same reference numerals and detailed description thereof will be omitted.

<Process flow>
The processing at the time of accepting an inquiry in the information processing apparatus 1000 of this embodiment differs from that of the second embodiment in that leaf node merging processing is added. FIG. 12A will be described with reference to the flowchart of the process at the time of accepting an inquiry in this embodiment. The same parts as those in the second embodiment are represented by the same reference numerals, and the description thereof will be omitted. The process of the present embodiment and the process of the second embodiment are different in that the processes of steps S1201 and S1202 are added between steps S809 and S811. That is, after the processing of step S809, in step S1201, the query execution unit 307 sets the number of statistic values to be held, that is, the number of leaf nodes, in advance via the input unit 610 through the partial aggregation tree management unit 1001. The maximum allowable number is exceeded.

If the result of this determination is that the number of statistical values is less than or equal to the maximum allowable number, then the flow shifts to step S811. If the result of determination in step S1201 indicates that the number of statistical values exceeds the maximum allowable number, in step S1202 the partial aggregation tree management unit 1001 accesses the subset recorded in the leaf node. Check the frequency, and merge the leaf nodes whose access frequency is less than a predetermined value. By doing so, the number of statistical values is reduced and the tree is degenerated so that it is within the maximum allowable number. Here, degeneracy of the tree means reducing the number of leaf nodes.
When the acquisition of the statistical values required for executing the inquiry is completed in this way, in step S811, the inquiry execution unit 307 integrates the statistical values and calculates the inquiry result.

  Next, details of the processing in step 1202 will be described with reference to FIG. 12B.

  In step 1221, when the query execution unit 307 merges the subset corresponding to the leaf node with the smallest access count with the subset of another leaf node, the query execution unit 307 determines that the access frequency of the leaf node (count of the access count). Value). Next, in step S1223, the query execution unit 307 selects the node having the minimum access count value. In step S1225, the query execution unit 307 acquires the count values of the nodes on both sides of the node with the smallest count value. Further, in step S1227, the query execution unit 307 merges with the node having the smaller access count value from the nodes on both sides to generate a new leaf node and new data. Next, in step S1229, the query execution unit 307 calculates the statistical value of the leaf node data obtained by the merge. After that, the query execution unit 307 proceeds to the process of step S1015.

  In the second embodiment, the tree grows as the leaf node division processing is repeated, and the statistical value is calculated in smaller units. This increases the probability that the statistics will be reused. However, since the number of statistical values increases each time the data set is divided, the data size of the partial aggregation tree can be enlarged. Therefore, in the present embodiment, the maximum allowable number of statistic values held by the partial aggregation tree is set, and if the number of statistic values exceeds the maximum allowable number after dividing the leaf node, an appropriate leaf node is merged. So I try to keep the number of stats below the maximum allowed. In other words, it is not necessary to maintain statistical values in small units for a subset that includes data areas that are rarely referenced. Therefore, the partial aggregation tree stores the access frequency of the user to the subset of the data corresponding to the leaf nodes, and the subset of the data corresponding to the “least referenced leaf node” is defined as at least one adjacent subset. Choose to be merged. At this time, an average value of two or three access frequencies to be merged is calculated, and when the average value is less than or equal to a predetermined value, the merge is performed. This makes it possible to avoid merging a subset with low access frequency and a subset with high access frequency. It should be noted that the adjacent subset may be merged with the one with a lower access frequency. Further, when the access frequency of the adjacent subsets is equal to or higher than the predetermined threshold, the non-adjacent subsets may be merged as long as the access frequency is equal to or lower than the predetermined threshold. Further, the number of merged subsets may be three or more.

  Note that a simple LRU (Least Recently Used) algorithm (http://en.wikipedia.org/wiki/Page_replacement_algorithm#Least_recently_used) may be used to manage the access frequency. Alternatively, Clock (http://en.wikipedia.org/wiki/Page_replacement_algorithm#Clock), which is a lightweight alternative algorithm, may be used.

  The leaf node merging process in the partial aggregation tree management unit 1001 merges the areas in charge of two adjacent leaf nodes having the same parent node to generate a new leaf node, and replaces the parent node with the new leaf node. . At this time, it is necessary to calculate the statistic value of the new leaf node, but this can be implemented by merging the statistic values of the two original leaf nodes. That is, there is no need to scan the actual data again to recalculate the statistics. For example, if the left leaf node had a maximum value of 70 and the right leaf node had a maximum value of 150, the maximum value of the merged leaf node would be 150 based on Max (70,150). Recognize.

Next, a specific example will be described. Here, we describe an algorithm for statistical processing using a partial aggregation tree. First, consider the following function compare (range, query).
function compare (range, query) {
if (query.min <range.min) {
if (query.max <range.min) return OUTSIDE_QUERY;
if (query.max <range.max) return PART_DATA_IN_QUERY;
return ALL_DATA_IN_QUERY;
}
if (query.min === range.min && range.max <= query.max) return ALL_DATA_IN_QUERY;
if (query.min <= range.max) return PART_DATA_IN_QUERY;
return OUTSIDE_QUERY;
}
The function compare (range, query) receives the range [range.min, range.max] of the key attributes of a node and the refinement condition [query.min, query.max] for the key attributes in the query, and then the node. "All data is outside the range of the query (OUTSIDE_QUERY)", "Some data is within the range of the query (PART_DATA_IN_QUERY)", "All data is within the range of the query (ALL_DATA_IN_QUERY)" Returns one of the values.

Then, the tree search function computeAggregation (node, query) is as follows.
function computeAggregation (node, query) {
// Check if the data under this node is inside or outside the range of query
// Check using the compare function
answer = compare (node.range, query);
if (answer == OUTSIDE_QUERY) {
// The data under node is outside the range of query, so do not search further
return null;
}
if (answer == ALL_DATA_IN_QUERY) {
// All the data under node is within the range of query, so we will use the statistical values calculated in advance
return node.getPrecomputedAggregations ();
}
if (answer == PART_DATA_IN_QUERY) {
if (node instanceof LeafNode) {
// I searched to the leaf node but could not reuse it
// Split the node so that it can be reused in this section in the future
// Read the data from the data holding part and calculate the statistical value
node.split (query);
}
// search to reuse statistics of its own children
var leftAggregations = computeAggregation (node.leftChild, query);
var rightAggregations = computeAggregation (node.leftChild, query);
// Merge and return the stats from both children
return leftAggregations.merge (rightAggregations);
}
}
This function recursively searches the partial aggregation tree, and each node "all data is out of the query range (OUTSIDE_QUERY)", "some data is within the query range (PART_DATA_IN_QUERY)", "all data" Within the range of the query (ALL_DATA_IN_QUERY) ”is determined.

And
If "all data is outside the range of the query (OUTSIDE_QUERY)", the nodes below that node are out of the target of the query, and searching is useless. abort.

  If "some data is within the range of the query (PART_DATA_IN_QUERY)", the statistical value cannot be reused at the granularity of the node. However, since the lower node calculates the statistical value in a finer granularity and may be reused, the lower node continues the search recursively. If the node has no children, split the node so that statistics can be reused if the same query comes in the future.

  If "all the data is within the range of the query (ALL_DATA_IN_QUERY)", all the data related to the node is subject to the query, and the statistical value calculated in advance is reused. After that, when the statistical value is obtained from each node, the statistical value is integrated and the final inquiry result is calculated.

  In this embodiment, information processing is performed as a tree structure in which nodes are assigned to each of the data set and the subset obtained by dividing the data set. However, the present invention is not limited to this, and it goes without saying that the same effect can be obtained even if information processing is performed without using a tree structure.

  Further, in the present embodiment, the number of accesses within a predetermined time is taken as the access frequency, and a subset having a statistical value with a high access frequency is divided, but when the number of accesses to the subset exceeds a preset threshold, the access frequency is May be determined to be high, and this subset may be divided.

  Further, in the present embodiment, the subset with high access frequency is divided into two, but it may be divided into three or more.

  According to this embodiment, the probability that the statistical value calculated in advance in the statistical processing can be reused is increased, and the performance of the statistical processing is improved. Furthermore, it is possible to reuse the statistical values that have been automatically calculated in advance without using the preset subset unit, omit the scan of records, reduce the I / O amount and the calculation amount, and perform the statistical processing of attributes. Can be speeded up. Furthermore, a subset including a data area with low access frequency is automatically merged with at least one adjacent subset, and the number of statistics is always kept below the maximum allowable number. Can be prevented, and a decrease in data search efficiency can be prevented.

[Other Embodiments]
Although the present invention has been described with reference to the exemplary embodiments, the present invention is not limited to the above exemplary embodiments. Various changes that can be understood by those skilled in the art can be made to the configuration and details of the present invention within the scope of the present invention. Further, a system or apparatus in which any combination of different features included in each embodiment is included in the scope of the present invention.

  Further, the present invention may be applied to a system composed of a plurality of devices or may be applied to a single device. Furthermore, the present invention can be applied to a case where an information processing program that realizes the functions of the embodiments is directly or remotely supplied to a system or an apparatus. Therefore, in order to realize the functions of the present invention by a computer, a program installed in the computer, a medium storing the program, and a WWW (World Wide Web) server for downloading the program are also included in the scope of the present invention. . In particular, a non-transitory computer readable medium storing a program that causes a computer to execute at least the processing steps included in the above-described embodiments is included in the scope of the present invention.

[Other Expressions of Embodiment]
The whole or part of the exemplary embodiments disclosed above can be described as, but not limited to, the following supplementary notes.
(Appendix 1)
Access frequency management means for storing and managing the access frequency to a set of data,
Dividing means for dividing the set having the access frequency equal to or higher than a first predetermined value into at least two subsets;
Calculating means for calculating a statistical value for each of the divided subsets,
Information processing device provided with.
(Appendix 2)
The information processing apparatus according to appendix 1, wherein the dividing unit initializes an access frequency of the divided subset.
(Appendix 3)
3. The information processing apparatus according to appendix 1 or 2, wherein the dividing unit executes the division when the statistical value is accessed.
(Appendix 4)
4. The information processing device according to any one of appendices 1 to 3, further comprising a management unit that manages the statistical values included in the subset as a tree structure.
(Appendix 5)
5. The information processing apparatus according to any one of appendices 1 to 4, further comprising a merging unit that merges at least two of the subsets when the overall size of the statistical value exceeds a predetermined maximum value.
(Appendix 6)
4. The information processing apparatus according to any one of appendices 1 to 3, further comprising a merging unit that merges the subset having the lowest access frequency with at least one subset other than the subset.
(Appendix 7)
5. The information processing apparatus according to appendix 4, wherein the merging unit merges the subset having the lowest access frequency with a subset adjacent to the subset.
(Appendix 8)
6. The information processing apparatus according to attachment 5, wherein the merging unit merges with the adjacent subset with the smaller access frequency when there are two adjacent subsets.
(Appendix 9)
Note 6 wherein the merging unit merges the subset with the lowest access frequency with a subset that is not adjacent to the subset if the access frequency of the subset adjacent to the subset is larger than a second predetermined value. The information processing device according to 1.
(Appendix 10)
7. The information processing apparatus according to appendix 6, wherein the merging unit merges the subset having the minimum access frequency with the subset having the access frequency equal to or lower than a third predetermined value.
(Appendix 11)
11. The information processing apparatus according to appendix 10, wherein the merging unit merges the subset with the smallest access frequency with the next smallest subset with the smallest access frequency.
(Appendix 12)
The information processing apparatus according to appendix 5, further comprising a setting unit that sets the maximum value.
(Appendix 13)
An access frequency management step of storing and managing the access frequency to a set of data,
A dividing step of dividing the set having the access frequency of a first predetermined value or more into at least two subsets;
A calculation step of calculating a statistical value for each of the divided subsets,
Information processing method including.
(Appendix 14)
An access frequency management step of storing and managing the access frequency to a set of data,
A dividing step of dividing the set having the access frequency of a first predetermined value or more into at least two subsets;
A calculation step of calculating a statistical value for each of the divided subsets,
An information processing program that causes a computer to execute.

  This application claims the priority on the basis of Japanese application Japanese Patent Application No. 2015-094625 for which it applied on May 7, 2015, and takes in those the indications of all here.

Claims (9)

Access frequency management means for storing and managing the access frequency to a set of data,
Dividing means for dividing the set having the access frequency equal to or higher than a first predetermined value into at least two subsets;
For each of the divided subsets, calculation means for calculating a statistical value of the data included in the subset ,
Equipped with
The dividing unit divides the subset including the target subset by dividing the subset including the target subset when the statistical value of the target subset is not calculated when the statistical value of the target subset is inquired. Generate the target subset,
The calculation means is an information processing apparatus for calculating the statistical value of the target subset .   The information processing apparatus according to claim 1, wherein the dividing unit initializes an access frequency of the divided subset. The statistics included in the subset further comprising management means for managing as a tree structure, the information processing apparatus according to claim 1 or 2. Wherein if the entire length of the statistics value exceeds a predetermined maximum value, further comprising merging means for merging at least two of the subsets, the information processing apparatus according to any one of claims 1 to 3. The information processing apparatus according to claim 4 , wherein the merging unit merges the subset having the lowest access frequency with at least one subset other than the subset. The information processing apparatus according to claim 5 , wherein the merging unit merges the subset having the minimum access frequency with a subset adjacent to the subset. 7. The information processing apparatus according to claim 6 , wherein the merging unit merges with the adjacent subset having the smaller access frequency when there are two adjacent subsets. Store and manage the frequency of access to a set of data,
Dividing the set with the access frequency of a first predetermined value or more into at least two subsets,
For each of the divided subsets, calculate the statistical value of the data included in the subset ,
When the statistic value of the target subset is inquired, if the statistic value of the target subset is not calculated, the target subset is generated by dividing the subset including the target subset. Then
An information processing method for calculating the statistical value of the target subset . An access frequency management process of storing and managing the access frequency to a set of data,
A division process for dividing the set having the access frequency of a first predetermined value or more into at least two subsets;
For each of the divided subsets, a calculation process of calculating a statistical value of the data included in the subset ,
To the computer ,
In the division processing, when the statistic value of the target subset is inquired, if the statistic value of the target subset has not been calculated, by dividing the subset including the target subset, Generate the target subset,
The calculation process is an information processing program for calculating the statistical value of the target subset .

Images