# Statistical Validity and Consistency of Big Data Analytics: A General
Framework

B. Karmakar<EMAIL_ADDRESS>I. Mukhopadhyay<EMAIL_ADDRESS>University of Pennsylvania, PA, USA  Indian Statistical Institute, Kolkata,
India

###### Abstract

Informatics and technological advancements have triggered generation of huge
volume of data with varied complexity in its management and analysis. Big Data
analytics is the practice of revealing hidden aspects of such data and making
inferences from it. Although storage, retrieval and management of Big Data
seem possible through efficient algorithm and system development, concern
about statistical consistency remains to be addressed in view of its specific
characteristics. Since Big Data does not conform to standard analytics, we
need proper modification of the existing statistical theory and tools. Here we
propose, with illustrations, a general statistical framework and an
algorithmic principle for Big Data analytics that ensure statistical accuracy
of the conclusions. The proposed framework has the potential to push forward
advancement of Big Data analytics in the right direction. The partition-
repetition approach proposed here is broad enough to encompass all practical
data analytic problems.

###### keywords:

Big Data, Data mining, Partition-repetition, Statistical inference

##  1 Introduction

‘Big Data’ presents itself with unique challenges in retrieving, storing and
all the way to analysing the data. Technological breakthrough makes generation
and collection of huge volume of data possible in many fields like genetics,
genomics, health care, customer service, informatics, to name a few. Among
various challenges presented by the abundance of data, analysis of data is a
well recognized hurdle. While the explosion of information allows us to know
more about the process, appropriate methods or algorithms are essential to
make correct inference or to reveal hidden pattern.

Recent advancements of technology and targeted methods to Big Data analytics
give access to ample capacity for storing the data along with the skill of
parallel computing. Much effort has been dedicated to extract information from
Big Data in an efficient manner. From a practical standpoint, concern remains
about the validity of results from analysis of Big Data. As attested by many
recent articles, in most cases the inference based on such data is
unacceptable and unreliable. For example, High dimension conventional
classification methods are no better than random guesses [7]. Understanding
the output of Big Data analytics than to fixate on the technical aspect of it
is the most important issue [8, 9, 12], because the future decision making
process depends only on this output. The aim of this article is to put forward
a framework in order to establish the acceptability of the learning from the
Big Data. This framework also fits to the paradigm of parallel computing and
at the same time provides a robust statistical basis for practical
application.

The classical statistical theory of data analysis has its roots in axioms of
probability theory. With growing complexity of Big Data, statistical theory
needs to be revisited [6], mainly due to violation of probabilistic
independence or exchangeability situation. Statistics community has raised
concerns about how the sound and carefully developed theory can help build a
structure around it. In this article we exploit an algorithmic architecture
used in practice to tackle Big Data and suggest an appropriate mathematical
ground for analysis of such architecture.

We propose a partition and repetition approach in a general framework for
statistical analysis of Big Data. This approach expands the horizon of
standard statistical methods as well as opens new avenues for novel methods to
encompass and tackle the challenges arisen due to the specific characteristics
of Big Data. With the help of this general framework, we prove consistency and
accuracy of the analytic results thus obtained. We have explained this theory
through various examples that are usually required in common data analysis
paradigm in respect of many fields. We hope that such a framework would help
in further development of Big Data analytics.

##  2 The divide and conquer algorithm

Abundance of digital information is one way to explain what we today
understand as ‘Big Data’. There are two aspects to the story. Firstly, human
intuition suggests that accuracy of the answer to our question increases if we
have more and more information. This intuition works backward; we start with a
question, try to comprehend what data we might need to answer the question and
then realize that relevant information exists somewhere in digitized format.
The catch is that, this retrospective thought process assumes that the skill
by which human intelligence finds this answer from the data is transferable to
mechanical and algorithmic computing. Secondly, with huge volume of data we
can find a question of interest from the data itself and then get the answer
to the question. But the inherent complexity of available data makes this task
difficult. This whole process is advertised as Big Data analytics.

Principle characteristics of Big Data are its volume, velocity, variety and
complexity [13]. All of them presents as unique challenges at a technical
level of dealing with the data. At the hardware level we have reached a
saturation point on the achievable clock pulse on a single processor. Rather,
the growth in computing capacity is attained by increasing the number of
threaded cores. Moreover, while storage capacity is fairly cheap and scalable,
the RAM is not so. Recognizing this hardware restriction the state of the art
algorithms (Hadoop, Amazon EC2) for Big Data analytics has adopted a
partitioning based method.

However, in view of advancements in computing systems including storage and
processing, need for new data analytic tools are required that are adaptive to
new technologies [16]. Building such statistical tools and algorithms for
monitoring and analysis is needed to achieve success in Big Data analytics.
Hence standard statistical methods should be revisited, modified, and
validated in the light of scalability to extremely large scale data
applications [18].

