METHODS FOR STRATIFIED SAMPLING-BASED QUERY EXECUTION
A method for stratified-sampling-based query execution includes: receiving a query; collecting a first data sample from the first dataset using a non-stratified sampling technique; performing statistical analysis on the first data sample; identifying a stratum classifier from the statistical analysis; generating a stratum classification by calculating strata boundaries for the stratum classifier; and calculating a result to the query based on analysis of the second data sample.
1 . A method for determining a result to a query, comprising:
identifying a target dataset containing data relevant to the query from an event database, wherein each datum within the target dataset is associated with a user identifier and a set of stratum classifier values;
sampling a sampled dataset from the target dataset based on the respective user identifiers;
segmenting the sampled dataset into a set of strata based on the respective stratum classifier values of each datum, wherein the set of strata are determined by determining a set of multi-dimensional distributions of the sampled dataset across a classifier space and determining a set of strata that maximize clustering across the set of multi-dimensional distributions; and
calculating the result to the query based on an analysis dataset determined based on the set of strata.
2 . The method of claim 1 , wherein the analysis dataset is sampled from each stratum of the set of strata.
3 . The method of claim 1 , wherein the analysis dataset further comprises data not contained in the target dataset.
4 . The method of claim 1 , wherein the event database comprises a plurality of data shards partitioned across a plurality of data nodes of a distributed computing system.
5 . The method of claim 4 , wherein each data shard comprises a set of user identifiers and user activity data.
6 . The method of claim 1 , wherein determining the set of strata that maximize clustering comprises:
identifying different modes in the multidimensional distributions; and
segmenting different modes of the sampled dataset into different strata.
7 . The method of claim 1 , wherein calculating the result to the query comprises scaling the result based on a population metric.
8 . The method of claim 1 , wherein the query comprises at least one of event datasets, time ranges, filters, partition functions, or metric functions.
9 . The method of claim 1 , wherein the result comprises at least one of: raw event data, metric data, or confidence measure.
10 . The method of claim 1 , wherein calculating the result to the query based on the analysis dataset comprises:
in a first pass, scanning a subset of data from multiple shards contained within the sampled dataset to identify a set of identifiers;
in a second pass, scanning all shards containing data relevant to the set of identifiers; and
calculating the result to the query based on the second pass.
11 . The method of claim 1 , further comprising sampling the analysis dataset, wherein sampling the analysis dataset comprises sampling data from each stratum of the set of strata using a stratified sampling technique until a variance of the analysis dataset is lower than a threshold variance.
12 : A method for query execution, comprising:
identifying a target dataset based on a set of user identifiers, wherein each datum within the target dataset is associated with a user identifier;
determining a set of multi-dimensional distributions of the target dataset across a classifier space, wherein the set of multi-dimensional distributions have at least three dimensions;
segmenting the target dataset into a set of strata based on the set of multi-dimensional distributions; and
executing a query based on an analysis of a sampled dataset, wherein the sampled dataset is sampled from each stratum of the set of strata.
13 . The method of claim 12 , wherein the set of multi-dimensional distributions of the target dataset comprises a plurality of three-dimensional distributions of different potential classifiers.
14 . The method of claim 12 , wherein determining the set of stratum classifiers for the target dataset based on the set of multi-dimensional distributions comprises determining a set of strata that maximizes clustering within the set of multi-dimensional distributions.
15 . The method of claim 14 , wherein identifying the target dataset comprises identifying the target dataset from a queried dataset is stored in an event database, wherein the event database comprises a plurality of data shards partitioned across a plurality of data nodes of a distributed computing system.
16 . The method of claim 12 , wherein sampling the sampled dataset from each stratum of the set of strata comprises sampling a subset of data from the respective stratum based on a user identifier associated with each datum.
17 . The method of claim 12 , wherein segmenting the target dataset into the set of strata comprises:
identifying different modes of the target dataset within the set of multi-dimensional distributions; and
separating the different modes of the target dataset into disjoint sections, wherein each disjoint section comprises a strata.
18 . The method of claim 12 , wherein executing the query comprises iteratively altering the set of stratum classifiers to reduce a variance associated with the sampled dataset.
19 . The method of claim 12 , wherein executing the query comprises executing a multiple pass sampling method to obtain the sampled dataset.
20 . The method of claim 12 , wherein sampling the sampled dataset from each stratum of the set of strata comprises sampling each stratum using a random sampling technique.