Data organization and indexing related technology

• US 8,577,902 B1
• Filed: 05/11/2010
• Issued: 11/05/2013
• Est. Priority Date: 05/12/2009
• Status: Active Grant

• Current Assignee: Microstrategy Incorporated
• Original Assignee: Microstrategy Incorporated
• Inventors: Li, Benjamin Z., Ye, Alex
• Primary Examiner(s): LIN, SHEW FEN
• Application Number:
  US12/777,631
• Time in Patent Office: 1,274 Days
• Field of Search: 707/693, 707/737, 707/752, 707/756
• US Class Current: 707/752
• CPC Class Codes: H03M 7/3077 Sorting
• CPC Class Codes: H03M 7/3079 Context modeling
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind

Abstract

Data organization and indexing, in which data that includes information for multiple attribute classes is accessed and redundancy characteristics of the accessed data within each of at least two of the multiple attribute classes are identified. Based on the identified redundancy characteristics, a relative order among the multiple attribute classes of the accessed data is determined and the accessed data is organized based on the determined relative order. The organized data is compressed using run length encoding and an index that is descriptive of the compressed data is generated. The encoded data and the generated index are stored to enable subsequent searching of the encoded data using the generated index.

Claims

1. A computer-implemented method comprising:

accessing, from an electronic data storage, data stored in the electronic data storage for multiple attribute classes, the accessed data comprising data values stored in the electronic data storage for each of at least two of the multiple attribute classes;

identifying redundancy characteristics of the accessed data within each of the at least two attribute classes by;

analyzing the accessed data values stored in the electronic data storage for each of the at least two attribute classes, and

based on the analysis of the accessed data values stored in the electronic data storage for each of the at least two attribute classes, determining a measure of redundancy within the accessed data values for each of the at least two attribute classes;

accessing a rule that indicates a preference to maintain an order of attribute classes within a dimension of attribute classes despite redundancy characteristics, the dimension of attribute classes defining a subset of attribute classes that have a parent-child relationship;

identifying a dimension of attribute classes included in the multiple attribute classes, the dimension of attribute classes being arranged in a particular order in the electronic data storage based on a parent-child relationship;

determining a relative order among the multiple attribute classes based on the determined measure of redundancy within the accessed data values for each of the at least two attribute classes, including maintaining the particular order of the attribute classes included in the dimension despite the determined measure of redundancy within the accessed data values for each of the at least two attribute classes indicating that a different order of the attribute classes included in the dimension is preferred;

organizing the accessed data based on the determined relative order among the multiple attribute classes;

compressing, using run length encoding, the organized data in the determined relative order among the multiple attribute classes;

generating an index that is descriptive of the compressed data; and

storing, in electronic storage, the encoded data and the generated index to enable subsequent searching of the encoded data using the generated index,

wherein determining the measure of redundancy within the accessed data values for each of the at least two attribute classes comprises;

determining a number of distinct data values within an attribute class;

determining a parameter for a distinct data value within the attribute class, the parameter reflecting contribution of the distinct data value to the entirety of data values within the attribute class; and

determining a redundancy measure for the attribute class based on the number of distinct data values within the attribute class and the determined parameter; and

wherein determining the relative order among the multiple attribute classes based on the determined measure of redundancy within the accessed data values for each of the at least two attribute classes comprises determining the relative order among the multiple attribute classes based on the determined redundancy measure for the attribute class that is based on the number of distinct data values within the attribute class and the determined parameter.

2. The method of claim 1 wherein determining the relative order among the multiple attribute classes comprises:

determining that a first attribute class has a lower number of distinct values than a second attribute class; and

ordering the first attribute class prior to the second attribute class in the determined relative order.

3. The method of claim 1 wherein determining the relative order among the multiple attribute classes comprises:

identifying, from among the multiple attribute classes, an attribute class having a lowest number of distinct values; and

ordering the identified attribute class first in the determined relative order.

4. The method of claim 1 wherein:

determining the measure of redundancy within the accessed data values for each of the at least two attribute classes comprises determining a percentage, within each of the at least two attribute classes, of the accessed data that has a redundant value for the corresponding attribute class; and

