Systems and methods for optimizing data analysis

• US 10,162,855 B2
• Filed: 06/09/2015
• Issued: 12/25/2018
• Est. Priority Date: 06/09/2014
• Status: Active Grant

• Current Assignee: Simba Technologies, Inc.
• Original Assignee: Dundas Data Visualization, Inc. (Insightsoftware UK Trading Ltd.)
• Inventors: Andros, Oleg
• Primary Examiner(s): Waldron, Scott A.
• Application Number:
  US14/734,317
• Publication Number:
  US 20150356137A1
• Time in Patent Office: 1,295 Days
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Methods and systems are provided for optimizing data analysis. An example method for optimizing a computer for performing queries of a database can include determining a number of distinct members in a lowest hierarchy level of each hierarchy dimension and determining a unique hierarchy identifier for such distinct member; determining the hierarchy dimension with the fewest number of distinct members in its lowest level; ranking the hierarchy dimensions by the number of distinct members in the lowest level; generating a first hypergraph tree for the hierarchy dimension with the fewest number of distinct members in its lowest level; and generating an additional hypergraph tree for a hierarchy dimension having more than the fewest number of distinct members in its lowest level. Each hypergraph tree includes multiple nodes and each node corresponds to one of the unique hierarchy identifiers. The additional hypergraph tree includes fewer tiers than the first hypergraph tree.

Claims

1. A method of optimizing a computer for performing queries of a database, the database storing a plurality of metric records in a computer memory, each metric record comprising at least one measure data value and a plurality of hierarchy data values, wherein each hierarchy data value is in a hierarchy dimension, wherein each hierarchy dimension comprises at least one hierarchy level, said at least one hierarchy level including a lowest hierarchy level, wherein each hierarchy level comprises at least one distinct hierarchy member;

and wherein each hierarchy data value matches a hierarchy member in the lowest level of the corresponding hierarchy dimension, the method comprising;

a) determining the number of distinct members of the lowest hierarchy level of each hierarchy dimension and determining a unique hierarchy identifier (ID) for such distinct member;

b) determining the hierarchy dimension having the fewest number of distinct members in its lowest level;

c) ranking the hierarchy dimensions by number of distinct members in the respective lowest level;

d) generating a first hypergraph tree for the hierarchy dimension having the fewest number of distinct members in its lowest level, wherein the first hypergraph tree comprises a tier for each hierarchy dimension;

e) generating one or more additional hypergraph trees, each additional hypergraph tree for a hierarchy dimension having more than the fewest number of distinct members in its lowest level, wherein each additional hypergraph tree comprises at least one tier for a hierarchy dimension and each additional hypergraph tree has fewer than the number of tiers in the first hypergraph tree;

wherein each hypergraph tree comprises a plurality of nodes, and wherein each node corresponds to one of the unique hierarchy IDs, and wherein each node comprises at least one edge weighting comprising a determined measure data value,

wherein all of the nodes in a tier correspond to the same hierarchy dimension, and

wherein each generated hyperqraph tree uniquely corresponds to a different hierarchy dimension;

f) receiving, via a dashboard interface displayed on a networked computing device, a query comprising one or more search parameters;

g) identifying a hierarchy dimension for each of the one or more search parameters;

h) selecting, based on the one or more identified hierarchy dimensions, one of the first hyperqraph tree and the one or more additional hypergraph trees;

i) searching the selected hyperqraph tree to perform the query; and

j) returning a result of the query to the networked computing device for presentation in the dashboard interface.

2. The method of claim 1, wherein the determined measure data value for a node is determined from the measure data value for each metric record comprising a measure data value corresponding to that node'"'"'s corresponding unique hierarchy ID.

3. The method of claim 1, wherein at least one hierarchy dimension comprises a plurality of hierarchy levels.

4. The method of claim 1, wherein the determined unique hierarchy IDs are sequentially ordered.

5. A system for optimizing performance of queries of a database by a computer, the system comprising:

a computer memory storing, at least, the database for storing a plurality of metric records, each metric record comprising at least one measure data value and a plurality of hierarchy data values, wherein each hierarchy data value is in a hierarchy dimension, wherein each hierarchy dimension comprises at least one hierarchy level, said at least one hierarchy level including a lowest hierarchy level, wherein each hierarchy level comprises at least one distinct hierarchy member; and

wherein each hierarchy data value matches a hierarchy member in the lowest level of the corresponding hierarchy dimension; and

at least one processor configured to;

a) determine the number of distinct members of the lowest hierarchy level of each hierarchy dimension and determine a unique hierarchy ID for such distinct member;

b) determine the hierarchy dimension having the fewest number of distinct members in its lowest level;

c) rank the hierarchy dimensions by number of distinct members in the respective lowest level;

