A Random Sample Partition Data Model for Big Data
Analysis
Salman Salloum

Yulin He

∗

Joshua Zhexue Huang
Xiaoliang Zhang
Chenghao Wei Heping He

Tamer Z. Emara

arXiv:1712.04146v2 [cs.DC] 20 Jan 2018

Big Data Institute, College of Computer Science and Software Engineering, Shenzhen University,
Shenzhen 518060, Guangdong, China

{ssalloum, yulinhe, zx.huang, zhangxlassz, tamer, chenghao.wei}@szu.edu.cn
heping.he@outlook.com
ABSTRACT

2. INTRODUCTION

Big data sets must be carefully partitioned into statistically
similar data subsets that can be used as representative samples for big data analysis tasks. In this paper, we propose
the random sample partition (RSP) data model to represent a big data set as a set of non-overlapping data subsets,
called RSP data blocks, where each RSP data block has a
probability distribution similar to the whole big data set.
Under this data model, efficient block level sampling is used
to randomly select RSP data blocks, replacing expensive
record level sampling to select sample data from a big distributed data set on a computing cluster. We show how RSP
data blocks can be employed to estimate statistics of a big
data set and build models which are equivalent to those built
from the whole big data set. In this approach, analysis of a
big data set becomes analysis of few RSP data blocks which
have been generated in advance on the computing cluster.
Therefore, the new method for data analysis based on RSP
data blocks is scalable to big data.

Big data analysis is a challenging problem in many application areas especially with the ever increasing volume of
data. In this regard, divide-and-conquer is used as a common strategy in current big data frameworks to distribute
both data and computation on computing clusters. A big
data set is divided into smaller data blocks and distributed
on the nodes of a computing cluster so that data-parallel
computations are run on these blocks. However, analyzing a big data set all at once may require more computing resources than available ones on the computing cluster.
Moreover, current frameworks require new data-parallel implementations of traditional data mining and analysis algorithms. In order to enable efficient and effective big data
analysis when data volume goes beyond the available computing resources, a different approach is required which considers computational, as well as statistical, aspects of big
data on both data management and analysis levels. Such an
approach is essential for investigating a key research problem nowadays: should the full set of data be used to find
properties and reveal valuable insights from big data or a
subset of this data be good enough?
Although the existing mainstream big data frameworks
(e.g., Hadoop’s MapReduce [2], Apache Spark [11]) run dataparallel computations over distributed data blocks on computing clusters, current data partitioning techniques do not
consider the probability distributions of data in these blocks.
Sequentially chunking a big data set into small data blocks
does not guarantee that each block is a random sample in
case that data is not randomly ordered in the big data set.
In such case, using data blocks directly to estimate statistics
and build models may lead to statistically incorrect or biased results. Furthermore, classical random sampling techniques, which require a full scan of the data set each time a
random sample is generated, are no longer effective with the
increasing volume of big data sets stored in distributed systems [10]. Thus, partitioning a big data set into small data
subsets (i.e., data blocks), each being a random sample of
the whole data set, is a fundamental operation for big data
analysis. These data blocks can be used to estimate statistics and build models, especially when analyzing big data
sets requires more than the available resources in order to
meet specific application requirements [4][3]. Therefore, it
is necessary to develop statistically-aware data partitioning
methods which enable effective and efficient usage of data
blocks to fulfill the statistical and scalability requirements

1.

KEY INSIGHTS
• Big data analysis requires not only computationally
efficient, but also statistically effective approaches.
• A random sample partition (RSP) data model for big
data can be used efficiently and effectively in building
ensemble models, estimating statistics, and other big
data analysis tasks on a computing cluster.
• Experiments show that a sample of RSP data blocks
from an RSP data model can be used to get approximate analysis results equivalent to those using the
whole data set.
• In addition to the scalability advantage, adopting this
approach saves time and computing resources.

∗Corresponding Author