determining the relative order among the multiple attribute classes based on the determined measure of redundancy within the accessed data values for each of the at least two attribute classes comprises determining the relative order among the multiple attribute classes based on the determined percentages.

5. The method of claim 1 wherein:

the number of distinct data values within the attribute class is a first number of distinct data values within a first attribute class;

the parameter for the distinct data value comprises a first parameter for a first distinct data value,

the redundancy measure for the attribute class is a first redundancy measure for the first attribute class,

determining the measure of redundancy within the accessed data values for each of the at least two attribute classes further comprises;

determining a second number of distinct data values within a second attribute class, the second number of distinct data values within the second attribute class being lower than the first number of distinct data values within the first attribute class;

determining a second parameter for a second distinct data value within the second attribute class, the second parameter reflecting contribution of the second distinct data value to the entirety of data values within the second attribute class; and

determining a second redundancy measure for the second attribute class based on the second number of distinct data values within the second attribute class and the determined second parameter, the second redundancy measure reflecting a lower level of redundancy for the second attribute class than the first redundancy measure reflects for the first attribute class despite the second number of distinct data values within the second attribute class being lower than the first number of distinct data values within the first attribute class; and

determining the relative order among the multiple attribute classes based on the determined redundancy measure for the attribute class that is based on the number of distinct data values within the attribute class and the determined parameter comprises determining the relative order among the multiple attribute classes based on the first redundancy measure for the first attribute class and the second redundancy measure for the second attribute class, the first attribute class being ordered prior to the second attribute class in the determined relative order based on the second redundancy measure reflecting a lower level of redundancy for the second attribute class than the first redundancy measure reflects for the first attribute class.

6. The method of claim 1 wherein determining the parameter for the distinct data value comprises determining a rate of occurrence of the distinct data value within the entirety of data values within the attribute class.

7. The method of claim 1, further comprising:

accessing a rule that indicates attribute classes that are searched at a higher frequency than other attribute classes are prioritized in comparison to the other attribute classes in determining an order of attribute classes; and

identifying a first attribute class that is included in the multiple attribute classes and that is searched at a higher frequency than a second attribute class that is included in the multiple attribute classes;

wherein determining the relative order among the multiple attribute classes based on the determined measure of redundancy within the accessed data values for each of the at least two attribute classes comprises, based on the identification that the first attribute class is searched at a higher frequency than the second attribute class, determining to order the first attribute class prior to the second attribute class despite the determined measure of redundancy within the accessed data values for each of the at least two attribute classes indicating that ordering the second attribute class prior to the first attribute class is preferred.

8. The method of claim 1 wherein:

the multiple attribute classes are organized in the electronic data storage in a first order; and

organizing the accessed data based on the determined relative order among the multiple attribute classes comprises reorganizing the multiple attribute classes in a second order that is different than the first order in which the multiple attribute classes are organized in the electronic data storage.

9. The method of claim 1 wherein:

the multiple attribute classes include at least a first dimension of attribute classes and a second dimension of attribute classes, each of the first and second dimensions defining an exclusive subset of the multiple attribute classes that are related;

the multiple attribute classes are organized in the electronic data storage in a first order that is based on the first and second dimensions such that the exclusive subset of attribute classes included in the first dimension are ordered consecutively and the exclusive subset of attribute classes included in the second dimension are ordered consecutively; and

organizing the accessed data based on the determined relative order among the multiple attribute classes comprises reorganizing the multiple attribute classes in a second order in which at least one attribute class included in the first dimension is ordered among the attribute classes included in the second dimension such that the exclusive subset of attribute classes included in the first dimension are no longer ordered consecutively and the exclusive subset of attribute classes included in the second dimension are no longer ordered consecutively.

10. The method of claim 1 wherein:

the multiple attribute classes include a dimension of attribute classes that defines a subset of the multiple attribute classes that have a parent-child relationship;

the multiple attribute classes are organized in the electronic data storage in a first order that is based on the dimension such that parent attribute classes are ordered prior to child attribute classes in the electronic data storage; and