Fisher et al. [10] have identified the standard workflow of data analysis as,
1) acquiring data, 2) choosing an architecture, 3) shaping the data to the
architecture, 4) writing and editing the code, and 5) reflecting and iterating
on the results. The initial struggle is to adopt a suitable architecture for
the data and map the collected data to that architecture. In this article, we
are not focusing on this domain of analytics job. Rather the focus is on the
later part of analysing the data. To address the problem of huge volume of
data, the way is to partition it into small portions that are manageable by
RAM, process the data in a parallel manner, and finally combine the processed
information to produce the final output. This idea of partitioning has been
used, although in a subtle way, in other areas of research, e.g., data mining
[3, 4], MCMC [22]. An extra benefit of this divide and conquer method is that
such an algorithm easily adapts to the velocity of Big Data. Velocity
contributes to new partitions which are to be analysed and then the inference
is to be combined with the earlier output [19]. Issues relating to variety and
complexity are taken into account by the statistical methods and algorithms
that are used in the analysis (see discussion of Section 4 and References
therein).

##  3 The framework

###  3.1 Sample space structure

Classical theory of statistical analysis is a well developed area with sound
theories. To establish a framework for Big Data analytics we naturally would
like to fall back on those works. To begin with, we consider a sample space
$(\mathcal{S},\mathcal{A}_{\mathcal{S}})$ where $\mathcal{S}$ is the space of
realized values of the data and $\mathcal{A}_{\mathcal{S}}$ is the sigma field
associated with the sample space. We denote by $\mathcal{M}(\mathcal{S})$ the
set of probability measures on $(\mathcal{S},\mathcal{A}_{\mathcal{S}})$. Also
let
$\mathcal{M}^{e}(\mathcal{S})\big{(}\subset\mathcal{M}(\mathcal{S})\big{)}$ be
the set of probability measures with finite support. An observed data
$X_{n\times d}$ can be identified by a probability measure $m_{X}$ on
$(\mathcal{S},\mathcal{A}_{\mathcal{S}})$, with a support having finite
cardinality, defined as follows,

$m_{X}(A)=\sum_{x_{i}\in A,i=1}^{n}\frac{1}{n},$

for any $A\subseteq\mathcal{A}_{\mathcal{S}}$ and $x_{i}\,(i=1,\ldots,n)$ is
the $i$-th data point. To build a theory around it we would require a suitable
metric on the space $\mathcal{M}(\mathcal{S})$. For example, if
$(\mathcal{S},\mathcal{A}_{\mathcal{S}})$ is a polish space then with
Prokhorov metric ($d_{\mathcal{M}}$) we can put weak convergence on
$\mathcal{M}(\mathcal{S})$.

Till this point we have not considered any aspect of Big Data par se. Our aim
is to build the ideology of Big Data analytics on this sample space structure.
Identification of the realized data with an empirical measure on some sample
space gives a broader ground to work on. In a Big Data set up, we hardly have
any control on the generation of data. Thus unlike in classical statistical
theory, where mostly we want to build better experimental designs to apply
statistical methods, be it standard or novel, here we want to construct an
algorithm that would work with the data generation process. This difference in
approaches is subtle but central to how these two ideologies differ.

###  3.2 The problem approach

Main goal of Big Data analytics is to extract information from the data, which
is equivalent to getting information from an element in
$\mathcal{M}^{e}(\mathcal{S})$. So we assume that a satisfactory data
collection and mapping architecture exists. To develop a full framework, we
introduce some definitions about functionality of data analysis. This is
necessary to avoid the cumbersome details and technicalities of a particular
scenario.

Extracted information of a data analysis can be viewed as an element in the
result space ($\mathcal{R}$). A problem approach ($\rho$) is a function from
$\mathcal{M}^{e}(\mathcal{S})$ to $\mathcal{R}$. Based on this formulation of
problem approach we can consider two classes of problem approaches as follows.

##### Definition 1

Inference Problem: If the problem approach $\rho$ can be extended to a
strictly larger subset of $\mathcal{M}(\mathcal{S})$ than
$\mathcal{M}^{e}(\mathcal{S})$, then such a problem or problem approach is
called an inference problem.

##### Definition 2

Mining Problem: If the problem approach $\rho$ can only be defined on
$\mathcal{M}^{e}(\mathcal{S})$, then such a problem or problem approach is
called a mining problem.

The usual examples of these two classes of problems are as follows. Parametric
estimation and testing problems fall under the class of inference problems
where the subset of $\mathcal{M}(\mathcal{S})$ under consideration is
$\mathcal{M}^{e}(\mathcal{S})$ along with the parameter models. Clustering
problem or outlier detection problem, on the other hand, are under the class
of mining problems. In later sections, we shall discuss both these classes of
problem approaches and their solutions in more details.

A technical assumption we need to have is that, one such problem approach is
viable if the map