of big data analysis tasks.
Multivariate data is a common form of data in many application areas. Let D= {x1 , x2 , · · · , xN } be a multivariate
data set of N records where N is too big for statistical analysis of D on a single machine. Each record is depicted with
M attributes or features, i.e., xi = (xi1 , xi2 , · · · , xiM ) for
any i ∈ {1, 2, · · · , N }. In order to make a statistically-aware
data partitioning, we propose the random sample partition (RSP) data model to represent D as a set of nonoverlapping data blocks ( called RSP data blocks) where
each block itself is a random sample. If the records in D
are independently and identically distributed (i.i.d), we call
D a randomized data set (i.e., the order of records in D is
random). Our previous empirical study [8] showed that data
sets are naturally randomized in many application areas and
thus can be directly represented as RSP data models using
the current data partitioning techniques. In case that the
data is not randomized, scalable algorithms are developed
to randomize big data sets on computing clusters.
The RSP data blocks in an RSP can be directly drawn
as random samples of the whole big data set in data exploratory and analysis tasks. Since the RSP data blocks are
generated in advance and stored on the computing cluster,
randomly selecting a set of RSP data blocks is much efficient than sampling a set of records from a distributed big
data file because the full scan on the whole file is no longer
needed. In this article, we show that a small sample of few
RSP data blocks from an RSP is enough to build models
and compute the statistical estimates which are equivalent
to those calculated from the whole big data set. We propose the asymptotic ensemble learning framework for big
data analysis which depends on ensemble methods as a general approach for building block-based ensemble models from
RSP data blocks. With this framework, results can be improved incrementally without the need to load and analyze
the whole big data set all at once. This approach can be
generalized for statistics estimation by defining appropriate
ensemble functions (e.g., averaging the means from different
RSP data blocks).
In this article, we introduce the RSP data model of a
big data set and show how RSP data blocks are essential
for efficient and effective big data analysis. We also discuss
how this new RSP data model can be employed for different
data analysis tasks using the asymptotic ensemble learning
framework. Finally, we summarize the implications of this
new model and conclude this article with some of our current
works.

3.

DISTRIBUTED DATA-PARALLEL COMPUTING

As data volume in different application areas goes beyond the petabyte scale, divide-and-conquer is taken as a
general strategy to process big data on computing clusters
considering the recent advancements in distributed and parallel computing technology. In this strategy, a big data file
is chunked into small non-overlapping data blocks and distributed on the nodes of a computing cluster using a distributed file system such as Hadoop distributed file system
(HDFS) [9]. Then, data-parallel computations are run on
these blocks considering data locality. After that, intermediate results from processed blocks are integrated to produce
the final result of the whole data set. This is usually done

using the MapReduce computing model [2] adopted by the
mainstream big data frameworks such as Apache Hadoop 1 ,
Apache Spark 2 , and Microsoft R Server 3 .
As a unified engine for big data processing, Apache Spark
has been adopted in a variety of applications in both academia
and industry [12][7] as a new generation engine after Hadoop’s
MapReduce. It uses a new data abstraction and in-memory
computation model, the resilient distributed datasets (RDDs)
[11], where collections of objects (e.g., records) are partitioned across a cluster, kept in memory and processed in
parallel. Similarly, Microsoft R Server addresses the inmemory limitations of the open source statistical system,
R, by adding parallel and chunk-wise distributed processes
across multiple cores and nodes. It comes with the proprietary eXternal data frame (XDF) and a framework for
parallel external memory algorithms (PEMAs) of statistical analysis and machine learning. Both Apache Spark and
Microsoft R Server operate on data stored on HDFS. A fundamental operation is importing such data into XDF format
or RDDs, and then running data-parallel operations.
Although the current frameworks employ the data-parallel
model to run scalable algorithms on computing clusters, analyzing a whole big data set may exceed the available computing resources. There are some technical solutions for this
problem such as loading and processing blocks in batches
according to the available resources, but this still requires
analyzing each block in the data set which leads to longer
computation time. Furthermore, current data partitioning
techniques simply cut data sets into blocks without considering data probability distributions in these blocks. This
can lead to statistically incorrect or biased results in some
data analysis tasks. We argue that solving big data analysis
problems requires solutions which not only consider the computational aspects of big data, but also the statistical ones.
To address this issue, we propose the RSP data model.

4. RSP OF BIG DATA
The RSP data model is a new model to represent a big
data set as a set of RSP data blocks. It depends on two
fundamental concepts: random sample and partition of a
data set. First, we define these basic concepts and show
how they are applied to the RSP data models of big data
sets. Then, we present a formal definition of the RSP data
model. For convenience of discussion, we do not consider
the set anisotropy.

