# US 11,445,240 B2 · Query processing in data analysis

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,445,240 B2
- Document ID: US11445240B2
- Status: Granted
- Kind: B2
- Application number: 17/109,701
- Filed: 2020-12-02
- Published: 2021-03-25
- Granted: 2022-09-13
- Earliest claimed: 2016-10-26
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Qingwei Lin; Jian-Guang Lou
- Web page: https://patentgrep.com/patent/US11445240B2

## CPC

- G06F 16/283: {Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP}
- H04N 21/4363: Adapting the video stream to a specific local network, e.g. a Bluetooth® network
- G06F 16/24535: {of sub-queries or views}
- H04N 21/23406: {involving management of server-side video buffer}
- H04N 21/4302: {Content synchronisation processes, e.g. decoder synchronisation}
- G06F 16/24549: {Run-time optimisation}
- G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

In implementations of the subject matter described herein, a solution for query processing is provided. In this solution, data subsets are pre-stored for example in a fast access storage device for data analysis, each including data entries corresponding to one or more dimensions. If two or more data subsets are needed to cover target dimensions corresponding to query items in a received query, instead of turning to analyze a source data set that is not stored, the query is decomposed into subqueries. By means of the decomposing, the target dimension(s) corresponding to the query item(s) in each subquery can be covered by a single data subset. The data subset is analyzed for each subquery and a query result for the query is determined based on analysis results of the subqueries. In such way, the query result for the query can obtained in a fast manner from the available data subsets.

## Claims

### Claim 1

A computer-implemented method, comprising:
receiving a query including a plurality of query items associated with a plurality of target dimensions of a data entry;
determining at least two of a plurality of data subsets are needed to cover the plurality of target dimensions, at least one of the plurality of data subsets including data entries corresponding to at least one of the plurality of target dimensions;
in response to determining that the at least two of the plurality of data subsets are needed to cover the plurality of target dimensions, decomposing the query into a plurality of subqueries, each of the plurality of subqueries having at least one of the plurality of query items, wherein decomposing the query into the plurality of sub queries comprises:
determining correlations between respective pairs of query items among the plurality of query items, wherein determining the correlations comprises determining mutual information between the respective pairs of query items based on probabilities of presence of the plurality of query items in corresponding target dimensions; and
determining associations of the plurality of target dimensions based on the plurality of target dimensions corresponding to the respective data subsets and the correlations; and
determining a query result for the query by analyzing a data entry in the plurality of data subsets that is corresponding to a target dimension associated with the at least one query item in each of the plurality of subqueries.

### Claim 2 (depends on 1)

The method of claim 1, wherein decomposing the query into the plurality of sub queries further comprises:
decomposing, based on the determined associations of the plurality of target dimensions, the query into the plurality of subqueries such that target dimensions corresponding to a subquery having one or more of the plurality of query items are determined as having an association.

### Claim 3 (depends on 1)

The method of claim 1, wherein determining the associations of the plurality of target dimensions comprises:
determining two of the plurality of target dimensions as having an association based on at least one of:
a correlation between a pair of query items associated with the two target dimensions being greater than a threshold correlation;
the two target dimensions being covered by a first data subset of the plurality of data subsets; and
the two target dimensions and a further target dimension having an association with one of the two target dimensions being covered by a second data subset of the plurality of data subsets.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
creating a plurality of candidate data subsets from a source data set based on a predetermined coverage rate for combinations of source dimensions of the source data set, each of the plurality of candidate data subsets covering at least two of the source dimensions;
combining at least two of the plurality of candidate data subsets into a combined candidate data subset such that the combined candidate data subset covers source dimensions of the at least two candidate data subsets;
identifying, from the plurality of candidate data subsets, a candidate data subset with source dimensions covered by the combined candidate data subset; and
determining the plurality of data subsets based on remaining candidate data subsets other than the identified candidate data subset.

### Claim 5 (depends on 4)

The method of claim 4, further comprising selecting the at least two candidate data subsets by:
determining a data size of each of the plurality of candidate data subsets; and
selecting, from the plurality of candidate data subsets, the at least two candidate data subsets with respective data sizes smaller than a threshold data size.