$\rho:\big{(}\rho^{-1}(\mathcal{R}),d_{\mathcal{M}}\big{)}\longrightarrow\big{(}\mathcal{R},d_{\mathcal{R}}\big{)}$
(1)

is a continuous map, where $d_{\mathcal{M}}$ and $d_{\mathcal{R}}$ are
appropriate metrics on respective spaces. A viable problem approach ($\rho$)
then ensures that the problem is consistent in the number of samples as well
as data points. This means that slight change in the data generation process
($\mathcal{M}(\mathcal{S})$) should not create substantial difference in the
result ($\mathcal{R}$).

###  3.3 Big Data Algorithm

We now discuss various components of our proposed algorithmic structure of Big
Data analytics.

####  3.3.1 Partitioning

A naturally accepted strategy in analysing huge volume of data is to consider
small parts of data at a time. Our formulation for Big Data analytics
formulates this method of partitioning the data as a functional,

$\displaystyle
H_{L}:\mathcal{M}^{e}(\mathcal{S})\longrightarrow\mathcal{M}^{e}(\mathcal{S})\times\cdots\times\mathcal{M}^{e}(\mathcal{S})\;\;\;\;{(L\;many)}$
(2) $\displaystyle H_{L}(m)=(m_{1},m_{2},\ldots,m_{L}),$

such that $(m_{1},m_{2},\ldots,m_{L})$ is related to $m$ by,

$\displaystyle supp(m)=\mathop{\cup}\limits_{i=1}^{L}supp(m_{i});$ (3)
$\displaystyle supp(m_{i})\cap supp(m_{j})=\emptyset,\;\;1\leq i\neq j\leq L.$

where $supp(m)$ denotes the support set of $m$ and $\emptyset$ denotes the
empty set.

For convenience we write
$supp(m_{i})=\big{(}x_{1}^{(i)},x_{2}^{(i)},\ldots,x_{n_{i}}^{(i)}\big{)}$ for
each $i$. For a fixed data $m$ (or $m\equiv X$) we would be given a problem
approach $\rho$. Then the divide and conquer strategy would choose a
partitioning functional $H_{L}$.

But to reduce the error in result due to partitioning, the strategy is to
repeat $K(>1)$ times the partitioning; denote them by
$H_{L,1},H_{L,2},\ldots,H_{L,K}$. This type of algorithm we call as the
partition-repetition algorithm. We now formulate this partition-repetition
algorithm in a comfortable manner.

Let $\mathcal{H}_{L}$ be the set of all partitioning functionals $H_{L}$. A
$\sigma$-field $\mathcal{A}_{\mathcal{H}_{L}}$ can be defined as the smallest
$\sigma$-field on $\mathcal{H}_{L}$ such that the functions $f_{i,j}(\cdot)$
on $\big{(}\mathcal{H}_{L},\mathcal{A}_{\mathcal{H}_{L}}\big{)}$ to
$(\mathcal{S},\mathcal{A}_{\mathcal{S}})$ are measurable for any choice of
$m\in\mathcal{M}^{e}(\mathcal{S})$, where

$f_{i,j}\big{(}H_{L}(m)\big{)}=x_{j}^{(i)}\;\;j=1,2,\ldots,n_{i};\;i=1,2,\ldots,L.$

Then the strategy of analysing data of unmanageable size by partition-
repetition algorithm can be understood as a probability measure $P_{H_{L}}$ on
the measurable space
$\big{(}\mathcal{H}_{L},\mathcal{A}_{\mathcal{H}_{L}}\big{)}$. More precisely
$\\{H_{L,1},H_{L,2},\ldots,H_{L,K}\\}$ would be viewed as a random sample from
the probability measure space
$\big{(}\mathcal{H}_{L},\mathcal{A}_{\mathcal{H}_{L}},P_{H_{L}}\big{)}$. For
simplicity of notation let us denote by $\rho^{L}$ the map,

$\rho^{L}:(m_{1},\ldots,m_{L})\longmapsto(\rho(m_{1}),\ldots,\rho(m_{L}))\;\;{for}\;m_{i}\in\mathcal{M}^{e}(\mathcal{S});\;$

for $i=1,2,\ldots,L$. Then a single random sample $H_{L}$ from the probability
distribution $P_{H_{L}}$ provides us $L$ results
$\rho^{L}\big{(}H_{L}(m)\big{)}$, which are $L$ elements from $\mathcal{R}$.
With a random sample $H_{L,1},H_{L,2},\ldots,H_{L,K}$ from the distribution,
the set of results we get using the problem approach $\rho$ is

$\displaystyle\\{{R}_{k,l}^{*}\\}_{k=1,2,\ldots,K;\;l=1,2,\ldots,L}$
$\displaystyle=\big{\\{}{R}_{k,1}^{*},{R}_{k,2}^{*},\ldots,{R}_{k,L}^{*}\big{\\}}_{k=1,2,\ldots,K}$
$\displaystyle=\big{\\{}\rho^{L}\big{(}H_{L,k}(m)\big{)}\big{\\}}_{k=1,2,\ldots,K}.$