Random Sample of a Big Data Set.
Sampling is an essential technique for big data analysis
when the volume of data goes beyond the available computing resources. Random samples are widely used in statistics
to explore the statistical properties and distributions of big
data, calculate the statistics estimates and build regression
and classification models. In big data analysis, we define a
random sample of a big data set as follows:
Definition 1 (Random Sample): Let D = {x1 , x2 , · · · ,
xN } be a big data set of N records. Let Dn be a subset of D
containing n records chosen from D using a random process.
1

http://hadoop.apache.org/
https://spark.apache.org/
3
https://www.microsoft.com/en-us/cloud-platform/rserver
2

Dn is a random sample of D if
E[F̃n (x)] = F (x), for n ≤ N
where F̃n (x) and F (x) denote the sample distribution functions of Dn and D, respectively. E[F̃n (x)] denotes the expectation of F̃n (x).
According to the law of large numbers, we consider that
a big data set is a random sample of the population in a
certain application domain. For example, a big data set of
customers is a random sample of the customer’s population
in a company. Thus, we can use such data set to estimate the
distribution of all customers in the company. For big data
analysis, a random sample of a big data set D is often used
to investigate the statistical properties of D when D is too
big to be analyzed using the available computing resources.
A random sample is taken from D using a random sampling
process as stated in Lemma 1. However, if D is distributed
on a computing cluster, taking a random sample from D
itself is an computationally expensive process because a full
scan of D needs to be conducted on the distributed nodes
of the computing cluster. To avoid the random sampling
process on D in big data analysis, we can generate a set of
random samples from D in advance and save these random
samples to be used in analysis of D. This idea is materialized
in the RSP data model.

Partition of a Big Data Set.
On distributed file systems, a big data set D is divided
into small data blocks which are distributed on the nodes of
a computing cluster. Each block contains a subset of records
from D. From a mathematical point of view, this set of
blocks forms a partition of D. In mathematics, a partition
of a set is a grouping of the set’s elements into non-empty
subsets, in such a way that every element is included in one
and only one of the subsets4 .
Definition 2 (Partition of Data Set): Let D = {x1 ,
x2 , · · · , xN } be a data set containing N objects. Let T
be an operation which divides D into a set of subsets T =
{D1 , D2 , · · · , DK }. T is called a partition of data set D if
K
S
Dk = D;
(1)
k=1

(2) Di ∩ Dj = ∅, when i, j ∈ {1, 2, · · · , K} and i 6= j.
Accordingly, T is called a partition operation on D and each
Dk (k = 1, 2, · · · , K) is called a data block of D.
According to this definition, many partitions can be generated from a data set D. For example, an HDFS file is a
particular partition of D generated by partitioning operation
T to sequentially cutting the original data file D into data
blocks {D1 , D2 , · · · , DK }. Even with the same partitioning
operation, different partitions can be generated using different partitioning parameters such as the size of each block
or the number of records in each block. However, a key
issue with this sequential partitioning is that data blocks
may not have similar statistical properties as the big data
set. In fact, it is theoretically possible and practically required to find alternatives for generating a partition of a
data set which satisfies certain application requirements or
holds some statistical properties, e.g., each data block is a
random sample of D.
4

https://en.wikipedia.org/wiki/Partition of a set

Random Sample Partition of a Big Data Set.
We define the Random Sample Partition (RSP) to represent a big data set as a family of non-overlapping random
samples.
Definition 3 (Random Sample Partition): Let D =
{x1 , x2 , · · · , xN } be a big data set which is a random sample
of a population and assume F (x) is the sample distribution
function (s.d.f.) of D. Let T be a partition operation on D
and T = {D1 , D2 , · · · , DK } be a partition of D accordingly.
T is called a random sample partition of D if
E[F̃k (x)] = F (x) for each k = 1, 2, · · · , K,
where F̃k (x) denotes the sample distribution function of Dk
and E[F̃k (x)] denotes its expectation. Accordingly, each Dk
is called an RSP data block of D and T is called an RSP operation on D. In the next section, we discuss the partitioning
process to generate RSPs from big data sets.

