# US 2021/0279237 A1 · Systems and methods for accelerating exploratory statistical analysis

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

- Number: US 2021/0279237 A1
- Document ID: US20210279237A1
- Status: Published application
- Kind: A1
- Application number: 16/607,510
- Filed: 2018-04-23
- Published: 2021-09-09
- Earliest claimed: 2017-04-24
- Assignees: President and Fellows of Harvard College
- Applicants: President and Fellows of Harvard College
- Inventors: Stratos IDREOS; Wasay ABDUL; Niv DAYAN
- Web page: https://patentgrep.com/patent/US20210279237A1

## CPC

- G06F 16/2462: {Approximate or statistical queries}
- G06F 17/18: for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/24545: {Selectivity estimation or determination}
- G06F 16/2465: {Query processing support for facilitating data mining operations in structured databases}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Embodiments of the invention utilize a “data canopy” that breaks statistical measures down to basic primitives for various data portions and stores the basic aggregates in a library within an in-memory data structure. When a queried statistical measure involves a basic aggregate stored in the library over a data portion that at least partially overlaps the data portion associated with the basic aggregate, the basic aggregate may be reused in the statistical computation of the queried measure.

## Claims

### Claim 1

An apparatus for determining statistical properties of data, the apparatus comprising:
a computer memory for storing (i) a user-supplied statistical query and (ii) a plurality of basic statistical primitives, each basic statistical primitive corresponding to a plurality of data chunks, each of the chunks corresponding to a smallest logical partition of data that includes consecutive values of data from a data structure; and
a computer processor configured to:
process the statistical query to identify at least one statistical computation and at least one data range corresponding to the at least one statistical computation;
map the at least one data range to a subset of the data chunks;
map the at least one statistical computation to a subset of the basic statistical primitives;
perform the statistical computation; and
respond to the statistical query with the statistical computation, wherein the statistical computation is based at least in part on the subset of data chunks and the subset of basic statistical primitives to thereby reduce a latency response time to the statistical query.

### Claim 2 (depends on 1)

The system of claim 1, wherein the plurality of basic statistical primitives is computed prior to processing the received statistic query.

### Claim 3 (depends on 1)

The system of claim 1, wherein the plurality of basic statistical primitives is computed during process of the received statistic query.

### Claim 4 (depends on 1)

The system of claim 1, wherein the plurality of basic statistical primitives is stored as a set of segment trees.

### Claim 5 (depends on 4)

The system of claim 4, wherein the segment trees comprise binary trees.

### Claim 6 (depends on 4)

The system of claim 4, wherein each segment tree is associated with a pointer stored in the computer memory, and the computer processor is further configured to follow the pointers to access the corresponding segment trees for retrieving the basic statistical primitives.

### Claim 7 (depends on 4)

The system of claim 4, wherein the at least one data range comprises a first portion that aligns with boundaries of the subset of the data chunks and a second portion that does not align with boundaries of the subset of the data chunks, the processor being further configured to (i) access data associated with the second portion, (ii) compute at least one new basic statistical primitive corresponding to the data associated with the second portion, and (iii) perform the statistical computation based at least in part on the new basic statistical primitive.

### Claim 8 (depends on 7)

The system of claim 7, wherein the computer processor is further configured to:
compute a first query cost associated with (i) accessing the data associated with the second portion of the at least one data range and (ii) accessing the segment trees associated with the subset of the basic statistical primitives;
compute a second query cost associated with accessing data associated with the first and second portions; and
determine a critical range size based at least in part on the first and second query costs.

### Claim 9 (depends on 8)

The system of claim 8, wherein the computer processor is further configured to:
compare the at least one data range to the determined critical range size; and
if the at least one data range is smaller than the determined critical range size, access data associated with the at least one data range and, based thereon, perform the statistical computation.

### Claim 10 (depends on 4)

The system of claim 4, wherein the computer processor is further configured to determine an optimal size of the chunks based at least in part on a number of segment trees associated with the first portion of the at least one data range.

### Claim 11 (depends on 10)

The system of claim 10, wherein the computer processor is further configured to: determine an optimal depth of the segment trees based at least in part on the optimal size of the chunks; and
perform the statistical computation based at least in part on the basic statistical primitives associated with the segment trees within the determined optimal depth.

### Claim 12 (depends on 1)

The system of claim 1, wherein the computer memory further stores an eviction policy and the processor is further configured to evict a portion of the stored basic statistical primitives and/or a portion of the data in the data structure from the computer memory based on the eviction policy.

### Claim 13

A method of determining statistical properties of data, the method comprising:
storing, in a computer memory, a plurality of basic statistical primitives, each basic statistical primitive corresponding to a plurality of data chunks, each of the chunks corresponding to a smallest logical partition of data that includes consecutive values of data from a data structure;
receiving a statistical query from a user;
processing the received statistical query to thereby identify at least one statistical computation and at least one data range corresponding to the at least one statistical computation;
computationally mapping the at least one data range to a subset of the data chunks;
computationally mapping the at least one statistical computation to a subset of the basic statistical primitives;
performing the statistical computation; and
responding to the statistical query with the statistical computation, wherein the statistical computation is based at least in part on the subset of data chunks and the subset of basic statistical primitives to thereby reduce a latency response time to the statistical query.

### Claim 14 (depends on 13)

The method of claim 13, wherein the plurality of basic statistical primitives is computed prior to processing the received statistic query.

### Claim 15 (depends on 13)

The method of claim 13, wherein the plurality of basic statistical primitives is computed during process of the received statistic query.

### Claim 16 (depends on 13)

The method of claim 13, wherein the plurality of basic statistical primitives is stored as a set of segment trees.

### Claim 17 (depends on 16)

The method of claim 16, wherein the segment trees comprise binary trees.

### Claim 18 (depends on 16)

The method of claim 16, wherein each segment tree is associated with a pointer stored in the computer memory, the method further comprising following the pointers to access the corresponding segment trees for retrieving the basic statistical primitives.

### Claim 19 (depends on 16)

The method of claim 16, wherein the at least one data range comprises a first portion that aligns with boundaries of the subset of the data chunks and a second portion that does not align with boundaries of the subset of the data chunks, the method further comprising (i) accessing data associated with the second portion, (ii) computing at least one new basic statistical primitive corresponding to the data associated with the second portion, and (iii) performing the statistical computation based at least in part on the new basic statistical primitive.

### Claim 20 (depends on 19)

The method of claim 19, further comprising:
computing a first query cost associated with (i) accessing the data associated with the second portion of the at least one data range and (ii) accessing the segment trees associated with the subset of the basic statistical primitives;
computing a second query cost associated with accessing data associated with the first and second portions; and
determining a critical range size based at least in part on the first and second query costs.

### Claim 21 (depends on 20)

The method of claim 20, further comprising:
comparing the at least one data range to the determined critical range size; and
if the at least one data range is smaller than the determined critical range size, accessing data associated with the at least one data range and, based thereon, performing the statistical computation.

### Claim 22 (depends on 16)

The method of claim 16, further comprising determining an optimal size of the chunks based at least in part on a number of segment trees associated with the first portion of the at least one data range.

### Claim 23 (depends on 22)

The method of claim 22, further comprising:
determining an optimal depth of the segment trees based at least in part on the optimal size of the chunks; and
performing the statistical computation based at least in part on the basic statistical primitives associated with the segment trees within the determined optimal depth.

### Claim 24 (depends on 13)

The method of claim 13, further comprising:
storing an eviction policy in the computer memory further; and
evicting a portion of the stored basic statistical primitives and/or a portion of the data in the data structure from the computer memory based on the eviction policy.