This framework also encompasses the case where rather than partitioning one
chooses to sub-sample. In that case we would get rid of the extra restriction
in equation (3) on the functional $H_{L}$. Popular algorithms of Bootstrap and
Bag-of-Little-Bootstraps (BLB) [15] are covered in this framework.

####  3.3.2 Combining

Next critical part of the algorithm is combining the results obtained above,
$\big{\\{}{R}_{k,l}^{*}\big{\\}}_{k=1,2,\ldots,K;\;l=1,2,\ldots,L}$ in order
to arrive at a final result. Let $C_{KL}$ be the combining map that takes all
the results from the collection and gives the final result. The triplet
$\big{(}\rho,P_{H_{L}},C_{KL}\big{)}$ can be called a solution to a Big Data
problem.

Now it remains to understand the viability of the solution. We have put a
stable condition of continuity in equation (1) on problem approach $\rho$ as a
viable problem approach. Proper behaviour of the pair
$\big{(}P_{H_{L}},C_{KL}\big{)}$ would ensure an accurate solution to the
problem $\rho$ for $m$.

We focus on the case where $C_{KL}:=C^{2}_{K}\circ C^{1}_{L}$ works in two
stages. In the first stage $C^{1}_{L}$ works on each partition ($k$) to
collect the results

${R}_{k}^{*}:=C^{1}_{L}\big{(}\\{{R}_{kl}^{*}\\}_{l=1,2,\ldots,L}\big{)}\;\;\;{for}\;k=1,2,\cdots,K.$

This $K$-tuple is combined by $C^{2}_{K}$. For a fixed data $m$ when
$C^{1}_{L}$ is a measurable map, the randomness of
$\\{H_{L,1},H_{L,2},\ldots,H_{L,K}\\}$ makes the collection
$\\{{R}_{1}^{*},{R}_{2}^{*},\ldots,{R}_{K}^{*}\\}$ an independently and
identically distributed (i.i.d.) sample on the measure space
$\big{(}\mathcal{R},\mathcal{A}_{\mathcal{R}}\big{)}$. This formulation of the
solution $\big{(}\rho,P_{H_{L}},C^{2}_{K}\circ C^{1}_{L}\big{)}$ provides an
opportunity to use rich statistical theory in data analytics.

In the general case, the result space can be quite complicated (we shall give
concrete examples in later section). Rather than dealing with the space
$\mathcal{R}$ itself it would be better to work with real numbers. This is
achieved by an evaluation function
$ev:\mathcal{R}\longrightarrow\mathbb{R}^{N}$ for some fixed $N$ belonging to
the set of natural integers. Then, viability of the choice of $P_{H_{L}}$ can
be understood using the evaluation function of the result space $\mathcal{R}$.
For a given data $m$ and a problem approach $\rho$, we call a partitioning
probability measure $P_{H_{L}}$ to be viable under the first stage combining
operator $C^{1}_{L}$ if,

$\int ev\circ
C^{1}_{L}\big{(}\rho^{L}(H_{L}(m))\big{)}dP_{H_{L}}=ev\circ\rho(m).$ (4)

This condition means that the probability measure $P_{H_{L}}$ and the
combining method $C^{1}_{L}$ are compatible with each other for the problem
$\rho$. If we do infinitely many repetitions of our partition-repetition based
algorithm, the combining method $C^{1}_{L}$ will give equivalent performance
as the one we would have got if we could apply $\rho$ on the data $m$.

The second stage of combining method $C^{2}_{K}$ operates on the collection of
first stage result by combining ${R}_{1}^{*},{R}_{2}^{*},\ldots,{R}_{K}^{*}$
to get the solution

${R}_{K}^{**}:=C^{2}_{K}\big{(}\\{{R}_{k}^{*}\\}_{k=1,2,\ldots,K}\big{)}.$

Now the viability of $C^{2}_{K}$ is based on the comparison of ${R}_{K}^{**}$
with $\rho(m)={R}^{*}$ (say). Here we present the soundness of the algorithm
of partitioning and combining through the following theorem.

###### Theorem 1

For a Big Data solution $\big{(}\rho,P_{H_{L}},C^{2}_{K}\circ
C^{1}_{L}\big{)}$, if $P_{H_{L}}$ is a viable partitioning method under
combining method $C^{1}_{L}$ (i.e., equation (4) is satisfied) and convergence
in $ev$ is equivalent to that of in $\mathcal{R}$, then there exists a second
stage combining method $C^{2}_{K}$, such that
${R}_{K}^{**}\longrightarrow{R}^{*}$ almost surely in $P_{H_{L}}$.

###### Proof 1

Define $C^{2}_{K}$ on
$\mathcal{R}\times\mathcal{R}\times\cdots\times\mathcal{R}$ ($K$ times) as
follows,