5. TWO-STAGE DATA PARTITIONING
Given a big data set in HDFS, a partitioning algorithm is
required to convert the HDFS file into an RSP data model
of K RSP data blocks, each with n records, which are also
stored in HDFS. In this case, the partitioning algorithm
consists of two main steps: data chunking and data randomization as discussed below. The pseudo code is given in
Algorithm 1.
• Data Chunking: D is divided into P data blocks. We
call these blocks the original data blocks which are not
necessarily randomized. In the current big data frameworks, this operation is straightforward and available.
• Data Randomization: a slice of δ records is randomly
selected without replacement from each of the original
P data blocks to form a new RSP data block. First,
each original data block is randomized locally. Then,
the randomized block is further chunked into K subblocks, each with δ records. After that, a new RSP
block is created by selecting one sub-block from each
of the randomized original blocks and combining these
selected sub-blocks together. The last step is repeated
K times to produce the required number of RSP data
blocks where each RSP data block has n = Kδ records.
The number of records in a slice δ can be determined
depending on K and n (e.g., δ = n/K to distribute data
evenly over all blocks). The number of RSP data blocks K,
or the number of records in an RSP data block n, is selected
depending on both the available computing resources and
the target analysis tasks so that a single RSP data block
can be processed efficiently on one node (or core).
A prototype of this algorithm was implemented using the
Apache Spark’s RDD API. As a preliminary test on a small
cluster of 5 nodes (each node has 24 cores, 128 GB RAM
and 12.5 TB disk storage), Figure (1) shows the partitioning
time for synthesized numerical data. We can see how the
partitioning time increases almost linearly with the number
of records in the data set. This shows the scalability of such
partitioning algorithms. In this experiment, the number of
RSP data blocks is the same as the number of original blocks
where each block contains 100,000 records. However, we also
found that the partitioning time did not vary much when the

Algorithm 1 Partitioning Algorithm
Input:
- D: big data set;
- P : number of data blocks of D;
- n: number of records in an RSP data block;
- K: number of required RSP data blocks;
Method:
δ = n/K;
Divide D into P data blocks;
for i = 1 to P do
Randomize block Di ;
Sequentially cut each randomized Di into K sub-blocks,
each with δ records;
end for
for k = 1 to K do
Dk = φ;
for i = 1 to P do
Select one sub-block from Di without replacement;
Append the sub-block to Dk ;
end for
Save Dk as an RSP data block;
end for
T = {D1 ,D2 , · · · , DK };
Output:
- T: a set of RSP data blocks;

number of RSP data blocks is different from the number of
original blocks. Thus, this kind of algorithms can be used
to fulfill different requirements as the number of records in
a block is an essential factor for some analysis tasks.

6.

PROBABILITY DISTRIBUTIONS OF RSP
DATA BLOCKS

The key idea behind an RSP is partitioning a big data set
into RSP data blocks which can be used directly as random
samples of the whole data set. Thus, it is essential to investigate the statistical properties of these RSP data blocks.
We used hypothesis testing and exploratory data analysis
in our previous empirical studies [8] to compare RSP data
blocks. We discuss here the underlying theory of using the
RSP data blocks as random samples of the whole data set.
Each block in an RSP should follow a data distribution
similar to the whole data set. For a categorical feature,
records that belong to the same category should be evenly
distributed over all blocks. A good example is the label feature in a classification task. For example, Figure (2.a) shows
the distribution of a label feature (from HIGGS data set5 )
in the whole data set and some randomly selected RSP data
blocks. This also applies to continuous features as shown
in Figure (2.b). In addition, the similarity between RSP
data blocks and samples by simple random sampling, or the
whole data set if possible, can be computed using quantity
measures such as MMD measure [5].
Selecting a block from an RSP of D is equivalent to drawing a random sample directly from the big data set D. If
D is a randomized data set, cutting a block of n records is
equivalent to randomly selecting these n records. This also
applies when partitioning a non-randomized data set using
Algorithm 1 because each RSP data block is formed from
5

https://archive.ics.uci.edu/ml/datasets/HIGGS

Figure 1: Time for creating RSPs from synthesized
numerical datasets with 100 features using Apache
Spark on a computing cluster of 5 nodes (each node
has 24 cores, 128 GB RAM and 12.5 TB disk storage). The algorithm was run on 10 different sizes
of data, from 100 million records (1000 blocks) to
1 billion records (10000 blocks). The storage size is
approximately 100 GB for 100 million records and 1
TB for 1 billion records.