organizing the accessed data based on the determined relative order among the multiple attribute classes comprises reorganizing the subset of the multiple attribute classes included in the dimension in a second order in which at least one child attribute class is ordered prior to at least one of its parent attribute classes as defined by the parent-child relationship.

11. The method of claim 1 wherein generating the index that is descriptive of the compressed data comprises:

identifying blocks within the compressed data that have common values;

identifying storage locations of the identified blocks within the compressed data; and

associating, within the index, the identified blocks within the compressed data with the corresponding common values and identified storage locations to enable identification of storage locations of a particular block using the index.

12. The method of claim 11 further comprising handling a request to access a particular block within the compressed data by:

accessing, from the electronic storage, the generated index;

identifying the particular block within the generated index;

identifying, using the index, particular storage locations corresponding to the particular block; and

accessing, from the electronic storage, data corresponding to the particular storage locations identified using the index.

13. The method of claim 1 further comprising:

receiving a report generation query that defines a subset of the multiple attribute classes of interest;

accessing, from the electronic storage, the generated index in response to receiving the report generation query;

identifying the subset of the multiple attribute classes of interest defined by the report generation query;

identifying, using the generated index, portions of the compressed data that include a distinct combination of values for the subset of the multiple attribute classes of interest;

accessing, from the electronic storage, metrics for each of the identified portions of the compressed data;

computing a report parameter for each of the identified portions of the compressed data based on the accessed metrics;

generating a report based on the computed report parameters; and

displaying, on a display device, the generated report responsive to the report generation query.

14. An electronic system comprising:

at least one electronic data storage device; and

at least one processor configured to perform operations comprising;

accessing, from an electronic data storage, data stored in the electronic data storage for multiple attribute classes, the accessed data comprising data values stored in the electronic data storage for each of at least two of the multiple attribute classes;

identifying redundancy characteristics of the accessed data within each of the at least two attribute classes by;

analyzing the accessed data values stored in the electronic data storage for each of the at least two attribute classes, and

based on the analysis of the accessed data values stored in the electronic data storage for each of the at least two attribute classes, determining a measure of redundancy within the accessed data values for each of the at least two attribute classes;

accessing a rule that indicates a preference to maintain an order of attribute classes within a dimension of attribute classes despite redundancy characteristics, the dimension of attribute classes defining a subset of attribute classes that have a parent-child relationship;

identifying a dimension of attribute classes included in the multiple attribute classes, the dimension of attribute classes being arranged in a particular order in the electronic data storage based on a parent-child relationship;

determining a relative order among the multiple attribute classes based on the determined measure of redundancy within the accessed data values for each of the at least two attribute classes, including maintaining the particular order of the attribute classes included in the dimension despite the determined measure of redundancy within the accessed data values for each of the at least two attribute classes indicating that a different order of the attribute classes included in the dimension is preferred;

organizing the accessed data based on the determined relative order among the multiple attribute classes;

compressing, using run length encoding, the organized data in the determined relative order among the multiple attribute classes;

generating an index that is descriptive of the compressed data; and

storing, in the at least one electronic data storage device, the compressed data and the generated index to enable subsequent searching of the compressed data using the generated index,

wherein determining the measure of redundancy within the accessed data values for each of the at least two attribute classes comprises;

determining a number of distinct data values within an attribute class;

determining a parameter for a distinct data value within the attribute class, the parameter reflecting contribution of the distinct data value to the entirety of data values within the attribute class; and

determining a redundancy measure for the attribute class based on the number of distinct data values within the attribute class and the determined parameter; and

wherein determining the relative order among the multiple attribute classes based on the determined measure of redundancy within the accessed data values for each of the at least two attribute classes comprises determining the relative order among the multiple attribute classes based on the determined redundancy measure for the attribute class that is based on the number of distinct data values within the attribute class and the determined parameter.

15. A computer-implemented method comprising:

accessing, from an electronic data storage, data stored in the electronic data storage for multiple attribute classes, the accessed data comprising data values stored in the electronic data storage for each of at least two of the multiple attribute classes;

identifying redundancy characteristics of the accessed data within each of the at least two attribute classes by;