$C^{2}_{K}(R_{1},R_{2},\ldots,R_{K}):=\arg\min_{\\{R_{k}\\}_{k=1,2,\ldots,K}}\big{|}\big{|}ev\circ
R_{i}-ev\circ{R}^{*}\big{|}\big{|}.$

Let us use the notations $Y_{k}=ev\circ{R}_{k}^{*}$,
$Z_{K}=ev\circ{R}_{K}^{**}$ and $\mu=ev\circ{R}^{*}$. Since
$\\{{R}_{k}^{*}\\}_{k\geq 1}$ is an i.i.d. sample, by strong law of large
numbers as equation (4) holds, for all $\epsilon>0$ with
$P_{\mathcal{R}}:=P_{H_{L}}\circ C^{1^{-1}}_{L}\circ ev^{-1}$,

$P_{\mathcal{R}}\Big{(}\cup_{k_{0}=1}^{\infty}\cap_{K\geq
k_{0}}\Big{(}\Big{|}\Big{|}\frac{1}{K}\sum_{k=1}^{K}Y_{k}-\mu\Big{|}\Big{|}<\epsilon\Big{)}\Big{)}=0.$

Now using the fact that $||\sum_{k=1}^{K}Y_{k}/K-\mu||\geq||Z_{K}-\mu||$ and
definition of $C_{K}^{2}$, the above holds with $\sum_{k=1}^{K}Y_{k}/K$
replaced by $Z_{K}$. Since convergence in $(\mathcal{R},d_{\mathcal{R}})$ is
equivalent to that in $\big{(}ev\circ\mathcal{R},||\cdot||\big{)}$, rest of
the argument follows as by assumption convergence in
$(\mathcal{R},d_{\mathcal{R}})$ is equivalent to that in
$\big{(}ev\circ\mathcal{R},||\cdot||\big{)}$.

The theorem above deals with the volume aspect of Big Data. It says that even
if the data is unmanageable to be processed practically, we can adopt
partition-repetition approach to get a good solution. It is also not passed
our attention that the number of combination rules may be more than two, but
the final convergence of results requires some more assumptions and strong
theorems in the dependence set up.

Next we also need to answer the question which is more of classical
statistical in nature. If the velocity of the data provides us more and more
information of specific form, is the partition-repetition algorithm able to
extract that information? The following theorem tells us if that is the case,
we would be able to choose a partitioning measure and a sequence of combining
methods that gives the final result.

###### Theorem 2

Let $\\{m_{n}\\}_{n\geq 1}\in\mathcal{M}^{e}(\mathcal{S})$ and $m\in
domain\;of\;\rho$. Suppose the problem approach $\rho$ is viable on its domain
and $m_{n}\longrightarrow m$. If conditions of Theorem 1 hold for the sequence
of solutions $\big{(}\rho,P_{H_{L},n},C^{2}_{K,n}\circ C^{1}_{L,n}\big{)}$,
then there exists a sequence of integers $\\{k_{n}:n\geq 1\\}$ and a
$P_{H_{L}}$ such that, for $n\geq 1$, $P_{H_{L},n}$ is absolutely continuous
with respect to $P_{H_{L}}$ with

$\Big{|}\Big{|}ev\circ C^{2}_{k_{n},n}\circ
C^{1}_{L,n}\big{\\{}\rho^{L}(H_{L,k}(m_{n})\big{)}\big{\\}}_{k=1,2,\ldots,K}-ev\circ\rho(m)\Big{|}\Big{|}\longrightarrow
0,$

as $n\rightarrow\infty$ almost surely in $P_{\mathcal{R}}$.

###### Proof 2

Define $P_{H_{L}}(\cdot)=\sum_{n=1}^{\infty}P_{H_{L},n}(\cdot)/2^{n}$. Let us
denote,

${R}_{K,n}^{**}=C^{2}_{K,n}\circ
C^{1}_{L,n}\Big{(}\big{\\{}\rho^{L}\big{(}H_{L,k}(m_{n})\big{)}\big{\\}}_{k=1,2,\ldots,K}\Big{)}.$

Then for every $\epsilon(>0)$, by Theorem 1 and equation (1) there exists a
sequence $\\{k_{n}(\epsilon):n\geq 1\\}$ and $N\geq 1$ such that for all
$n\geq N$,

$\big{|}\big{|}ev\circ{R}_{k_{n}(\epsilon),n}^{**}-ev\circ\rho(m)\big{|}\big{|}<\frac{\epsilon}{2^{n}},$

almost surely in $P_{\mathcal{R},n}=P_{H_{L},n}\circ C^{1^{-1}}_{L,n}\circ
ev^{-1}$. Choosing $\epsilon$ as rationals, result follows from Cantor’s
diagonal argument.

