Systems and methods for accelerating exploratory statistical analysis

1. A system for determining statistical properties of data, the apparatus comprising:

a computer memory containing (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, 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;

map the at least one statistical computation to a subset of the basic statistical primitives;

access data associated with the second portion;

compute at least one new basic statistical primitive corresponding to the data associated with the second portion;

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, the subset of basic statistical primitives, and the at least one new basic statistical primitive.

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

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

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

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

6. 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.

7. The system of claim 4 , 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.

8. The system of claim 7 , 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.

9. 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.

10. The system of claim 9 , 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.

11. 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.

12. 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, 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;

computationally mapping the at least one statistical computation to a subset of the basic statistical primitives;

accessing data associated with the second portion;

computing at least one new basic statistical primitive corresponding to the data associated with the second portion;

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, the subset of basic statistical primitives, and the at least one new basic statistical primitive.

13. The system of claim 1 , wherein performing the statistical computation includes reusing values corresponding to the subset of the basic statistical primitives for the subset of data chunks.

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

15. The method of claim 12 , wherein the plurality of basic statistical primitives is computed during processing of the received statistic query.

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

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

18. 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.

19. The method of claim 16 , 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.

20. The method of claim 19 , 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.

21. 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.

22. The method of claim 21 , 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.

23. The method of claim 12 , further comprising:

further storing an eviction policy in the computer memory; 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.