analyzing the accessed data values stored in the electronic data storage for each of the at least two attribute classes, and

based on the analysis of the accessed data values stored in the electronic data storage for each of the at least two attribute classes, determining a measure of redundancy within the accessed data values for each of the at least two attribute classes;

accessing a rule that indicates a preference to maintain an order of attribute classes within a dimension of attribute classes despite redundancy characteristics, the dimension of attribute classes defining a subset of attribute classes that have a parent-child relationship;

identifying a dimension of attribute classes included in the multiple attribute classes, the dimension of attribute classes being arranged in a particular order in the electronic data storage based on a parent-child relationship;

determining a relative order among the multiple attribute classes based on the determined measure of redundancy within the accessed data values for each of the at least two attribute classes, including maintaining the particular order of the attribute classes included in the dimension despite the determined measure of redundancy within the accessed data values for each of the at least two attribute classes indicating that a different order of the attribute classes included in the dimension is preferred;

ordering the multiple attribute classes within the accessed data based on the determined relative order among the multiple attribute classes;

encoding the accessed data within the ordered multiple attribute classes, with the encoding reflecting redundancies and uniqueness within the accessed data and accounting for the determined relative order among the multiple attribute classes; and

storing, in electronic storage, the encoded data to enable subsequent searching of the encoded data,

wherein determining the measure of redundancy within the accessed data values for each of the at least two attribute classes comprises;

determining a number of distinct data values within an attribute class;

determining a parameter for a distinct data value within the attribute class, the parameter reflecting contribution of the distinct data value to the entirety of data values within the attribute class; and

determining a redundancy measure for the attribute class based on the number of distinct data values within the attribute class and the determined parameter; and

wherein determining the relative order among the multiple attribute classes based on the determined measure of redundancy within the accessed data values for each of the at least two attribute classes comprises determining the relative order among the multiple attribute classes based on the determined redundancy measure for the attribute class that is based on the number of distinct data values within the attribute class and the determined parameter.

16. A computer-implemented method comprising:

accessing, from an electronic data storage, data that includes information for multiple attribute classes;

identifying redundancy characteristics of the accessed data within each of at least two of the multiple attribute classes;

identifying a search frequency for each of the at least two attribute classes;

determining a relative order among the multiple attribute classes based on;

the identified redundancy characteristics of the accessed data within each of at least two attribute classes, and

the identified search frequency for each of the at least two attribute classes;

organizing the accessed data based on the determined relative order among the multiple attribute classes;

compressing, using run length encoding, the organized data in the determined relative order among the multiple attribute classes;

generating an index that is descriptive of the compressed data; and

storing, in electronic storage, the encoded data and the generated index to enable subsequent searching of the encoded data using the generated index,

wherein identifying redundancy characteristics of the accessed data within each of at least two of the multiple attribute classes comprises;

determining a number of distinct data values within an attribute class;

determining a parameter for a distinct data value within the attribute class, the parameter reflecting contribution of the distinct data value to the entirety of data values within the attribute class; and

determining a redundancy measure for the attribute class based on the number of distinct data values within the attribute class and the determined parameter; and

wherein determining the relative order among the multiple attribute classes comprises determining the relative order among the multiple attribute classes based on the determined redundancy measure for the attribute class that is based on the number of distinct data values within the attribute class and the determined parameter, and

wherein determining the relative order among the multiple attribute classes further comprises;

accessing a rule that indicates attribute classes that are searched at a higher frequency than other attribute classes are prioritized in comparison to the other attribute classes in determining an order of attribute classes;

identifying a first attribute class that is included in the multiple attribute classes and that is searched at a higher frequency than a second attribute class that is included in the multiple attribute classes; and

based on the identification that the first attribute class is searched at a higher frequency than the second attribute class, determining to order the first attribute class prior to the second attribute class despite the identified redundancy characteristics indicating that ordering the second attribute class prior to the first attribute class is preferred.

17. The method of claim 16, wherein determining the relative order among the multiple attribute classes comprises overriding the identified redundancy characteristics based on the identified search frequency.