Both these results are of existential nature rather than being instructive for
practice. Although little abstract in their formulation, these theorems form
the basis of the methods that would be applied in practice. Study on combining
methods is not new to statistics. This framework enforces the importance of
various combining methods along with partitioning methods in the light of Big
Data analytics.

The power of this kind of theory is that we do not put any hard and fast
regularity condition on the data or the data generation process. Theorem 2
only requires that the data collected eventually amounts to some specific
information.

##  4 Illustrative Examples

An analyst’s job and a statistician’s work differ in a crucial way. An analyst
is more concerned with how to extract information from the data available.
This work is referred to as number crunching. A statistician is concerned
about the quality of the extracted information sometimes taking for granted
the effort of extracting the information. In a Big Data scenario where
importance of analyst’s job comes more into the limelight, a statistician
could provide support by accepting some compromise on their ideology. In this
section we illustrate the formulation developed above through some standard
data analytic problems.

We first consider a few problems where the solution $\rho(m_{n})$ can be
calculated without any error from partitioning based algorithm. Here we
specify by subscript $n$ the size of the data. In these examples it is enough
to consider $P_{H_{L}}$ to be some degenerate probability distribution of
convenience and we only require a single sample ($K=1$) from it.

##### Calculating sample mean

Here $P_{H_{L}}$ can be any distribution that partitions the data into
manageable balanced pieces. Then for $\rho(m_{n}):=(\int x\,dm_{n},n)$ the
combining method shall be,

$C_{L}^{1}(\\{(\bar{x}_{i},n_{i})\\}_{i=1,2,\ldots,L})=\Big{(}\frac{\sum_{i}n_{i}\bar{x}_{i}}{\sum_{i}n_{i}},\sum_{i}n_{i}\Big{)}.$

A little tweak in these definitions allows us to calculate many other
descriptive statistics like weighted means, dispersion measures and also some
robust measures for central tendency.

##### Sorting

To get a Big Data solution to the sorting problem we can define a partitioning
$P_{H_{L}}$ as a degenerate distribution such that it divides the data $m_{n}$
into $L$ parts based on a sequence $bound_{0}<bound_{1}<\cdots<bound_{L}$ as,

$bound_{i-1}\leq\\{x_{j}^{(i)}\\}<bound_{i}\;\;for\;i=1,2,\cdots,L.$

The choice of the sequence $\\{bound_{i}\\}$ should be such that the
individual parts are of manageable sizes. With $\rho$ providing us with a
sorted array, the combining stage should simply concatenate the ordered parts,
i.e.,

$C_{L}^{1}(\\{{R}_{l}^{*}\\}_{l=1,2,\ldots,L}):=({R}_{1}^{*},{R}_{2}^{*},\cdots,{R}_{L}^{*}).$

Similar solutions of the above type are obvious for problems like searching,
calculating extreme statistics ($x_{(1)},x_{(n)})$, constructing a histogram
etc. Most of the time these simple problems are only intermediate steps
towards more challenging problems of data analytics.

Some solutions to more standard problems of Big Data analytics are discussed
in brief below. First few examples are inference problems while the later ones
are mining problems. We assume that the data are cleaned and dressed for the
purpose at hand. We avoid discussing the technical aspects of implementing
these algorithms in practice, though in a few examples we shall provide
references to available literature that has more focus on detailed analysis of
the algorithms.

##### Estimation

The problems of modeling (nonparametric, parametric, time series or even
Bayesian) come under the radar of inference problem. Based on the requirements
of the solution (e.g., unbiasedness, minimum variance, consistency) there
would be different Big Data solutions to the problem approach $\rho$. Many of
the times it suffices to consider $P_{H_{L}}$ as a random partitioning measure
of the data, although while considering spatial and/or temporal data more
clever partitioning measure would be required to satisfy viability condition
like equation (4).

Let us consider the problem of finding maximum likelihood estimate (MLE) for a
parameter based on some algorithm (say, EM algorithm or Newton-Raphson or
Fisher’s Scoring etc.). The scenario is that, we have a statistical model in
mind where the number of parameters is fixed. Then partitioning the data
simply breaks the objective function (log-likelihood function) into $L$ parts.
Consequently an intuitive choice of the combining method $C_{KL}$ would be
whichever of the results from partitions maximizes the whole objective
function. Although this method does not ensure the MLE for the data, but in
practice we are hardly concerned about theoretical properties like efficiency;
the estimate found by this method is acceptable.

##### Testing

Consider a test function $\rho$ that provides p-value for testing $H_{0}$
against $H_{1}$. Then based on random partitioning of the data into balanced
parts, a conservative combining algorithm [20] for the corresponding solution
can be

${R}_{k}^{*}:=C_{L}^{1}\big{(}\\{{R}_{lk}^{*}\\}_{l=1,2,\ldots,L}\big{)}=\min_{l=1,2,\ldots,L}{R}_{lk}^{*},\text{for}\;k=1,2,\ldots,K,$

and