### Claim 6 (depends on 5)

The method of claim 5, wherein determining the data size of each of the plurality of candidate data subsets comprises:
sampling a plurality of data entries from data entries included in a given candidate data subset;
determining a first number of different data entries and a second number of data entries having a frequency of occurrence lower than a threshold frequency among the sampled plurality of data entries;
determining, based on the first number and the second number, a number of different data entries included in the given candidate data subset; and
determining, based on the number of the different data entries, the data size of the given candidate data subset.

### Claim 7 (depends on 4)

The method of claim 4, wherein determining the plurality of data subsets based on the remaining candidate data subsets comprises:
determining whether a total data size of the remaining candidate data subsets exceeds a storage space available for storing the plurality of data subsets; and
in response to the total data size being equal to or smaller than the storage space, determining the remaining candidate data subsets as the plurality of data subsets.

### Claim 8

A device, comprising:
a processing unit;
a memory coupled to the processing unit and storing instructions thereon, the instructions, when executed by the processing unit, cause the processing unit to:
receive a query including a plurality of query items associated with a plurality of target dimensions of a data entry;
determine whether at least two of a plurality of data subsets are needed to cover the plurality of target dimensions, at least one of the plurality of data subsets including data entries corresponding to at least one of the plurality of target dimensions;
in response to determining that the at least two of the plurality of data subsets are needed to cover the plurality of target dimensions, decompose the query into a plurality of subqueries, each of the plurality of subqueries having at least one of the plurality of query items, wherein decomposing the query into the plurality of subqueries comprises:
determine correlations between respective pairs of query items among the plurality of query items, wherein determining the correlations comprises determining mutual information between the respective pairs of query items based on probabilities of presence of the plurality of query items in corresponding target dimensions; and
determine associations of the plurality of target dimensions based on the plurality of target dimensions corresponding to the respective data subsets and the correlations; and
determine a query result for the query by analyzing a data entry in the plurality of data subsets that is corresponding to a target dimension associated with the at least one query item in each of the plurality of subqueries.

### Claim 9 (depends on 8)

The device of claim 8, wherein, to decompose the query into the plurality of subqueries, the processing unit is further caused to:
decompose, based on the determined associations of the plurality of target dimensions, the query into the plurality of subqueries such that target dimensions corresponding to a subquery having one or more of the plurality of query items are determined as having an association.

### Claim 10 (depends on 8)

The device of claim 8, wherein, to determine the association of the plurality of target dimensions, the processing unit is caused to:
determining two of the plurality of target dimensions as having an association based on at least one of:
a correlation between a pair of query items associated with the two target dimensions being greater than threshold correlation;
the two target dimensions being covered by a first data subset of the plurality of data subsets; and
the two target dimensions and a further target dimension having an association with one of the two target dimensions being covered by a second data subset of the plurality of data subsets.

### Claim 11 (depends on 8)

The device of claim 8, wherein the processing unit is further caused to:
create a plurality of candidate data subsets from a source data set based on a predetermined coverage rate for combinations of source dimensions of the source data set, each of the plurality of candidate data subsets covering at least two of the source dimensions;
combine at least two of the plurality of candidate data subsets into a combined candidate data subset such that the combined candidate data subset covers source dimensions of the at least two candidate data subsets;
identify, from the plurality of candidate data subsets, a candidate data subset with source dimensions covered by the combined candidate data subset; and
determine the plurality of data subsets based on remaining candidate data subsets other than the identified candidate data subset.

### Claim 12 (depends on 11)

The device of claim 11, wherein the processing unit is further caused to select the at least two candidate data subsets by:
determining a data size of each of the plurality of candidate data subsets; and
selecting, from the plurality of candidate data subsets, the at least two candidate data subsets with respective data sizes smaller than a threshold data size.

### Claim 13 (depends on 12)