d) generate a first hypergraph tree for the hierarchy dimension having the fewest number of distinct members in its lowest level, wherein the first hypergraph tree comprises a tier for each hierarchy dimension; and

e) generate one or more additional hypergraph trees, each additional hypergraph tree for a hierarchy dimension having more than the fewest number of distinct members in its lowest level, wherein each additional hypergraph tree comprises at least one tier for a hierarchy dimension and each additional hypergraph tree has fewer than the number of tiers in the first hypergraph tree;

wherein each hypergraph tree comprises a plurality of nodes, and wherein each node corresponds to one of the unique hierarchy IDs, and wherein each node comprises at least one edge weighting comprising a determined measure data value,

wherein all of the nodes in a tier correspond to the same hierarchy dimension, and

wherein each generated hypergraph tree uniquely corresponds to a different hierarchy dimension;

f) receive, via a dashboard interface displayed on a networked computing device, a query comprising one or more search parameters;

g) identify a hierarchy dimension for each of the one or more search parameters;

h) select, based on the one or more identified hierarchy dimensions, one of the first hypergraph tree and the one or more additional hypergraph trees;

i) search the selected hypergraph tree to perform the query; and

j) return a result of the query to the networked computing device for presentation in the dashboard interface.

6. The system of claim 5, wherein the determined measure data value for a node is determined from the measure data value for each metric record comprising a measure data value corresponding to that node'"'"'s corresponding unique hierarchy ID.

7. The system of claim 5, wherein at least one hierarchy dimension comprises a plurality of hierarchy levels.

8. The system of claim 5, wherein the determined unique hierarchy IDs are sequentially ordered.

9. A method for optimizing performance of at least one query of a database by a computer, the computer having a processor and the processor being in electronic communication with a memory storing, at least, the database, the method comprising:

storing in the memory a set of hierarchy data tables generated based on a plurality of metric records stored in the database, each metric record including a set of data values and each data value being associated with a hierarchy dimension, each hierarchy data table being associated with a different hierarchy dimension and each hierarchy data table including a plurality of distinct data members, each distinct data member being assigned a unique hierarchy identifier;

operating the processor to assign each hierarchy dimension a dimension rank, wherein operating the processor to assign the dimension rank comprises;

for each hierarchy data table, determining a number of distinct data members in the respective hierarchy data table;

assigning each hierarchy dimension with the dimension rank sequentially according to the determined number of distinct data members for the set of hierarchy data tables, wherein the processor is configured to assign a first dimension rank to the hierarchy dimension associated with the hierarchy data table determined to have a fewest number of distinct data members and to assign a last dimension rank to the hierarchy dimension associated with the hierarchy data table determined to have a greatest number of distinct data members; and

based on the plurality of metric records, generating at least one hypergraph tree for at least one hierarchy dimension according to the assigned dimension ranks; and

in response to a query received via a dashboard interface of a networked computing device, operating the processor to;

select one of the at least one hypergraph tree, search the selected hypergraph tree to perform the query, and return a result of the query to the networked computing device for presentation in the dashboard interface.

10. The method of claim 9, wherein generating the at least one hypergraph tree for the at least one hierarchy dimension according to the assigned dimension ranks comprises:

generating a first hypergraph tree based on one or more data values in the plurality of metric records associated with a first hierarchy dimension, the first hierarchy dimension being the hierarchy dimension assigned the first dimension rank, wherein generating the first hypergraph tree comprises generating an initial node for each distinct data value in the first hierarchy dimension in the plurality of metric records, a data value being a distinct data value when the data value is different from all other data values in the same hierarchy dimension; and

generating a subsequent hypergraph tree based on one or more data values in the plurality of metric records associated with a subsequent hierarchy dimension of one or more subsequent hierarchy dimensions, the subsequent hierarchy dimension being different from the first hierarchy dimension and the subsequent hierarchy dimension corresponding to a dimension rank subsequent to the first dimension rank.

11. The method of claim 10, wherein generating the initial node for each distinct data value in the first hierarchy dimension in the plurality of metric records comprises, for each initial node:

identifying one or more metric records having a data value in the first hierarchy dimension corresponding to the distinct data value;

retrieving one or more measure data values corresponding to the identified one or more metric records;

determining a measure aggregation for the retrieved one or more measure data values; and

associating the initial node with, at least, the distinct data value and the determined measure aggregation.

12. The method of claim 11, wherein the determined measure aggregation comprises one of:

a sum;

an average;

a minimum;

a maximum; and

a distinct count.

13. The method of claim 12, wherein the distinct data value comprises a corresponding hierarchy identifier determined from the hierarchy data table associated with the first hierarchy dimension.

14. The method of claim 12 further comprises:

linking one or more subsequent nodes to the initial node according to the dimension ranks, each subsequent node corresponding to one of the one or more subsequent hierarchy dimensions.