${R}^{**}:=C_{K}^{2}\big{(}\\{{R}_{k}^{*}\\}_{k=1,2,\ldots,K}\big{)}=median\\{{R}_{k}^{*}\\}_{k=1,2,\ldots,K}.$

##### Variable Selection

The context in which variable selection problem has been addressed in recent
literature is sometimes too idealistic for Big Data paradigm, although there
are some promising methods. The data generation process is assumed to provide
information on a set of response variables and a fixed set of regressors. We
might be interested in a subset of these variables which have effect on the
responses. The quality of the selected variables can be assessed by
proportions of the variables wrongly selected. In a situation where assumption
of homoscedastic uncorrelated linear model is valid, Barbar and Candes [1]
proposed a method to select variables with a control on the proportion of
falsely discovered variables. This method is no doubt computationally heavy.
The partition-repetition philosophy can be used to adapt this algorithm to
achieve the same goal in current context.

If the data generation process is well controlled, the above inference
problems and solutions make sense. Some recent works are available in the area
of regression [2, 5] focusing on divide and conquer methods. Unfortunately
spurious correlations, noisy data etc. are very common in Big Data
perspective. In that case these naive solutions can be hugely mis-
representative of the actual truth. Data mining problems are more relevant in
such a scenario. In a mining problem we are interested in the data itself
without having to make any modeling assumption. Possible Big Data solutions to
a few mining problems are discussed below.

##### Clustering

An elaborate and critical discussion on clustering problem in view of Big Data
analytics can be found in recent article by the authors [14]. In brief, the
combing method would identify the unique clusters from the set
$\\{{R}_{lk}^{*}\\}_{l=1,2,\ldots,L}$ based on a decision function that tells
us to combine two results when they seem to form a single data cloud. The
second stage is to make stable clusters based on some measure from the $K$
sets of clusterings $\\{{R}_{k}^{*}\\}_{k=1,2,\ldots,K}$.

##### Outliers Detection

Based on a random partitioning measure $P_{H_{L}}$ and a problem approach
$\rho$ that separates the outliers ($m_{n}^{o}$) and the data ($m_{n}^{d}$)
section, (i.e., $\rho(m_{n}):=(m_{n}^{d},m_{n}^{o})$), the combining method
$C_{L}^{1}$ would check the structure of the outliers from the individual
parts and get the outliers from the whole part. The method should check if
outliers from one part belongs to the data section of some other part and also
if outliers from all the parts together form some data section. Second stage
of combining would then pick out the stable outliers from all repetitions.

Ramaswamy et al. [17] discuss another Big Data solution to this mining problem
based on a different partitioning method based on clustering the data and van
Stein et al. [21] propose local subspace-based solution to outlier detection
problem, which applies a combining strategy using global neighbourhoods. These
methods can be viewed as special cases of our proposed framework.

##### Classification

First we consider the $k$-NN classifier, where $\rho$ finds the $k$ nearest
neighbours of a test data point ($x$) as,

$\rho(m_{n}):=((x_{(i)},d(x,x_{(i)}))_{i=1,2,\ldots,k})\;\;$ $\displaystyle
s.t.\;\;d(x,x_{(1)})$ $\displaystyle\leq\cdots\leq d(x,x_{(k)})$
$\displaystyle\leq min\\{d(x,x_{i});x_{i}\in
X\setminus\\{x_{(1)},x_{(2)},\ldots,x_{(k)}\\}\\}.$

Based on any partitioning $P_{H_{L}}$, then the problem is exactly solvable in
a single repetition with a combining operator that picks the $k$ data points
nearest to $x$ among the $L\times k$ points. Subsequently the classifier is
contracted on a second algorithm that simply checks for the maximum number of
representatives in these $k$ data points from each of the classes.

Another celebrated class of classifiers is decision trees. A relevant
combining operator of decision trees based on partition of the data is
proposed by Hall et al. [11].

##  5 Discussion

Data is the lubricant that drives the machinery of statistics. It is no longer
a topic of debate that the way data is generated and collected in modern times
is drastically different from what statisticians are used to deal with.
Statistics should adapt to this change and thereby assist the masses of data
analytic work.

The main contribution of this article is suggesting a basis of statistical
theory for present day data analytic works. In composing the theory we have
tried to stay true to the practical nature of a data science job. This
formulation proposes a divide and conquer algorithm (either partition-
repetition or subsampling method). More importantly it respects the fact that
more often than not we have no control on the data generation process. We have
also tried to encompass all possible data analytic problems. A range of such
data analytic problems are discussed in perspective of our formulation.

Successful use of statistical theory in data analysis would require
understanding the field of ‘Big Data’. Rather than being insistent on
developing methods and elaborate theories based on idealistic assumptions, we
have kept their applicability in mind. Our proposed framework encompasses
statistical analyses of majority of problems in view of complex
characteristics of Big Data and can be extended further keeping its
compatibility with modern advances in computational world.

## References