The device of claim 12, wherein, to determine the data size of each of the plurality of candidate data subsets, the processing unit is caused to:
sample a plurality of data entries from data entries included in a given candidate data subset;
determine a first number of different data entries and a second number of data entries having a frequency of occurrence lower than a threshold frequency among the sampled plurality of data entries;
determine, based on the first number and the second number, a number of different data entries included in the given candidate data subset; and
determine, based on the number of the different data entries, the data size of the given candidate data subset.

### Claim 14 (depends on 11)

The device of claim 11, wherein, to determine the plurality of data subsets based on the remaining candidate data subsets, the processing unit is caused to:
determine whether a total data size of the remaining candidate data subsets exceeds a storage space available for storing the plurality of data subsets; and
in response to the total data size being equal to or smaller than the storage space, determine the remaining candidate data subsets as the plurality of data subsets.

### Claim 15

A non-transitory computer storage medium with computer-executable instructions stored thereon, the instructions comprising:
receiving a query including a plurality of query items associated with a plurality of target dimensions of a data entry;
determining whether at least two of a plurality of data subsets are needed to cover the plurality of target dimensions, at least one of the plurality of data subsets including data entries corresponding to at least one of the plurality of target dimensions;
in response to determining that the at least two of the plurality of data subsets are needed to cover the plurality of target dimensions, decomposing the query into a plurality of subqueries, each of the plurality of subqueries having at least one of the plurality of query items, wherein decomposing the query into the plurality of sub queries comprises:
determining correlations between respective pairs of query items among the plurality of query items, wherein determining the correlations comprises determining mutual information between the respective pairs of query items based on probabilities of presence of the plurality of query items in corresponding target dimensions; and
determining associations of the plurality of target dimensions based on the plurality of target dimensions corresponding to the respective data subsets and the correlations; and
determining a query result for the query by analyzing a data entry in the plurality of data subsets that is corresponding to a target dimension associated with the at least one query item in each of the plurality of subqueries.

### Claim 16 (depends on 15)

The non-transitory computer storage medium of claim 15, wherein decomposing the query into the plurality of subqueries further comprises:
decomposing, based on the determined associations, the query into the plurality of subqueries such that target dimensions corresponding to a subquery having one or more of the plurality of query items are determined as having an association.

### Claim 17 (depends on 15)

The non-transitory computer storage medium of claim 15, the instructions further comprising:
creating a plurality of candidate data subsets from a source data set based on a predetermined coverage rate for combinations of source dimensions of the source data set, each of the plurality of candidate data subsets covering at least two of the source dimensions;
combining at least two of the plurality of candidate data subsets into a combined candidate data subset such that the combined candidate data subset covers source dimensions of the at least two candidate data subsets;
identifying, from the plurality of candidate data subsets, a candidate data subset with source dimensions covered by the combined candidate data subset; and
determining the plurality of data subsets based on remaining candidate data subsets other than the identified candidate data subset.

### Claim 18 (depends on 17)

The non-transitory computer storage medium of claim 17, wherein the at least two candidate data subsets are selected by:
determining a data size of each of the plurality of candidate data subsets; and
selecting, from the plurality of candidate data subsets, the at least two candidate data subsets with respective data sizes smaller than a threshold data size.

### Claim 19 (depends on 15)

The non-transitory computer storage medium of claim 15, wherein determining the data size of each of the plurality of candidate data subsets comprises:
sampling a plurality of data entries from data entries included in a given candidate data subset;
determining a first number of different data entries and a second number of data entries having a frequency of occurrence lower than a threshold frequency among the sampled plurality of data entries;
determining, based on the first number and the second number, a number of different data entries included in the given candidate data subset; and
determining, based on the number of the different data entries, the data size of the given candidate data subset.

### Claim 20 (depends on 15)

The non-transitory computer storage medium of claim 15, wherein determining the associations of the plurality of target dimensions comprises:
determining two of the plurality of target dimensions as having an association based on at least one of:
a correlation between a pair of query items associated with the two target dimensions being greater than a threshold correlation;
the two target dimensions being covered by a first data subset of the plurality of data subsets; and
the two target dimensions and a further target dimension having an association with one of the two target dimensions being covered by a second data subset of the plurality of data subsets.