Frequency partitioning: entropy compression with fixed size fields
View Patent ↗A frequency partitioning technique is introduced that amortizes the work of computing codeword lengths within a tuplecode by grouping together tuples that have the same pattern of codeword lengths. Specifically, the technique entropy codes and partitions column values in each column into disjoint sets called column partitions, assigns a codeword length to each of the column partitions, identifies cells (a combination of codeword lengths), and collectively storing tuples associated with each of the cells.
1. A computer-based partitioning method comprising the steps of:
a. identifying a plurality of attributes associated with a database and identifying a set of one or more attribute values for each of said identified attributes;
b. partitioning the set of attribute values for each identified attribute into one or more attribute partitions;
c. identifying a plurality of cells, each cell representing a combination of disparate attribute partitions, said disparate attribute partitions belonging to different attributes;
d. collectively storing database records associated with each of said plurality of cells, wherein said computer-based partitioning method stores database records of a given cell together, and wherein said attributes are partitioned according to a frequency of occurrence of attribute values, where attributes values with similar frequencies of occurrence are assigned to the same attribute partition.
2. The computer-based partitioning method of claim 1 , wherein said method comprises the additional step of representing attribute values in each cell and for a given attribute using fixed length representation.
3. The computer-based partitioning method of claim 2 , wherein said fixed length representation is done by assigning a code to each attribute value such that ordering of codes is either same as or inverse of a numerical or alphabetical ordering of attribute values.
4. The computer-based partitioning method of claim 1 , wherein said partitioning of column values is optimized based on the following objective function:
∑
i
P
(
S
i
)
(
⌈
1
g
S
i
⌉
-
1
g
P
(
S
i
)
)
wherein S i is a set of attribute values in the i th partition and P(S i ) is the frequency of occurrence of said set S i .
5. The computer-based partitioning method of claim 1 , wherein said method additionally places a constraint on the total number of cells.
6. The computer-based partitioning method of claim 1 , wherein said method implements dynamic programming to determine optimal per column partitioning and further implements a greedy method to determine optimal partitions for conducting said partitioning.
7. The computer-based partitioning method of claim 1 , wherein said method results in similar sized partitions by partitioning only the larger partitions.
8. The computer-based partitioning method of claim 1 , wherein said method results in similar sized partitions by ordering the column partitions and applying partitioning only to partitions that are larger than a pre-determined size.
9. The computer-based partitioning method of claim 1 , wherein each partition represents a disjoint set of attribute values.
10. A computer-based partitioning system implemented via an extract-transform-load module stored in computer storage medium, said computer storage medium comprising computer readable program code, which when executed by a computer, provides:
a. an analysis component implementing an analysis phase, said analysis component:
i. accessing a database, identifying a plurality of attributes associated with said database, and identifying a set of one or more attribute values for each of said identified attributes, and
ii. partitioning the set of values for each identified attribute into one or more attribute partitions;
b. a compression component implementing a compression phase, said compression component:
i. identifying a plurality of cells, each cell representing a combination of disparate attribute partitions, said disparate attribute partitions belonging to different attributes;
ii. representing attribute values in each cell and for a given attribute using fixed length representation;
iii. collectively storing database records associated with each of said plurality of cells,
wherein said computer-based partitioning system stores records of a given cell together, and wherein said attributes are partitioned according to a frequency of occurrence of attribute values, where attributes values with similar frequencies of occurrence are assigned to the same attribute partition.
11. The computer-based partitioning system of claim 10 , wherein said fixed length representation is done by assigning a code to each attribute value such that ordering of codes is either same as or inverse of a numerical or alphabetical ordering of attribute values.
12. The computer-based partitioning system of claim 10 , wherein said partitioning of column values is optimized based on the following objective function:
∑
i
P
(
S
i
)
(
⌈
1
g
S
i
⌉
-
1
g
P
(
S
i
)
)
wherein S i is a set of attribute values in the i th partition and P(S i ) is the frequency of occurrence of said set S i .
13. The computer-based partitioning method of claim 10 , wherein said system additionally places a constraint on the total number of cells.
14. The computer-based partitioning system of claim 10 , wherein said system implements dynamic programming to determine optimal per column partitioning and further implements a greedy method to determine optimal partitions for conducting said partitioning.
15. The computer-based partitioning system of claim 10 , wherein similar sized partitions are produced by partitioning only the larger partitions.
16. The computer-based partitioning system of claim 10 , wherein said similar sized partitions are produced by ordering the column partitions and applying partitioning only to partitions that are larger than a pre-determined size.
17. The computer-based partitioning system of claim 10 , wherein each partition represents a disjoint set of attribute values.
18. An article of manufacture comprising a computer user storage medium having computer readable program code embodied therein which implements a computer-based frequency partitioning method, said medium comprising:
a. computer readable program code identifying a plurality of attributes associated with a database and identifying a set of one or more attribute values for each of said identified attributes;
b. computer readable program code partitioning the set of attribute values for each identified attribute into one or more attribute partitions;
c. computer readable program code identifying a plurality of cells, each cell representing a combination of disparate attribute partitions, said disparate attribute partitions belonging to different attributes;
d. computer readable program code providing instructions to collectively store database records associated with each of said plurality of cells wherein said computer-based partitioning method stores database records of a given cell together, and wherein said attributes are partitioned according to a frequency of occurrence of attribute values, where attributes values with similar frequencies of occurrence are assigned to the same attribute partition.