## References

  * [1] R.F. Barber, E. Candes, Controlling the false discovery rate via knockoffs, The Annals of Statistics 43(5) (2015) 2055–2085. doi:10.1214/15-AOS1337.
  * [2] H. Battey, F. Fan, H. Liu, J. Lu, Z. Zhu, Distributed estimation and inference with statistical guarantees, arXiv preprint, 2015. arXiv:1509.05457v1.
  * [3] G. Buehrer, R.L. de Oliveira, D. Fuhry, S. Parthasarathy, Towards a parameter-free and parallel itemset mining algorithm in linearithmic time, 2015 IEEE 31st International Conference on Data Engineering, Seoul (2015) 1071–1082. doi:10.1109/ICDE.2015.7113357.
  * [4] T. Calders, C. Garboni, B. Goethals, Efficient pattern mining of uncertain data with sampling, in: M.J. Zaki, J.X. Yu, B. Ravindran, V. Pudi, (Eds.) PAKDD 2010, Part I. LNCS (LNAI), 6118, Springer, Heidelberg, 2010, pp. 480–487. doi:10.1007/978-3-642-13657-3_51.
  * [5] X. Chen, M. Xie, A split-and-conquer approach for analysis of extraordinarily large data, Statistica Sinica 24 (2014) 1655–1684. doi:10.5705/ss.2013.088.
  * [6] M. Davidian, Aren’t we data science, Amstat News, (2013) 433-435.
  * [7] J. Fan, Y. Fan, High dimensional classification using features annealed independence rules, The Annals of Statistics 36 (2008) 2605–2637. doi:10.1214/07-AOS504.
  * [8] J. Fan, H. Fang, L. Han, Challenges of big data analysis, National Science Review 1(2) (2014) 293–314. https://doi.org/10.1093/nsr/nwt032.
  * [9] J. Fan, Q.M. Shao, W.X. Zhou, Are discoveries spurious? Distributions of maximum spurious correlations and their applications, arXiv preprint, 2015. arXiv:1502.04237.
  * [10] D. Fisher, R. DeLine, M. Czerwinski, S. Drucker, Interactions with big data analytics, Interactions with Big Data Analysis 19(3) (2012) 50–59. doi:10.1145/2168931.2168943.
  * [11] L. Hall, N. Chawla, K.W. Bowyer, Combining decision trees learned in parallel, in: Working Notes of the KDD-97 Workshop on Distributed Data Mining, 1998, pp. 10–15.
  * [12] J.P. Huang, Big data need physical ideas and methods, arXiv preprint, 2014. arXiv:1412.6848.
  * [13] A. Katal, M. Wazid, R.H. Goudar, Big data: Issues, challenges, tools and good practices, in: 2013 Sixth International Conference on Contemporary Computing (IC3), 2013, pp. 404–409. doi:10.1109/IC3.2013.6612229
  * [14] B. Karmakar, I. Mukhopadhyay, An efficient partition – repetition approach in clustering of big data, in: S. Pyne, B.L.S. Prakasa Rao, S.B. Rao (Eds.), Big data analytics: Methods and applications, Springer India, New Delhi, 2016, pp. 75–93. doi:10.1007/978-81-322-3628-3_5.
  * [15] A. Kleiner, A. Talwalkar, P. Sarkar, M.I. Jordan, A scalable bootstrap for massive data, J. R. Stat. Soc. Ser. B. Stat. Methodol. 76 (2014) 795–816. doi:10.1111/rssb.12050.
  * [16] D. Petcu, et al., On processing extreme data, Scalable Computing: Practice and Experience 16(4) (2015) 467–489.
  * [17] S. Ramaswamy, R. Rastogi, K. Shim, Efficient algorithms for mining outliers from large data sets, SIGMOD Rec. 29(2) (2000) 427–438. doi:10.1145/335191.335437.
  * [18] D.A. Reed, J. Dongarra, Exascale computing and big data, Communications of the ACM 58(7) (2015) 56–68. doi:10.1145/2699414.
  * [19] E.D. Schifano, J. Wu, C. Wang, J. Yan, M.H. Chen, Online updating of statistical inference in the Big Data setting, arXiv preprint, 2015. arXiv:1505.06354.
  * [20] L.H.C. Tippett, The methods of statistics, Williams & Norgate, London, 1931.
  * [21] B. van Stein, M. van Leeuwen, B. Bäck, Local subspace-based outlier detection using global neighbourhoods, arXiv preprint, 2016. arXiv:1611.00183v1.
  * [22] X. Wang, F. Guo, K.A. Heller, D.B. Bunson, Parallelizing MCMC with random partition trees, Advances in Neural Information Processing Systems, (2015) 451–459.
  * [23] T. Zhao, G. Cheng, H. Liu, A partially linear framework for massive heterogeneous data, The Annals of Statistics 44(4) (2016) 1400–1437. doi:10.1214/15-AOS1410.