15. The method of claim 14, wherein:

the one or more subsequent nodes comprises a first subsequent node corresponding to a second hierarchy dimension, the second hierarchy dimension being the hierarchy dimension assigned the second dimension rank; and

linking the one or more subsequent nodes to the initial node comprises, for the first subsequent node;

identifying a subset of metric records from the identified one or more metric records, the subset of metric records having a common data value in the second hierarchy dimension;

retrieving one or more first subsequent measure data values corresponding to the identified subset of metric records;

determining a first subsequent measure aggregation for the retrieved one or more first subsequent measure data values; and

associating the first subsequent node with the first subsequent measure aggregation.

16. The method of claim 9, wherein operating the processor to select one of the at least one hypergraph tree comprises identifying a hierarchy dimension for each of one or more search parameters included in the query, and selecting the hypergraph tree to be searched based on the one or more identified hierarchy dimensions.

17. A system for optimizing performance of at least one query of a database by a computer, the system comprises:

a memory storing, at least;

the database storing a plurality of metric records, each metric record including a set of data values and each data value being associated with a hierarchy dimension; and

a set of hierarchy data tables generated based on the plurality of metric records, each hierarchy data table being associated with a different hierarchy dimension and each hierarchy data table including a plurality of distinct data members, each distinct data member being assigned a unique hierarchy identifier; and

a processor in electronic communication with the memory, the processor being configured to;

assign each hierarchy dimension a dimension rank, wherein operating the processor to assign the dimension rank comprises;

for each hierarchy data table, determining a number of distinct data members in the respective hierarchy data table;

assigning each hierarchy dimension with the dimension rank sequentially according to the determined number of distinct data members for the set of hierarchy data tables, wherein the processor is configured to assign a first dimension rank to the hierarchy dimension associated with the hierarchy data table determined to have a fewest number of distinct data members and to assign a last dimension rank to the hierarchy dimension associated with the hierarchy data table determined to have a greatest number of distinct data members; and

based on the plurality of metric records, generate at least one hypergraph tree for at least one hierarchy dimension according to the assigned dimension ranks; and

receive a query via a dashboard interface of a networked computing device, select one of the at least one hypergraph tree, search the selected hypergraph tree to perform the query, and return a result of the query to the networked computing device for presentation in the dashboard interface.

18. The system of claim 17, wherein the processor is further configured to:

generate the at least one first hypergraph tree based on one or more data values in the plurality of metric records associated with a first hierarchy dimension, the first hierarchy dimension being the hierarchy dimension assigned the first dimension rank, wherein the processor is further configured to generate an initial node for each distinct data value in the first hierarchy dimension in the plurality of metric records, a data value being a distinct data value when the data value is different from all other data values in the same hierarchy dimension; and

generate a subsequent hypergraph tree based on one or more data values in the plurality of metric records associated with a subsequent hierarchy dimension of one or more subsequent hierarchy dimensions, the subsequent hierarchy dimension being different from the first hierarchy dimension and the subsequent hierarchy dimension corresponding to a dimension rank subsequent to the first dimension rank.

19. The system of claim 18, wherein, for each initial node, the processor is configured to:

identify one or more metric records having a data value in the first hierarchy dimension corresponding to the distinct data value;

retrieve one or more measure data values corresponding to the identified one or more metric records;

determine a measure aggregation for the retrieved one or more measure data values; and

associate the initial node with, at least, the distinct data value and the determined measure aggregation.

20. The system of claim 19, wherein the measure aggregation comprises one of:

a sum;

an average;

a minimum;

a maximum; and

a distinct count.

21. The system of claim 19, wherein the distinct data value comprises a corresponding hierarchy identifier determined from the hierarchy data table associated with the first hierarchy dimension.

22. The system of claim 19, wherein the processor is configured to:

link one or more subsequent nodes to the initial node according to the dimension ranks, each subsequent node corresponding to one of the one or more subsequent hierarchy dimensions.

23. The system of claim 22, wherein:

the one or more subsequent nodes comprises a first subsequent node corresponding to a second hierarchy dimension, the second hierarchy dimension being the hierarchy dimension assigned the second dimension rank; and

for the first subsequent node, the processor is configured to;

identify a subset of metric records from the identified one or more metric records, the subset of metric records having a common data value in the second hierarchy dimension;

retrieve one or more first subsequent measure data values corresponding to the identified subset of metric records;

determine a first subsequent measure aggregation for the retrieved one or more first subsequent measure data values; and

associate the first subsequent node with the first subsequent measure aggregation.

24. The system of claim 17, wherein the processor is configured to select one of the at least one hypergraph tree by identifying a hierarchy dimension for each of one or more search parameters included in the query, and to select the hypergraph tree to be searched based on the one or more identified hierarchy dimensions.