randomly selected records from all the original blocks. Thus,
each RSP data block from an RSP data model is equivalent
to a simple random sample from D. The underlying theory
of RSP data blocks is shown in Lemma 1 and Theorem 1.
Lemma 1: Suppose D = {x1 , x2 , · · · , xKδ } is a data set.
Randomly choose a permutation of the sequence 1, 2, · · · , Kδ
which is denoted as τ = {τ1 , τ2 , · · · , τKδ }. For each i =
1, · · · , K, set Di = {xτδ(i−1) +1 , xτδ(i−1) +2 , · · · , xτδi }, then
each Di is an RSP data block of D. Below, we prove this for
one dimensional data. It also applies to high dimensional
cases with minor modifications.
Proof : Suppose the sample distribution function of D and
Di are F (x) and Fi (x) (i = 1, 2, · · · , K) respectively. For
any real number x, let M denote the number of the records
in D whose values are not greater than x. Then, it is easy
to show M = Kδ · F (x). If si denotes the number of records
in Di whose values are not greater than x, then
E(si ) =

δ
X

j · P {si = j} =

j=1

=

δ
X
C j · C δ−j
j M δKδ−M
CKδ
j=1

δ−1
M
· CKδ−1 = δ · F (x),
δ
CKδ

So, the expectation of Fi (x) is
E[Fi (x)] =

E(si )
= F (x).
δ

Thus, each Di is an RSP data block of D.
Theorem 1: Suppose data set A has N1 records and
data set B has N2 records. If A1 is an RSP data block of
A with records n1 and
S B1 is an RSP data block of B
S with
records n2 , then A1 B1 is an RSP data block of A B as
N1
n1
= N
.
n2
2
Proof : Suppose the sample distribution functions of data

Figure 2: Probability distribution in data blocks and the whole data set.

blocks A, B, A1 and B1 are F1 (x), F2 (x), F̃1 (x) and F̃2 (x),
respectively. We have E[F̃1 (x)] = F1 (x) and E[F̃2 (x)] =
F2 (x). For any real number x, the number of records of
S
A1 B1 whose values are not greater than x is n1 F̃1 (x) +
n2 F̃S
Therefore, the sample distribution function of
2 (x).
A1 B1 is:
n1 F̃1 (x) + n2 F̃2 (x)
.
n1 + n2
S
Similarly, the sample distribution function of A B is:
F̃ (x) =

F (x) =

N1 F1 (x) + N2 F2 (x)
.
N1 + N2

The expectation of F̃ (x) is
n1 F̃1 (x) + n2 F̃2 (x)
]
n1 + n2
n1 E[F̃1 (x)] + n2 E[F̃2 (x)]
=
n1 + n2
n1
N1
F
(x)
+ F2 (x)
F1 (x) + F2 (x)
1
n
N
= 2 n1
= 2 N1
+1
+1
n2
N2

E[F̃ (x)] = E[

= F (x).
S
S
Therefore, A1 B1 is an RSP data block of A B.

7.

BLOCK LEVEL SAMPLE: A SAMPLE OF
RANDOM SAMPLE DATA BLOCKS

As each block in an RSP data model is a random sample of big data set D, the RSP data model can be used as
a reduced representative space to directly draw samples of
RSP data blocks instead of drawing samples of individual
records from D. In contrast to the classical record level
sampling, we call this sampling method as block level sampling where blocks are sampled, without replacement and
with equal probability. Thus, a sample of RSP data blocks
is a set of non-overlapping random samples from D. This
is more efficient especially when K << N because it avoids
the full scan of D each time a random sample is needed.
Definition 4 (Block Level Sample): Let T be an RSP of
a big data set D. S = {D1 , D2 , · · · , Dg }, where g < K, is a
block level sample with RSP data blocks randomly selected
from T without replacement and with equal probability.
The block-sampling operation is called separately in each
analysis process so that samples of RSP data blocks are selected without replacement, i.e., without repeating a block
neither in the same sample nor in other samples in the same
analysis process. The number of RSP data blocks g in a
block sample depends on the available computing resources
so that each selected block can be loaded and analyzed locally on one node or core. In such case, a sample of RSP
data blocks is analyzed in one batch in a perfectly parallel manner. This sampling process can be refined to select
blocks depending on the availability of nodes on a computing

cluster which can lead to better scheduling algorithms.
Block level sampling can be employed for designing data
analysis pipelines, for example, analyzing big data in batches
(i.e., each batch uses one sample of RSP data blocks) to stepwise collect and improve statistical models and estimates
rather than trying to load the data set all at once. Further
statistical investigation can be done on the selected RSP
data blocks. For example, exploratory data analysis techniques can be used to visualize and compare data distributions between RSP data blocks and classical random samples. Quantitative measures can be also used, such as the
maximum mean discrepancy (MMD) measure [5] for the similarity between data distributions and Hotelling’s T-Square
test for the difference between means of features. This kind
of statistical testing is fundamental for many data analysis
tasks. In the following sections, we describe how block level
samples can be used effectively and efficiently for estimating
statistics and building ensemble models.

8.

ESTIMATION FROM A SAMPLE OF RSP
DATA BLOCKS

The method of bootstrapping multiple samples from a
given data set to evaluate statistical estimates is widely used
in statistics. However, traditional bootstrap method is not
suitable for a distributed big data set because of the high
computational and storage costs. One approach for reducing these costs is drawing samples of small sizes such as the
bag of little bootstraps [6] to calculate the average estimates
from those small samples. However, this still requires scanning the whole data set each time a sample is needed. In
addition, extra storage space to store these samples is also
inevitable in most cases. Instead, storing a big data set in
an RSP data model can avoid both the repeated random
sampling and extra storage costs. This gives a chance, not
only to directly estimate statistics and sample distributions
from RSP data blocks, but also to turn the focus into improving the quality of estimations because the whole data
set is stored, by default, as a collection of random samples.
Estimated statistics from individual RSP data blocks of
an RSP data model can be combined (e.g., by averaging) in
a single estimation which is generally better than any of the
individual ones. For example, Figure (3) shows the average
means of 4 features in HIGGS data. Each value is an average
of the estimated means from blocks used up to that point.
We can see the error of the means is not significant even in
the first several batches and the estimated mean values converge to the true mean value while adding more blocks. In a
similar way, Figure (4) shows the estimated standard deviations for the same features in HIGGS data. As we can see,
samples of RSP data blocks from an RSP data model can be
used efficiently to estimate the statistics of a big data set.
This approach can be generalized to other statistical analysis tasks such as building classification or regression models.
In the following section, we show how a sample of RSP data
blocks can be used effectively for building ensemble models.

9.

ASYMPTOTIC ENSEMBLE LEARNING
FRAMEWORK

The RSP data blocks of an RSP data model can be used as
component data sets to build ensemble models for different
tasks (e.g., classification, regression, clustering). Ensemble
methods use multiple base models built with the same or

Figure 3: Block level estimation of means of 4 features in HIGGS data using 5 RSP data blocks.
Each point represents the estimated value after each
batch (averaged from 100 runs). The dotted line
represents the true value calculated from the entire
HIGGS data.

Figure 4: Block level estimation of standard deviations of 4 features in HIGGS data using 5 RSP data
blocks. Each point represents the estimated value
after each batch (averaged from 100 runs). The dotted line represents the true value calculated from the
entire HIGGS data.
different algorithms from different component data sets. The
results from base models are combined in a single ensemble
model which generally outperforms each of the individual
ones [1].
As shown in Figure (5), the asymptotic ensemble learning

Figure 5: Asymptotic Ensemble Learning Framework: Base models are built from a sample of RSP data
blocks and then combined in an ensemble model.

framework provides a general framework to analyze big data
by building base models from randomly selected RSP data
blocks of the big data set. Given a learning algorithm F and
an RSP data model T = {D1 , D2 , · · · , DK }, an ensemble
model are learnt from RSD data blocks in batches as follows:
• Blocks Selection: a sample of RSP data blocks is drawn
without replacement from the RSP data model, e.g.,
D5 , D120 , D506 and D890 . This sample of RSP data
blocks is put in one batch.
• Learning Base Models: A base model is built from each
selected RSP data block. These base models are built
in parallel on a computing cluster. For instance, four
classifiers π1 , π2 , π3 , π4 are built in parallel from the
four selected RSP data blocks as shown in the figure.
• Ensemble Learning and Update: The base models are
collected to form an ensemble model Π which is updated after each batch.
• Ensemble Evaluation: If the current ensemble model
Π is evaluated. If it does not satisfy the termination
condition(s), go back to the first step; otherwise, output the ensemble model. This process continues until a
satisfactory ensemble model Π is obtained or all blocks
are used up.
The basic operations in building an ensemble model using
the asymptotic ensemble learning framework are described
in Algorithm 2. Base models are built from RSP data block
samples until there is no significant increase in the accuracy
of the ensemble model. BlocksSampling function is used to
select g RSP data blocks from T. Ω() is an evaluation function to evaluate whether the ensemble model Π satisfies the

Figure 6: Accuracy of block-based ensemble classifiers on HIGGS data averaged from 100 runs of
Algorithm 2. Base models were trained in batches
of 5 blocks with 1% data in each block. The dotted
line is the accuracy of a single model built using all
data with the same algorithm.

analysis requirements. An empirical study of this method
was presented in [8].
A prototype of this framework was implemented using Microsoft R Server packages with Apache Spark. Taking decision trees as an example, Figure (6) shows the results on
HIGGS data set. Ensemble models were built using the previous ensemble process and evaluated on the same test data

Algorithm 2 Asymptotic Ensemble Learning Algorithm
Input:
- T: an RSP of D;
- f : a learning algorithm;
- g: number of blocks in one batch;
Method:
Π = φ;
1- Blocks Selection: S = BlocksSampling(T, f, g)
2- Base Models Learning:
for Dq ∈ S do
πq = f (Dq )
end for
3- Ensemble Update: Π = Π + {πq }gq=1
4- Ensemble Evaluation:
If Ω(Π) < threshold (or no more blocks)
Stop
Else
Go to 1
Output: Π

after each batch. We can see how the ensemble model accuracy changes after each batch. However, this change is
not significant after using about 15-20% of the data. Furthermore, the ensemble model accuracy is generally better
than the accuracy of a single model built using the whole
data (the dotted line in the figure). This framework can also
be used to get indicators of a model’s quality using only a
subset of RSP data blocks.
These results show that a small subset of RSP data blocks
from a big data set are enough to obtain ensemble models
equivalent to the models built using the whole data set. In
this way, computation time can be decreased significantly
as shown in Figure (7). As far as the number of RSP data
blocks in a batch is equal to or smaller than the number of
available executors in the computing cluster, the computation time of a batch does not vary a lot. Even when using
all RSP data blocks of a big data set in one batch, which is
generally not required, it still takes less time than required
for training a single model from the whole data (about 8
minutes for HIGGS data set on the same cluster).

Figure 7: Training time for block-based models on a
cluster of 5 nodes. Each block holds 1% of the data
(e.g., 5% of data means that 5 blocks were used in
one batch). For comparison, the time for building
a single model from all data on the same cluster is
shown on the far right.

10. ADVANTAGES AND IMPLICATIONS

In this work, we argue that alleviating the challenges of
big data analysis, especially when data volume goes beyond
the available computing resources, requires a different way
of thinking. It is not efficient to treat data analysis as a
pure computational problem and ignore its statistical aspects whether on the data analysis level or data management level. Applying the RSP data model on big data sets
is a promising approach for a variety of data analysis tasks.
It can open the door for further investigations of new innovative solutions to cope with the ever increasing volume of
big data sets.
A key advantage is that RSP data blocks can be used
directly as random samples without the need for expensive
online sampling and extra storage space. These blocks can
be used to obtain unbiased estimators of a big data set because each data block has approximately the same distribution as the whole data set. In addition, creating an RSP
data model from a big data set is only performed once. After that, samples of RSP data blocks can be used directly,
not only for approximate computing and ensemble learning,
but also for exploratory data analysis, interactive analysis
and quickly piloting models. As we can see from the experimental results, while there is no significant difference
in accuracy, block-based ensembles and estimations require
less computational time and resources. At least, equivalent
results can be reached using only a small portion of a big
data set. In this way, memory limitation is not critical anymore as data is analyzed in batches and RSP data blocks
are small enough to be processed on single nodes or cores.
Since the RSP based analysis approach enables reusing
sequential algorithms for conducting data analysis on RSP
data blocks without the need to rewrite these algorithms
for distributed and parallel environment, tackling big data
analysis problems turns to solving small data problems and
defining proper ensemble or combination functions. Furthermore, statistically-aware data partitioning algorithms can be
implemented using the current APIs of distributed computation engines, such as Apache Hadoop and Apache Spark.
As a result, many of the current algorithms can be scaled to
big data without the need for new parallel implementations.
This approach can also help in separating big data storage
from big data analysis so that selected RSP data blocks can
be loaded on or transferred to local machines or computing clusters for analysis. As such, a computing cluster can
be used to analyze data sets stored in different clusters by
combining the outputs from different locations. If RSP data
blocks from different data centers have different probability distributions, a combination criterion can be defined to
produce representative RSP data blocks of the whole data
set and then analyze the combined blocks to produce the
estimated results of the big data in different data centers.

11. CONCLUSIONS
In this article, we introduced the random sample partition (RSP) data model to represent a big data set as a set
of RSP data blocks where each RSP data block itself is a
random sample of the whole data set. An RSP data model
of a big data set can be created using distributed data partitioning algorithms. We showed that block level samples
from an RSP data model can be used efficiently and effectively for different data analysis tasks such as statistics estimation and ensemble learning. We demonstrated how the

asymptotic ensemble learning framework is used as a general
framework for building block-based ensemble models using
block samples from an RSP data model. For further testing
and investigation, some of our future works include implementing different statistically-aware partitioning algorithms,
extending our framework for building random subspace base
models in order to increase the variety of base models as well
as testing other data analysis tasks.

12. ACKNOWLEDGMENTS
The first author and second author contributed equally
the same to this paper which was supported by grants from
National Natural Science Foundation of China (No. 61473194,
61503252) and China Postdoctoral Science Foundation (No.
2016T90799).

13. REFERENCES
[1] C. C. Aggarwal. Data Mining: The Textbook. Springer
Publishing Company, Incorporated, 2015.
[2] J. Dean and S. Ghemawat. Mapreduce: Simplified
data processing on large clusters.
COMMUNICATIONS OF THE ACM, 51(1):107–113,
JAN 2008.
[3] J. Gantz and D. Reinsel. Extracting value from chaos,
2011.
[4] Í. Goiri, R. Bianchini, S. Nagarakatte, and T. D.
Nguyen. Approxhadoop: Bringing approximations to
mapreduce frameworks. In Proceedings of the
Twentieth International Conference on Architectural
Support for Programming Languages and Operating
Systems, pages 383–397. ACM, 2015.
[5] A. Gretton, K. M. Borgwardt, M. J. Rasch,
B. Schölkopf, and A. Smola. A kernel two-sample test.
J. Mach. Learn. Res., 13:723–773, Mar. 2012.
[6] A. Kleiner, A. Talwalkar, P. Sarkar, and M. I. Jordan.
The Big Data Bootstrap. In ICML, 2012.
[7] S. Salloum, R. Dautov, X. Chen, P. X. Peng, and J. Z.
Huang. Big data analytics on apache spark.
International Journal of Data Science and Analytics,
1(3):145–164, 2016.
[8] S. Salloum, J. Z. Huang, and Y. He. Empirical
analysis of asymptotic ensemble learning for big data.
In Proceedings of the 3rd IEEE/ACM International
Conference on Big Data Computing, Applications and
Technologies, BDCAT ’16, pages 8–17, New York, NY,
USA, 2016. ACM.
[9] K. Shvachko, H. Kuang, S. Radia, and R. Chansler.
The hadoop distributed file system. In 2010 IEEE
26th Symposium on Mass Storage Systems and
Technologies (MSST), pages 1–10, May 2010.
[10] M. Vojnovic, F. Xu, and J. Zhou. Sampling based
range partition methods for big data analytics.
Technical Report MSR-TR-2012-18, February 2012.
[11] M. Zaharia, M. Chowdhury, T. Das, and A. Dave.
Resilient distributed datasets: A fault-tolerant
abstraction for in-memory cluster computing. NSDI’12
Proceedings of the 9th USENIX conference on
Networked Systems Design and Implementation, pages
2–2, Apr. 2012.
[12] M. Zaharia, R. S. Xin, P. Wendell, T. Das,
M. Armbrust, A. Dave, X. Meng, J. Rosen,

S. Venkataraman, M. J. Franklin, A. Ghodsi,
J. Gonzalez, S. Shenker, and I. Stoica. Apache spark:
A unified engine for big data processing. Commun.
ACM, 59(11):56–65, Oct. 2016.

