text:
\subsection{Accounting for cell-cycle dependent variability in gene dosage}
\label{sec_cell_cycle}

As cells progress through the cell cycle, the genome has to be replicated to
guarantee that each daughter cell receives a copy of the genetic material. As
replication of the genome can take longer than the total cell cycle, this
implies that cells spend part of the cell cycle with multiple copies of each
gene depending on the cellular growth rate and the relative position of the
gene with respect to the replication origin \cite{Bremer1996}. Genes closer to
the replication origin spend a larger fraction of the cell cycle with multiple
copies compared to genes closer to the replication termination site
\cite{Bremer1996}. \fref{fig3_cell_cycle}(A) depicts a schematic of this
process where the replication origin ({\it oriC}) and the relevant locus for
our experimental measurements ({\it galK}) are highlighted.

Since this change in gene copy number has been shown to have an effect on
cell-to-cell variability in gene expression \cite{Jones2014a, Peterson2015}, we
now extend our minimal model to account for these changes in gene copy number
during the cell cycle.  We reason that the only difference between the
single-copy state and the two-copy state of the promoter is a doubling of the
mRNA production rate $r_m$. In particular, the promoter activation and
inactivation rates $\kpon$ and $\kpoff$ and the mRNA production rate $r_m$
inferred in \secref{sec_model} assume that cells spend a fraction $f$ of the
cell cycle  with one copy of the promoter (mRNA production rate $r_m$) and a
fraction $(1-f)$ of the cell cycle with two copies of the promoter (mRNA
production rate $2 r_m$). This inference was performed considering that at each
cell state the mRNA level immediately reaches the steady state value for the
corresponding mRNA production rate. This assumption is justified since the
timescale to reach this steady state depends only on the degradation rate
$\gm$, which for the mRNA  is much shorter ($\approx 3$ min) than the length of
the cell cycle ($\approx$ 60 min for our experimental conditions)
\cite{Dong1995}. \siref{supp_param_inference} shows that a model accounting for
this gene copy number variability is able to capture data from single molecule
mRNA counts of an unregulated (constitutively expressed) promoter.

Given that the protein degradation rate $\gp$ in our model is set by the cell
division time, we do not expect that the protein count will reach the
corresponding steady state value for each stage in the cell cycle. In other
words, cells do not spend long enough with two copies of the promoter for the
protein level to reach the steady state value corresponding to a transcription
rate of $2 r_m$. We therefore use the dynamical equations developed in
\secref{sec_moments} to numerically integrate the time trajectory of the
moments of the distribution with the corresponding parameters for each phase of
the cell cycle. \fref{fig3_cell_cycle}(B) shows an example corresponding to the
mean mRNA level (upper panel) and the mean protein level (lower panel) for the
case of the unregulated promoter. Given that we inferred the promoter rate
parameters considering that mRNA reaches steady state in each stage, we see
that the numerical integration of the equations is consistent with the
assumption of having the mRNA reach a stable value in each stage (See
\fref{fig3_cell_cycle}(B) upper panel). On the other hand, the mean protein
level does not reach a steady state at either of the cellular stages.
Nevertheless it is notable that after several cell cycles the trajectory from
cycle to cycle follows a repetitive pattern (See \fref{fig3_cell_cycle}(B)
lower panel). Previously we have experimentally observed this repetitive
pattern by tracking the expression level over time with video microscopy as
observed in Fig. 18 of \cite{Phillips2019}.

To test the effects of including this gene copy number variability in our model
we now compare the predictions of the model with experimental data. As detailed
in the Methods section, we obtained single-cell fluorescence values of different
{\it E. coli} strains carrying a YFP gene under the control of the LacI
repressor. Each strain was exposed to twelve different input inducer (IPTG)
concentrations for $\approx 8$ generations for cells to adapt to the media. The
strains imaged spanned three orders of magnitude in repressor copy number and
three distinct repressor-DNA affinities. Since growth was asynchronous, we
reason that cells were randomly sampled at all stages of the cell cycle.
Therefore, when computing statistics from the data such as the mean fluorescence
value, in reality we are averaging over the cell cycle. In other words, as
depicted in \fref{fig3_cell_cycle}(B), quantities such as the mean protein copy
number change over time, i.e. $\ee{p} \equiv \ee{p(t)}$. This means that
computing the mean of a population of unsynchronized cells is equivalent to
averaging this time-dependent mean protein copy number over the span of the cell
cycle. Mathematically this is expressed as
\begin{equation}
	\ee{p}_c = \int_{t_o}^{t_d} \ee{p(t)} P(t) dt,
	\label{eq_time_avg}
\end{equation}
where $\ee{p(t)}$ represents the first moment of the protein distribution as
computed from \eref{eq_gral_mom}, $\ee{p}_c$ represents the average protein
copy number over a cell cycle, $t_o$ represents the start of the cell cycle,
$t_d$ represents the time of cell division, and $P(t)$ represents the
probability of any cell being at time $t \in [t_o, t_d]$ of their cell cycle.
We do not consider cells uniformly distributed along the cell cycle since it is
known that cells age is exponentially distributed, having more younger than
older cells at any point in time \cite{Powell1956} (See
\siref{supp_cell_age_dist} for further details). All computations hereafter are
therefore done by applying an average like that in \eref{eq_time_avg} for the
span of a cell cycle. We remind the reader that these time averages are done
under a fixed environmental state. It is the trajectory of cells over cell
cycles under a constant environment that we need to account for. It is through
this averaging over the span of a cell cycle that we turn a periodic process as
the one shown in \fref{fig3_cell_cycle}(B) into a stationary process that we can
compare with experimental data and, as we will see later, use to reconstruct the
steady state gene expression distribution.

\fref{fig3_cell_cycle}(C) compares zero-parameter fit predictions (lines) with
experimentally determined quantities (points). The upper row shows the
non-dimensional quantity known as the fold-change in gene expression
\cite{Garcia2011c}. This fold-change is defined as the relative mean gene
expression level with respect to an unregulated promoter. For protein this is
\begin{equation}
	\foldchange = {\ee{p(R > 0)}_c \over \ee{p(R = 0)}_c},
\end{equation}
where $\ee{p(R > 0)}_c$ represents the mean protein count for cells with
non-zero repressor copy number count $R$ over the entire cell cycle, and
$\ee{p(R = 0)}_c$ represents the equivalent for a strain with no repressors
present. The experimental points were determined from the YFP fluorescent
intensities of cells with varying repressor copy number and a $\Delta lacI$
strain with no repressor gene present (See Methods for further details). The
fold-change in gene expression has previously served as a metric to test the
validity of equilibrium-based models \cite{Phillips2015}. We note that the
curves shown in the upper panel of \fref{fig3_cell_cycle}(C) are consistent
with the predictions from equilibrium models \cite{Razo-Mejia2018} despite
being generated from a clearly non-equilibrium process as shown in
\fref{fig3_cell_cycle}(B). The kinetic model from \fref{fig2_minimal_model}(A)
goes beyond the equilibrium picture to generate predictions for moments of the
distribution other than the mean mRNA or mean protein count. To test this
extended predictive power the lower row of \fref{fig3_cell_cycle}(C) shows the
noise in gene expression defined as the standard deviation over the mean
protein count, accounting for the changes in gene dosage during the cell cycle.
Although our model systematically underestimates the noise in gene expression,
the zero-parameter fits capture the scaling of this noise. Possible origins of
this systematic discrepancy could be the intrinsic cell-to-cell variability of
rate parameters given the variability in the molecular components of the central
dogma machinery \cite{Jones2014a}, or noise generated by irreversible
non-equilibrium reactions not explicitly taken into account in our minimal model
\cite{Grah2020}.  The large errors for the highly repressed strains (lower left
panel in \fref{fig3_cell_cycle}(C)) are a result of having a small number in the
denominator - mean fluorescence level - when computing the noise. Although the
model is still highly informative about the physical nature of how cells
regulate their gene expression, the lack of exact numerical agreement between
theory and data opens an opportunity to gain new insights into the biophysical
origin of cell-to-cell variability. In \siref{supp_empirical} we explore
empirical ways to account for this systematic deviation. We direct the reader to
\siref{supp_multi_gene} where equivalent predictions are done ignoring the
changes in gene dosage due to the replication of the genome.

\begin{figure}[h!]
	\centering \includegraphics
  {./fig/main/fig3_cell_cycle_moments.pdf}
	\caption{\textbf{Accounting for gene copy number variability during the
	cell cycle.} (A) Schematic of a replicating bacterial genome. As cells
	progress through the cell cycle the genome is replicated, duplicating gene
	copies for a fraction of the cell cycle before the cell divides. {\it oriC}
	indicates the replication origin, and {\it galK} indicates the locus at
	which the YFP reporter construct was integrated. (B) mean (solid line)
	$\pm$ standard deviation (shaded region) for the mRNA (upper panel) and
	protein (lower panel) dynamics. Cells spend a fraction of the cell cycle
	with a single copy of the promoter (light brown) and the rest of the cell
	cycle with two copies (light yellow). Black arrows indicate time of cell
	division. (C) Zero parameter-fit predictions (lines) and experimental data
	(circles) of the gene expression fold-change (upper row) and noise (lower
	row) for repressor binding sites with different affinities (different
	columns) and different repressor copy numbers per cell (different lines on
	each panel). Error bars in data represent the 95\% confidence interval on
	the quantities as computed from 10,000 bootstrap estimates generated from
	$> 500$ single-cell fluorescence measurements. In the theory curves, dotted
	lines indicate plot in linear scale to include zero, while solid lines
	indicate logarithmic scale. For visual clarity, data points in the noise
	panel with exceptionally large values coming from highly repressed strains
	are plotted on a separate panel.}
	\label{fig3_cell_cycle}
\end{figure}


text:
\chapter{Introduction}

The universe must be self-consistent. This is the basic premise physicists assume in the quest for the ultimate laws that govern our universe. Without it, a theory would be a mere description of a collection of observed facts.

Despite highly precise experimental corroboration of the Standard Model of particle physics, which relies on Quantum Field Theory (QFT) with gauge symmetry, and Einstein's General Relativity (GR) that describes gravity, these two frameworks are mutually incompatible. That is without mentioning the foundational problems of QFT, that the Clay Mathematics Institute urges to solve with a million-dollar prize incentive\footnote{
See the link: \url{http://www.claymath.org/millennium-problems/yang\%E2\%80\%93mills-and-mass-gap}
}.

Classical physics is elegantly formulated in terms of the least action principle.
The standard procedure is to encode the dynamics in a quantity called action,
minimize it with respect to the physical variables which gives a set of differential equations (of motion) to be solved.
In quantum physics, we relax this principle. When quantizing a classical theory in Feynman path integral formulation,
paths that do not minimize the action also contribute to the dynamics. In strong analogy with statistics,
physical quantities are weighted observables $O$ by the exponential of the classical action\footnote{
The analogy is even closer when we analytically continue the time to pure imaginary time, i.e. Wick rotate $t \rightarrow -i t_{E}$,
then the action becomes purely imaginary, and the exponential decays.}:
\[
 \braket{O} = \int D\phi \, O\, e^{-i S[\phi]/\hbar},
\]
where we used the shorthand notation $\phi$ for the collection of quantum fields\footnote{
Quantum mechanics can be formulated as a (0+1)-dimensional QFT.}.
The problem is, however, the lack of a rigorous definition of the measure $D\phi$.
Very often, we only know how to compute quantum observables in certain limits,
when we can rely on the saddle-point approximation to the integral.
For example, in the classical limit (vanishing Plank constant $\hbar$),
the saddle-point method for the partition function gives us the least action principle:
\[
 Z=\braket{1} \approx e^{-i S[\phi_c]/\hbar}; \quad  \delta S[\phi_c] = 0 .
\]
Other examples are the weak coupling limit, such as in Quantum Electrodynamics (QED),
or the thermodynamic limit in quantum many-body systems.
By contrast, we have no established analytical tool to handle strongly-coupled QFTs,
which would explain quark confinement in Quantum Chromodynamics (QCD), and phases of high-Tc superconductors.

Only very few classes of path integrals are solvable.
Besides free theories, path integrals of topological quantum field theories and some supersymmetric theories localize \emph{exactly}
at their saddle-points. This highly non-trivial phenomenon is called the localization of path integrals,
and it is one of the pillars our work is based on.

Generalizing point-particles to strings,
String Theory might be the best candidate for a consistent quantum gravity theory,
which would be a unifying framework for QFT and GR. It is not free of mathematical problems though,
for example the string action in a curved background is not fully known,
and path integral measures are not rigorously defined either. Nevertheless, it is mathematically rich,
with a web of dualities that connect different perturbative string theories (the underlying theory is known as the M-theory).
It is offering us many insights otherwise unsuspected and a very important realization is the AdS/CFT correspondence.
The most well-studied instance of the correspondence is the one between weakly-coupled superstring theory living on $AdS_5 \times S^5$ space,
and a strongly-coupled supersymmetric conformal field theory (CFT) called $\mathcal{N}=4$  SYM.
Despite much success (and still some issues concerning quantum stringy corrections), the correspondence remains an unproven conjecture.

An even more general correspondence is the gauge/string (or gauge/gravity) duality,
also known as the holographic principle (so named because the gauge theory lives in a lower dimensional space than the string theory).
If it were true, it would be revolutionary in many aspects. From a practical point of view,
on one hand we would have a toolbox to solve strongly-coupled gauge theories using essentially GR,
and on the other hand, experiments on quantum gravity could be done in laboratories by handling systems like cold atoms.
From a conceptual point of view, it could indicate that gravity, and hence spacetime, are emergent from lower dimensional quantum systems.

We lack the mathematical constructs to even formulate the conjecture in a precise manner.
However, we can generalize what we learned from AdS/CFT to settings where we still hold some analytical control.
A perfect toy model to investigate \emph{non-conformal} gauge/string duality is the unique massive deformation of $\mathcal{N}=4$ SYM,
called $\mathcal{N}=2^*$ SYM.
On one hand, like $\mathcal{N}=4$ SYM, supersymmetric localization is applicable
and reduces the complicated path integrals to a manageable matrix model,
allowing us to access its strongly-coupled regime (actually any finite coupling regime).
On the other hand, $\mathcal{N}=2^*$ SYM
is conjectured to be dual to a supergravity solution known as the Pilch-Warner background.
Figure \ref{fig:Overview} shows a graph on the relationship between different theories that we consider.
% Therefore, it is a golden opportunity to test the gauge/string duality beyond AdS/CFT,
% and perhaps learn more about the string theory side through this duality.

\begin{figure}[t]
\begin{center}
\includegraphics[width=\textwidth]{Images/Overview.pdf}
\end{center}
\caption{\label{fig:Overview} Localization applies to theories on the sphere, indicated by a dashed box.
Since the gravity dual of $\mathcal{N}=2^*$ on $S^4$ is only partially known (indicated by the dotted line arrow),
we take the decompactification limit ($R \rightarrow \infty$) to obtain $\mathcal{N}=2^*$ on $\mathbb{R}^4$.
Our research focuses on the dashed arrow,
which generalizes the well-established AdS/CFT correspondence shown in the dashed box below it.
The limits will be explained through out the thesis.
%  in the 't Hooft limit ($N\rightarrow \infty$ and $\lambda \rightarrow \infty$),
}
\end{figure}

\subsection*{Outline}
This thesis has two parts, both aimed at introducing and reviewing some background material in order to help the readers follow the appended papers.
Part I focuses on the gauge theory side. We start off with the basics of the supersymmetric localization technique,
then we go on to discuss the action of $\mathcal{N}=4$ SYM on $\mathbb{R}^4$ and on $S^4$.
We then extend it to $\mathcal{N}=2^*$ SYM on $S^4$, and focus on the partition function after localization.
We show the common technique to solve a matrix model, and conclude with the phase diagram of the theory.
The last chapter of this part introduces the Wilson loop observables, and we review some known results in $\mathcal{N}=4$ case,
and finally, write down the results we computed for $\mathcal{N}=2^*$ case.
Part II starts with supergravity and some of its solutions,
including $AdS_5\times S^5$ and Pilch-Warner.
Then, we review the AdS/CFT correspondence and the logic behind its original derivation. In the end, we talk about holographic Wilson loops and connect our holographic solutions to the gauge theory results.

\begin{quote}
 \emph{Physics is really nothing more than a search for ultimate simplicity, but so far all we have is a kind of elegant messiness.}
   ---  Bill Bryson
%  , \emph{A Short History of Nearly Everything}
\end{quote}

ext: tex

max_stars_repo_name: yixinyi/PhDThesis

max_issues_repo_name: yixinyi/PhDThesis

max_forks_repo_name: yixinyi/PhDThesis


text:
This section is dedicated to exploring various mechanisms and communication protocols used in embedded devices for working with peripheral devices.

\subsection{GPIO}
General-Purpose Input/Output, abbreviated as GPIO, is one of the most basic means of communication between a micro-controller and a peripheral device that is connected to it.

General-purpose Input/Output pins have no predetermined usage. As such, various aspects of a GPIO pin may be configured:\cite{giometti2017gnu}
\begin{itemize}
    \item Enabled or disabled
    \item Used as input or output
    \item Read or write output value
    \item Read input value
    \item Set value as pulled-up or pulled-down by default
\end{itemize}

In fact, the GPIO pins are generic enough that they may be used to emulate another digital interface controller. Other than emulating, GPIO pins may be used for signal control (reset, power enable, suspend), managing relays, LEDS, switches, and buttons.\cite{giometti2017gnu}

\subsection{UART}

\subsection{I2C}

\subsection{SPI}

max_stars_repo_name: knejadfard/rkern

max_issues_repo_name: knejadfard/rkern

max_forks_repo_name: knejadfard/research-kernel


text:
%!TEX root = manual.tex
%
\chapter{A complete example}
\label{ch:example}

This chapter gives a complete example of a simple calculator
language implemented using both \texttt{ml-ulex} and \texttt{ml-antlr}.
The language has the following syntax:
\begin{displaymath}
  \begin{array}{rcl}
    E & ::=  & \mathtt{let}\;\mathrm{id}\;\mathtt{in}\;E \\
      & \mid & E \;\mathtt{+}\; E \\
      & \mid & E \;\mathtt{*}\; E \\
      & \mid & \mathtt{-}\;E \\
      & \mid & \mathrm{id} \\
      & \mid & \mathrm{num}
  \end{array}%
\end{displaymath}%
The lexical conventions allow arbitrary whitespace between tokens.
Numbers ($\mathrm{num}$) numbers are unsigned decimal numbers
and identifiers ($\mathrm{id}$) begin with a letter followed by letters and digits.
The expression forms are listed in order of increasing precedence:
let-expressions have the lowest precedence; then addition, multiplication, and negation.
The calculator will compute and return the value of the expression.

Figure~\ref{fig:calc-sources} gives the CM file for the project.
%Note that we are assuming that the \texttt{ml-ulex} and \texttt{ml-antlr} tools have been run by hand.
\begin{figure}[h]
\begin{lstlisting}[language=CM]
Library

  structure CalcLexer
  functor CalcParseFn
  structure CalcTest

is
  $/basis.cm
  $/smlnj-lib.cm
  $/ml-lpt-lib.cm

  calc.grm : ml-antlr
  calc.lex : ml-ulex
  calc-test.sml
\end{lstlisting}%
\caption{The CM file: {\tt sources.cm}}
\label{fig:calc-sources}
\end{figure}%

\begin{figure}

\begin{lstlisting}[language=MLULex]
%name CalcLexer;

%let digit = [0-9];
%let int = {digit}+;
%let alpha = [a-zA-Z];
%let id = {alpha}({alpha} | {digit})*;

%defs (
  structure T = CalcTokens
  type lex_result = T.token
  fun eof() = T.EOF
);

let     => ( T.KW_let );
in      => ( T.KW_in );
{id}    => ( T.ID yytext );
{int}   => ( T.NUM (valOf (Int.fromString yytext)) );
"="     => ( T.EQ );
"+"     => ( T.PLUS );
"-"     => ( T.MINUS );
"*"     => ( T.TIMES );
"("     => ( T.LP );
")"     => ( T.RP );
" " | \n | \t
        => ( continue() );
.       => ( (* handle error *) );
\end{lstlisting}
\caption{The ml-ulex specification: \texttt{calc.lex}}
\label{fig:calc-lex}
\end{figure}%

\begin{figure}[p]
\begin{lstlisting}[language=SML]
%name Calc;

%tokens
  : KW_let  ("let")  | KW_in   ("in")
  | ID of string     | NUM of Int.int
  | EQ      ("=")    | PLUS    ("+")
  | TIMES   ("*")    | MINUS   ("-")
  | LP      ("(")    | RP      (")")
  ;

exp(env)
  : "let" ID "=" exp@(env)
    "in" exp@(AtomMap.insert(env, Atom.atom ID, exp1))
      => ( exp2 )
  | addExp@(env)
  ;

addExp(env)
  : multExp@(env) ("+" multExp@(env))*
      => ( List.foldr op+ 0 (multExp::SR) )
  ;

multExp(env)
  : prefixExp@(env) ("*" prefixExp@(env))*
      => ( List.foldr op* 1 (prefixExp::SR) )
  ;

prefixExp(env)
  : atomicExp@(env)
  | "-" prefixExp@(env)
      => ( ~prefixExp )
  ;

atomicExp(env)
  : ID
      => ( valOf(AtomMap.find (env, Atom.atom ID)) )
  | NUM
  | "(" exp@(env) ")"
  ;
\end{lstlisting}
\caption{The ml-antlr specification: \texttt{calc.grm}}
\label{fig:calc-grm}
\end{figure}%

\begin{figure}
\begin{lstlisting}[language=SML]
structure CalcTest =
  struct

    structure CP = CalcParseFn(CalcLexer)

    fun tok2s (ID s) = s
      | tok2s (NUM n) = Int.toString n
      | tok2s tok = CalcTokens.toString tok

  (* val calc : TextIO.instream -> Int.int *)
    fun calc instrm = let
      val sm = AntlrStreamPos.mkSourcemap()
      val lex = CalcLexer.lex sm
      val strm = CalcLexer.streamifyInstream instrm
      val (r, strm', errs) = CP.parse lex AtomMap.empty strm
      in
        print (String.concatWith "\n"
            (List.map (AntlrRepair.repairToString tok2s sm)
                 errs));
        r
      end

  end
\end{lstlisting}
\caption{The driver: {\tt calc-test.sml}}
\label{fig:calc-test}
\end{figure}%


text:
\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{geometry}
\usepackage{enumerate}
\usepackage{natbib}
\usepackage{float}%稳定图片位置
\usepackage{graphicx}%画图
\usepackage[english]{babel}
\usepackage{a4wide}
\usepackage{indentfirst}%缩进
\usepackage{enumerate}%加序号
\usepackage{multirow}%合并行
\title{\large UM-SJTU JOINT INSTITUTE\\Advanced Lasers and Optics Laboratory\\(VE438)\\\ \\\ \\\ \\\ \\\ \\\ \\\ \\\ \\\ \\\ \\\
Pre Lab Assignment\\\ \\\ LAB 5\\\ Spectrometer \\\ \\\ \\\ \\\ \\\ }
\author{Name: Pan Chongdan \\ID: 516370910121}
\date{Date: \today}

\begin{document}
\maketitle
\newpage
\section{Answers for Pre Lab Questions}
\subsection{Question 1}
\begin{figure}[H]
\centering
\includegraphics[scale=0.3]{P1.png}
\end{figure}
The is a schematic spectrometer called FGY-01. The light can pass into the spectrometer through part 2, which is a slit. Part 1 is the parallel collimator, which can product parallel light after it pass through the slit.Part 6 and part 8 are lens that can have the parallel focused on part 11 is reticle with a rectangle prism which can produce light of different color by dispersion effect. Then we can observe the result from part 7. User can also put other things on the rest parts to observe their behaviour.
\subsection{Question 2}
The periodicity of grating is the distance between the places where the refractive index has one change and another change. The smaller the period of the grating is smaller, light will form a different patter at a high frequency, which means the spreading angle is smaller.
\par The parallel light produced from collimator can have diffraction through the grating. The relationship can be expressed as $d(\sin\theta\pm\sin i)=m\lambda$ where $i$ is the incident angle and $\theta$ is the diffraction angle, $m$ is the order and $d$ is the period.
\subsection{Question 3}
For zero-mode grating, according to the equation above, all the diffraction angles for light of different color are same and they can't be split up so we should use the first-order grating so that there is diffraction patterns can be separated.
\end{document}

max_stars_repo_name: PANDApcd/Physics

max_issues_repo_name: PANDApcd/Physics

max_forks_repo_name: PANDApcd/Physics


text:
\chapter{Cassandra}\label{ch:cassandra}

\section{Overview}

Apache Cassandra is a Java-based NoSQL database management system. It contains the command-line interface CQL for Cassandra database commands instead of SQL. It has to be recognized that the supported Java version by the open-source project Apache Cassandra is able to be changed with every version.
That has to be considered during the integration into the \gls{CI/CD} pipeline of the project. There are different multi-arch Dockerfiles for all versions of AdoptOpenJDK for public usage. These can be applied for the base Cassandra image. Afterwards, a multi-arch Docker image for Cassandra, which includes the s390x architecture, can be published.
A \ref{monitoring} "nagios monitoring check" - usable for containerized environments - is chosen for tests. This one has to be assimilated in the setup. \\
This Apache project is using CircleCI for Continuous Integration.

\section{Installation}\label{Cassandra-Installation}

A Dockerfile\footnote{\url{https://github.com/s390x-container-samples/s390x-cassandra-ci-cd/blob/master/Dockerfile}} for a multi-arch image should be created in this project with the reason for using it for multiple architectures in the future.
Apache Cassandra is a Java-based application. Therefore, the research has contained the search for a multi-arch image with pre-installed Java. The Cassandra version 3.11.6 is supporting Java 8.
AdoptOpenJDK is maintaining multi-arch images for different Linux distributions with pre-installed AdoptOpenJDK.
In the description of \ref{AdoptOpenJDK-Multi-Arch} "Multi-Arch Image AdoptOpenJDK 8" is explained how the recommended Java version will be chosen for the specific architecture in this base image.
This base image is integrated with \lstinline!FROM adoptopenjdk:8-jdk-hotspot! on top of the Dockerfile.

Apache Cassandra will be cloned from the Github repository with \\
\lstinline!git clone https://github.com/apache/cassandra.git!. \\
The selected version is set with an argument with the ARG variable. On this way, it is possible to check out other versions with a given argument as \lstinline!--build-arg CASSANDRA_VERSION=3.12.4! in the docker build command. \\
Apache Cassandra is using JNA (Java Native Library)\footnote{\url{https://github.com/java-native-access/jna}} as an extension of Java. JNA provides Java programs easy access to native shared libraries for improved communication with the database system. The ant command is building the application and the JNA subsequently. \\
The command \lstinline!sed -i ' s/Xss256k/Xss32m/'! is setting the size of the frame stack (JVM stack) used by each thread to store local variables. This frame size is reduced to a minimum and stored in both files build.xml and conf/jvm.options.
A soft link (\textbf{ln -s}) will be created to save space in the container. Such a soft link refers to a symbolic path of another file or directory. Following, all files inside of the build directory \path{/root/cassandra} are additionally available under \path{/usr/share/cassandra}. Another benefit is the fast creation of a soft link in comparison to a copy / move command.
\begin{figure}[H]
\centering
\begin{boxedverbatim}
FROM adoptopenjdk:8-jdk-hotspot
ARG CASSANDRA_VERSION=3.11.6
git clone https://github.com/java-native-access/jna.git \
&& cd jna \
&& git checkout 4.2.2 \
&& ant native jar \
# Build and install Apache Cassandra
&& cd $SOURCE_ROOT \
&& git clone https://github.com/apache/cassandra.git \
&& cd cassandra \
&& git checkout cassandra-${CASSANDRA_VERSION} \
&& sed -i ' s/Xss256k/Xss32m/' build.xml conf/jvm.options \
&& ant \
&& rm lib/snappy-java-1.1.1.7.jar \
&& wget -O lib/snappy-java-1.1.2.6.jar https://repo1.maven.org/maven2/org/xerial/snappy/
snappy-java/1.1.2.6/snappy-java-1.1.2.6.jar \
&& rm lib/jna-4.2.2.jar \
&& ln -s $SOURCE_ROOT/cassandra /usr/share/cassandra \
&& rm -rf  $SOURCE_ROOT/jna $SOURCE_ROOT/*.tar.gz  \
&& rm -rf /usr/share/cassandra/test \
\end{boxedverbatim}
 \caption{Cassandra Installation}
    \label{CassandraInstallation}
\end{figure}

Cassandra can be started with \lstinline!CMD ["cassandra", "-R", "-f"]! with \textbf{f} for force and \textbf{R} so start the service as root after setting the environment variables with inside of the Docker container.

\section{Java Optimization}

Apache Cassandra should be allowed to use all available memory of the minimal system effectively.
Default the JVM is configured that only a part of that can be used. These configurations are set in the Java Options.
Afterwards, Apache Cassandra can work with good performance. \\
Every major Java release can differ from another one with such options for Java optimization.

Following Java optimizations are available for Java 8: \\
\begin{itemize}
\item \textbf{-XX:+UseCGroupMemoryLimitForHeap}  \\
This option tells the JVM to look into \path{/sys/fs/cgroup/memory/memory.limit} after the available memory and to use the whole memory if necessary \cite{Flood2017}.
\item \textbf{-XX:ParallelGCThreads=2} \\
Apache Cassandra is referencing  2 required CPUs as a minimum in their documentation \cite{Cassandra}.
This JVM option permits 2 GC (Garbage Collection) threads parallel on different (virtual) processors.
\end{itemize}

All these Java optimization options can be set as an environment variable with \lstinline!ENV JVM_OPTIONS! in the Dockerfile. Then they will be used for every Java process like Apache Cassandra as an example.
As a result, Apache Cassandra can use the whole memory and delivered CPU, which is specified in the \gls{QEMU} options.

\section{Workaround Because of a JVM Issue}\label{jvm-issue}

Apache Cassandra is using OpenJDK 8 for running as default. There are some discussions\footnote{\url{https://lists.apache.org/thread.html/r38f6beaa22e247cb38212f476f5f79efdc6587f83af0397406c06d7c\%40<dev.cassandra.apache.org>}} about supporting OpenJDK 11 at the moment. The Dockerfile mentioned above is using AdoptOpenJDK 8 at the build process is working without any problems on Z systems. There exists a JVM issue during the build process on x86 which is the reason for non-successful builds of Java applications there. That counts for all more complex Java applications.

This case has been tested with AdoptOpenJDK 8 and AdoptOpenJDK 11. The library hsdis-s390.so is not loadable for both Java versions for emulated s390x guests on x86, but during the build process on s390x\footnote{\url{https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=951764}}. This issue does not exist with the version AdoptOpenJDK 14, but Apache Cassandra does not work with this version. \\
This emulation bug of qemu has to be fixed, and the issue has been reported to \gls{KVM} Developers inside of IBM.

There exists a workaround for the development process for finishing the project. The Docker image is buildable on s390x. Therefore, the Docker image has been built for s390x on s390x with \\
\lstinline!docker build --squash -t cassandra .!. \\
Afterwards, this image can be saved as a tar archive with \\
\lstinline!docker save cassandra > cassandra.tar!\\
on the host. It has to be transferred with rsync to the x86 system then. The image inside of the tar archive can be included to all existing images of \lstinline!docker images! with the command
\lstinline!docker load --input cassandra.tar!. \\
After this action, the Docker image is usable as it would have been built on this system.
It can be integrated into \gls{QEMU} and be started without any problems afterwards.

\section{Nagios Monitoring Check for Tests} \label{monitoring}

Nagios is an open-source \gls{monitoring system} to check the status of systems with their services. There are many checks for different services available. One monitoring check\footnote{\url{https://github.com/skyscrapers/monitoring-plugins/blob/master/check_cassandra.pl}} exists for Apache Cassandra. It is testing whether Java would be working, the service Apache Cassandra would be up and running, and whether CQL commands would be possible to execute without any issues. This Perl script is using \textbf{nodetool} for monitoring the JVM and the application. Nodetool is delivered together with Cassandra. It is connecting with the database and can dispense statistics about the Cassandra cluster / host \cite[~p.256]{Carpenter2020}. The result contains the status, information about memory usage and other capacities. This tool can indicate issues resulting in messages via the monitoring plugin in our case.\\
This monitoring check is written in Perl and is an excellent choice for automated tests with error messages in the case if any output would not give an \textbf{OK}. \\
All monitoring plugins in the referenced Github repository are developed additionally for integration into Docker. Following, these scripts do not require any installed nagios system for monitoring.
Summarily, these monitoring plugins can be used for tests inside of containerized environments for testing Docker images.

\newpage
For a better maintenance, \textbf{cassandra\_check.pl} is integrated with a separate Dockerfile with the installation Dockerfile as a base image:
\begin{figure}[H]
\centering
\begin{boxedverbatim}
FROM cassandra-s390x
RUN apt-get update && apt-get install -y \
    perl \
    perl-base \
    libimage-magick-perl
WORKDIR /bin
COPY cassandra_check.pl /bin/cassandra_check.pl
ENTRYPOINT ["perl", "cassandra_check.pl"]
RUN apt-get remove -y \
    perl \
    libimage-magick-perl\
    perl-base  \
&& apt autoremove -y \
&& apt-get clean && rm -rf /var/lib/apt/lists/*
\end{boxedverbatim}
 \caption{Cassandra Monitoring Check}
    \label{Cassandra-Monitoring}
\end{figure}
The separation of both Dockerfiles profits by the reutilization of the main Dockerfile. The base Docker image can be published in different container registries for public usage without the monitoring check. Accessorily, the build process for the base image of Cassandra and the test with the monitoring check can be split in the \gls{CI/CD} pipeline. The possibility of bug identification is simplified by this process. \\
The test Dockerfile in the monitoring directory\footnote{\url{https://github.com/s390x-container-samples/s390x-cassandra-ci-cd/blob/master/monitoring/Dockerfile}} can be reused for every Cassandra container image based on Ubuntu or Debian. The unique requirement is that the FROM line is matching the name of the tested Cassandra image name.

\section{Run Docker Image in QEMU}\label{RunningDockerImage}

The Docker image will be built with the command  \\
\lstinline!docker build buildx --platform=linux/s390x --squash -t cassandra-s390 .! \\
in the directory with the Cassandra Dockerfile  for the architecture s390x. That is the base Cassandra image.\\
The \verb+--squash+ option is compressing a Docker image and is combining commands in a Dockerfile automatically. The prequisites for building s390x images on x86 are set during the emulation preparation. The command \lstinline!docker images! has to show the registered Docker image with the name cassandra-390 in the local container registry. Afterwards, the monitoring check has to be added.
The same procedure will be executed in the monitoring directory. The FROM command is referencing the self built Cassandra image with cassandra-s390. With the following command the monitoring check can be attached to the exiting Cassandra image to test it: \\
\verb+docker build buildx --platform=linux/s390x --squash -t cassandra-test-s390x .+ \\
It should be possible to integrate this Docker image into the qemu command. Therefore, a qemu-image will be created with an rounded given size besides of the Docker image in the  \lstinline!docker images! command. So the command \\
\lstinline!qemu-img create -f raw cassandra-s390x.img 2G!  \\
can be used. This image needs to be converted to any Linux file system because \gls{QEMU} does not know the Docker file system. Therefore, the image is formatted with the command  \lstinline!mkfs.ext4 -F cassandra-s390x.img!. A directory with the name rootfs has to be created and the command for receiving the file system of the Docker image. \\
\lstinline!docker export $(docker create cassandra-test-s390x) | tar -C "rootfs" -xvf -!  \\
is exporting the docker image into the directory rootfs. Afterwards, the following command transfers the content of rootfs into the image cassandra.img.

\begin{figure}[H]
\centering
\begin{boxedverbatim}
mkdir /mnt/rootfs
mount -o loop cassandra-s390x.img /mnt/rootfs
cp -r rootfs/* /mnt/rootfs/.
\end{boxedverbatim}
 \caption{Mount Rootfs}
    \label{Mount-Rootfs}
\end{figure}

Now it is possible to run the system with Cassandra: \\
\begin{figure}[H]
\centering
\begin{boxedverbatim}
 /usr/bin/qemu-system-s390x -kernel vmlinuz-4.15.0-20-generic -m 8G \
 -M s390-ccw-virtio -nodefaults -device sclpconsole,chardev=console \
 -parallel none -net none -chardev stdio,id=console,signal=off,mux=on \
 -mon chardev=console -nographic -smp 3 -hda cassandra-s390x.img \
 --append 'root=/dev/vda rw console=ttyS0 rdinit=/bin/bash'
\end{boxedverbatim}
 \caption{Run Cassandra}
    \label{RunCassandra}
\end{figure}

\newpage
\section{Integration into CI/CD}

The community of Apache Cassandra is using CircleCI\footnote{\url{https://circleci.com/}} as a Continuous Integration system.
This \gls{CI/CD} system is connected with Github. The tests are running after every commit in the master repository.
These tests can run in a container or in a virtual machine. These options make it possible to build the Docker image for the architecture s390x and to integrate it into \gls{QEMU} via the \gls{CI/CD} pipeline without additional scripting or workarounds. \\
CircleCI is working with a yaml configuration\footnote{\url{https://circleci.com/docs/2.0/sample-config/}}.
An enhancement is the opportunity to define shell commands with "command" in the yaml file. Therefore, \ref{LinuxKernel} "Fetching Signed Linux Kernel Image" can be integrated.
Additionally, dependencies can be created. On this way, it can be assured that the build process for the Docker image is triggered before the file system creation.
The same counts for the kernel fetching process and the file system creation before the \gls{QEMU} start. \\
This configuration file with the whole test process has got the name \textbf{config.yml}. \\
\textbf{Workflows} defines the order of different process steps with their dependencies with \textbf{- requires}.
The different processes are specified separately above then.
The advantage of different steps with dependencies is, that every step can be tested and the build process will be aborted after one failed process and this step will be listed with the error message in the \gls{CI/CD} system. \\
The configuration of CircleCI is clearly structured. The workspace can be declared. Running steps can receive names. Shell commands can be executed. Additionally, binaries and other files can be stored as artifacts. \\
The implementation of the job configuration can be found under \ref{CircleCI} "CircleCI configuration for Apache Cassandra". It can only work with a bug fix for the \ref{jvm-issue} "JVM Issue".\\
The system is configured that the version number of Apache Cassandra can be replaced by a new version with \verb+--build-arg CASSANDRA_VERSION=$CASSANDRA_VERSION+ in the docker build command. With that, the checkout of the special Cassandra branch will be executed instead of the configured last one.

max_stars_repo_name: skriesch/BachelorThesis

max_issues_repo_name: skriesch/BachelorThesis

max_forks_repo_name: skriesch/BachelorThesis


text:
\documentclass[sigconf]{acmart}

\usepackage{booktabs} % For formal tables

\begin{document}
\title{PyPandas: A data cleaning toolkits for Spark}

\author{Pei-Lun Liao}
\affiliation{%
  \institution{New York University}
}
\email{pll273@nyu.edu}

\author{Chia-Hsien Lin}
\affiliation{%
  \institution{New York University}
}
\email{chl566@nyu.edu}

\author{Shang-Hung Tsai}
\affiliation{%
  \institution{New York University}
}
\email{st3127@nyu.edu}

\begin{abstract}
Data cleaning is a huge challenge in data mining and machine learning tasks. In this paper, we propose PyPandas, a data cleaning toolkits running on Spark, to provide further solutions to data cleaning tasks. PyPandas provides advance cleaning features such as outlier detection, data scaling and text pattern searching and replacement. We have released PyPandas on GitHub.\footnote{https://github.com/shtsai7/PyPandas}\footnote{Verison 0.2.1 for milestone report}
\end{abstract}

\maketitle

\section{Introduction}
In recent years, as storage devices become cheaper, storing big data in thousands of computers is easier than before. People start thinking about how to extract useful information from the huge datasets. The term, Big Data, was created to describe this phenomenon\cite{bigdata}. As the result, data mining\cite{Han, MMD} and machine learning\cite{ml} get popular nowadays. The quality of data is one of the key factors to successful data mining\cite{dataquality}. Hence, data cleaning becomes a challenge in the first step of data management and analysis\cite{datacleaning, DBS-045, PW}.

To process huge datasets efficiently, distributed systems and parallel computing frameworks\cite{mapreduce, gfs, hadoop} were introduced. Spark\cite{spark} is one of the most popular open source projects for industry and academia. It is built on Hadoop\cite{hadoop} and provides a way to manage distributed memory. PySpark\cite{pyspark} is an extended library for Python programmers to work with Spark.

In the Python machine learning and data mining ecosystem, Pandas\cite{pandas} is the most popular data management library. Pandas dataframe provides convenient ways to collect data and several data management methods for missing value filling, data indexing and data profiling. In PySpark SQL module, PySpark provides Pandas-liked DataFrame to handle data indexing, data integration, and simple data cleaning tasks such as missing value handling and duplication removal.

However, PySpark DataFrame does not support advance data processing features like outlier detection and data scaling. Although there exists several clustering and scaling algorithms in the PySpark ML module, the integration with PySpark DataFrame is not helpful and can be difficult to use for data cleaning. User has to go back and forth to process their dataset.

In this paper, we propose PyPandas, a data cleaning toolkits built on top of PySpark, that integrates PySpark ML module to support user friendly data processing features such as outlier detection and numerical data scaling. These features are important for the machine learning tasks and are supported in Scikit-Learn\cite{scikit-learn}, a mainstream machine learning library, as well.

Furthermore, text data is another common data type in our storage. Text data is hard to process because of different languages, newly invented words, typos, abbreviations, urls and emoji etc. Although we have NLTK\cite{nltk}, a popular text cleaning library, there is no intergation with PySpark DataFrame. In this paper, we also intergate NLTK within our toolkits and provide customized tools for users to clean text data easily.

The features of our library are summarized below.
\begin{itemize}
	\item{User friendly data cleaning toolkits built on PySpark}
	\item{Outlier detection and numerical data scaling}
	\item{Text processing such as url detection, punctuation removing, pattern searching and replacement. }
\end{itemize}

\section{Related Work}
There exists a number of open-source library for data cleaning and parallel data computing.
\begin{itemize}
	\item{Optimus}\cite{optimus} is a framework that can perform distributed data cleaning and preprocessing. This framework works well with Spark and its DataFrame can scale in big cluster. Optimus comes with helpful tools such as removing special characters and replacing null values.
	\item{Dask}\cite{dask} is another open-source library that supports parallel analytic computing. It provides scalable parallel data structures that extend interfaces like Pandas. At the same time, it offers low latency and high responsiveness.
	\item{SparklingPandas}\cite{sparklingpandas} attempts to combine the power of Spark and Pandas to scale data analysis. It provides a Pandas-like API that is built using Spark's DataFrame class. Unfortunately, it only support spark v1.4 and Python 2.7, and its development has ended.
\end{itemize}

\section{Problem Formulation}
In this paper, we focus on three major tasks, outlier detection, data scaling, and text pattern searching and replacement.
\subsection{Outlier Detection}
Outlier or anomalies detection is a challenging task in the field of data cleaning\cite{anomal}. In this paper, we simply define outlier as the data that is far away from data centroid. Hence, given a dataset $X$, a clustering algorithm $A$\cite{MMD}, a distance measurement $d$, and the user-defined threshold $t$, the outlier is simply defined as following.

\[ outlier = \{x | x \in X, d( x, x_{A_X(x)} ) > t \}  \]

where $A_X(x)$ assigns $x$ into a cluster given the dataset $X$ and $x_c$  is the centroid of cluster $c$.

\subsection{Scaling and Normalization}
Scaling and normalization are common preprocess in data cleaning. It is crucial to several machine learning models and optimization methods. Scaling increases the convergence speed and chance to find good optimum\cite{convex}. The scaling problem could be formulated as below.
Given an one dimensional numerical dataset $X$, we provide a scaling method $S$ such that scaled elements are bounded in same reasonable range $[a, b]$.

\[ S_X(x) \in [a, b]\]

where $x \in X$ and $|a - b|$ should not be large.

To define the problem formally, we consider and implement several specific scaling methods.
\begin{itemize}
	\item{Standard scale}
		\[ S(X) = \dfrac{X-\mu}{\sigma} \in \text{proper deviation range}\]
		where $\mu$ is the mean of $X$ and $\sigma$ is the standard deviation of $X$
	\item{Min-Max scale}
		\[ S(X) = \dfrac{X-min(X)}{max(X) - min(X)}\in [0.0, 1.0] \]
	\item{Max-Abs scale}
		\[ S(X) = \dfrac{X}{max(X)} \in [-1.0, 1.0] \]
	\item{P-norm Normalization}
		\[ S(X) = \dfrac{X}{\|X\|_{p}} \in [-1.0, 1.0]\]
\end{itemize}

\subsection{Pattern Searching and Replacement}
Pattern searching and replacement is a common technique in cleaning text data. Given a string $t$ and a regular expression\cite{theory_com} $re$, we replace the matched pattern with a user-defined string $s$. The replacement function $R$ could be defined as following.
Consider $t$ as a concatenation of non-overlapping substrings $t = t_1...t_n$.

\[ R(t) =  r(t_1)...r(t_i)...r(t_n)\]

\[r(t) = \begin{cases} s & \text{if $M$ accept $t$} \\ t & \text{otherwise} \end{cases}\]

\[\text{such that $M$ does not accept any substring of } R(t)\]

where $M$ is the generalized nondeterministic finite automaton\cite{theory_com} corresponding to the regular expression $re$. We do not define replacement order and simply ignore it.

\section{Methods, Architecture and Design}
In this project, we build our library on top of PySpark. We handle PySpark DataFrame and implement useful data cleaning functions in our library. We integrate PySpark ML module and customize user define functions to perform advanced cleaning features such as pattern searching and replacement with regular expression. We survey the PySpark\cite{pyspark}, Pandas\cite{pandas} and Scikit-Learn\cite{scikit-learn} libraries to find out key features and create Pandas-like and Scikit-Learn-like API to provide easy usage and seamless adaptation.

\subsection{Outlier Detection}
\subsubsection{Design}
Our goal in outlier detection is to integrate the existing clustering algorithms in PySpark ML module to provide user-friendly solution for outlier detection. Users are able to select existing clustering algorithms. Furthermore, users are given the power to decide their own threshold value based on their knowledge about the dataset to filter outliers. To help users identify outliers and pick a proper threshold, we provide statistics summary of the clustering. Possible future work on outlier detection is to provide framework to register user defined clustering algorithms or implementing popular clustering algorithms such as DBScan\cite{DBScan} in our library.

\subsubsection{Architecture}
The implementation of the outlier detection functionality integrates the PySpark ml package. Our architecture hides the complexity of training and tuning clustering models, while it exposes easily accessible APIs for users to remove outliers. In addition, our data cleaning library implements User Defined Functions to compute distance between data points and cluster centers, as well as other summary statistics. At this time, our current remover can handle outliers with KMeans clustering algorithm. We will refactor our architecture to integrate all existing clustering algorithms in PySpark ML module. To simplify our architecture, we will use Factory Design Pattern to construct different types of outlier removers with the generic APIs.

\subsubsection{Methods}
\begin{itemize}
	\item{KMeans}\cite{KMeans}: Users can specify the number of clusters to use based their knowledge about the dataset. The system will choose random initial values, and perform 20 iterations of updates. Finally, a summary of the clusterings will be generated, which includes cluster centers, cluster sizes, distances, etc. User can then filter out outliers in each cluster by specifying a minimum distance from the cluster center, and all data points that are beyond that distance will be removed from the dataset.
\end{itemize}

\subsection{Scaling and Normalization}
\subsubsection{Design}
Standardization is a common requirement for many machine learning algorithms, since some optimization methods will not work properly without scaling or normalization\cite{convex}. Our goal in scaling and normalization is similar to the goal of outlier detection. We will intergrate existing scaling algorithms in PySpark ML module into our library. User can choose existing scaling algorithms to scale their datasets. The future works is to provide framework to register user defined scaling algorithms.

\subsubsection{Architecture}
Since the design is similar with the design of outlier detection, we will follow the architecture of outlier detection. We will use the Factory Design Pattern to allow users construct their desired scaling models. We are considering to implement a single interface between any existing models in PySpark ML module to DataFrame in PySpark SQL module. Hence, we will be able to provide any feature transformation with the existing machine learning models in PySpark ML module.

\subsubsection{Methods}
\begin{itemize}
	\item{Standard Scale}: Performs basic scaling on a particular column or a list of columns in a dataframe so that the values have unit standard deviation and zero mean.
	\item{Min-max Scale}: Rescales columns to a user defined range(e.g. [0, 1]) using min max scaling.
	\item{Max-abs Scale}: Transforms columns to range between -1 and 1 by dividing through the maximum absolute value in the columns. This operation does not shift/center the data, and thus does not destroy any sparsity.
	\item{Normalization}: Given a list of columns, the normalize function can generate a normalized feature vector having unit norm. The default p-norm value for normalization is 2.0, yet users can optionally specify the p-norm value.
\end{itemize}

\subsection{Pattern Searching and Replacement}
\subsubsection{Design}
To provide a useful text cleaning toolkits, we need to have the flexibility for user to search any pattern and replace the matched ones with any user defined string. At the same time, we have to provide common patterns so that users won't need to reinvent the wheel. For example, url pattern, leading space, trailing space or numbers are common search patterns that we should provide. Moreover, we would like to integrate NLTK\cite{nltk}, a popular natural language toolkit, into our library. With NLTK, we would be able to perform advanced cleaning tasks or feature transformation.
%%to follow the don't repeat yourself (DRY) principle

\subsubsection{Architecture}
In order to achieve those design issues, we extract the common logic and column feature transformation into our core functions. We design the architecture such that user defined functions can be applied on a single or multiple columns, and a new DataFrame will be provided. The user defined function could be a regular expression substitution function, a column scaling function or a natural language processing function in NLTK. Our architecture ensures the flexibility to various customized processing methods.

\subsubsection{Methods}
We define several common regular expression patterns in table \ref{tab:reg} and provide simple cleaning functions to handle those patterns in text data.
\begin{table}
\caption{Common Regular Expression Pattern}
\label{tab:reg}
\begin{tabular}{lc}
	Common Pattern & Regular Expression \\
\hline
	URL & URL regular expression\cite{url} \\
	Leading space & \verb!'^ +'! \\
	Trailing space & \verb!' +$'! \\
	Consecutive space & \verb!' +'! \\
	Number & \verb!'\d+'!  \\
	Not a word & \verb!'[^\w\d\s]+'! \\
	Blank & \verb!'_+'!
\end{tabular}
\end{table}

\begin{table}
\caption{Selected dataset}
\label{tab:dataset}
\begin{tabular}{lccc}
 		                 & (Row, Col)  & Size      & Missing Value  \\
\hline
 311 Service Requests   & (9M, 53)     & 6.01 GB  & 28\%            \\
 Permit Issuance            & (3M, 60)     & 1.43 GB  & 20\%             \\
 Job Application Filings   & (5M, 89)     & 2.88 GB  & 40\%             \\

\end{tabular}
\end{table}

\begin{table*}
\caption{Evaluation: Features Comparison}
\label{tab:features}
\begin{tabular}{lccccc}
						&  PySpark DataFrame\cite{pyspark} 	& PyPandas 	& Optimus\cite{optimus} 	& SparkingPandas\cite{sparklingpandas} 	& Dask\cite{dask}	\\
&&&&& \\
Data manipulation &&&&& \\
\hline
Data integration				& \checkmark 	        			& \checkmark   	& \checkmark		& 							& \checkmark	 \\
Data aggregation				& \checkmark 	        			& \checkmark   	& \checkmark		& \checkmark					& \checkmark	 \\
Data filtering					& \checkmark 	        			& \checkmark   	& \checkmark		& 							& \checkmark	 \\
Data profiling				& \checkmark 	        			& \checkmark   	& \checkmark		& \checkmark					& \checkmark	 \\
Data sorting					& \checkmark 	        			& \checkmark   	& \checkmark		& 							&	 		 \\

&&&&& \\
Basic data cleaning &&&&& \\
\hline
Missing value filling	 			& \checkmark 		  	      	& \checkmark   	& \checkmark		& 							& \checkmark	 \\
Missing value removing			& \checkmark 	 	  	     	& \checkmark   	& \checkmark 		& 							& \checkmark	 \\
Duplication removing 			& \checkmark 			       	& \checkmark 	& \checkmark		&							& \checkmark	\\

&&&&& \\
Outlier Detection &&&&& \\
\hline
Deviation with median			&						& 			& \checkmark		&							&			\\
Clustering algorithms			&						& \checkmark	& 				&							&			\\

&&&&& \\
Scaling and Normalization &&&&& \\
\hline
Standard scaling				&						& \checkmark	& 				&							& \checkmark	\\
Scale in range				&						& \checkmark	& 				&							& \checkmark	\\
Normalization				&						& \checkmark	& 				&							& 			\\

&&&&& \\
Text Cleaning &&&&& \\
\hline
Special character removing		& \checkmark				& \checkmark	& \checkmark		&							&		\\
Pattern searching 			 	& \checkmark				& \checkmark	& \checkmark		&							&		\\
Pattern searching and replacement 	&						& \checkmark	&				&							&		\\
\end{tabular}
\end{table*}

\section{Experiment}
\subsection{Dataset}
Three datasets are chosen for the experiments. Each of them has different properties and can be used to test different parts of the library. The summary of datasets could be found in table \ref{tab:dataset}.
\begin{itemize}
	\item{311 Service Requests}\cite{nycopendata1} This dataset contains all 311 Service Requests since 2010. The majority of data has string type, including both categorical  data (e.g. City, Status) and variable length data (e.g. Address, Description). This can be useful in testing the string-related features of the library.
	\item{DOB Permit Issuance}\cite{nycopendata2} The dataset consists of a list of permits for buildings in NYC issued by Department of Building. It has diverse data types, including categorical, string, numerical, and geographical data. Hence, it provides a good test case for the versatility of the library.
	\item{DOB Job Application Filings}\cite{nycopendata3} The dataset stores job applications filed through the Borough Offices in NYC. There are many columns containing numerical data, such as fee and number of stories. It can be used to test the data scaling and outlier detection features.
\end{itemize}

\subsection{Evaluation}
We will evaluate our project by comparing it against other existing open-source libraries, including Optimus\cite{optimus}, Dask\cite{dask}, and SparkingPandas\cite{sparklingpandas}.
\subsubsection{Features}
We will compare our data cleaning features with previous works, particularly those frequently used functionality in data science such as null value handling, special character removal, duplicate detection, etc.
\subsubsection{Performance}
We will evaluate the performance of our library by measuring the time and space consumed and drawing comparison with existing libraries. This performance evaluation will show that this library is efficient and can be useful in production.
\subsubsection{Usability}
We might assess the usability of our library by doing a survey among a random group of users. We will compare the installation process and APIs provided and generate scores of user experience.

\subsection{Preliminary Results}
At current stage, our experiments were run on the Dumbo clusters of NYU. We plan to migrate our settings to AWS since we will have the privileges needed to install other packages there. While on Dumbo, we don't have such privileges. We will perform comparison with other related works after we finish migration.

\subsubsection{Features}
In this section, we compare our features with previous works. The result is shown in table \ref{tab:features}. We find that PySpark DataFrame provide easy-to-use data manipulation functions. Since PyPandas and Optimus extend the DataFrame, both support the same data manipulation features. In SparkingPandas, the project only aims to provide grouping methods on Pandas-liked dataframe and miss other important features in data manipulation. Dask also support many features in data manipulation.

PySpark DataFrame, Optimus, Dask, and our library all provide the basic data cleaning functions like missing value handling. In the outlier detection, Optimus detects outliers by calculating the deviation with the median of data. On the other hand, PyPandas provides advance detecting methods with clustering algorithms. Dask do support several clustering algorithms. Nonetheless, they are not integrated in their Dask DataFrame. Users have to train and tune the models to detect the outliers.

In scaling and normalization, Dask and PyPandas provide basic scaling methods like standard scaling or min-max scaling. However, Dask does not provide normalization on their Dask ML preprocessing module.

For the text cleaning, PyPandas provides more powerful pattern searching and replacement feature to let user find out any pattern and replace the matched one with their desired value. Moreover, PyPandas defines several common patterns for users to clean their text quickly without repeating themselves. In summary, PyPandas extends PySpark DataFrame and provides more easy-to-use features for users to clean their data.

\subsubsection{Performance} We evaluate the performance of different parts of our library. The total of execution times of each task, including the time for Spark initialization, data loading, and data preprocessing, were all recorded and listed below.
\begin{itemize}
	\item{Outlier Detection Experiment}: This experiment is performed on the DOB Job Application Filings Dataset. 15 columns that contain numerical values are chosen. We use K-Means Outlier Remover with three different k values [1, 2, 3]. For each k value setting, we run the clustering with different number of attributes (dimensions). The results are shown in table \ref{tab:Outlier Detection Experiment Result}.
	\item{Scaling and Normalization Experiment}: This experiment involves all three testing datasets. We choose three columns with numerical values from each dataset as input. For each input, we test all scaling and normalization operations. The experiment results can be found in table \ref{tab:Scaling and Normalization Experiment Result}.
\end{itemize}

\begin{table}
\caption{Outlier Detection Experiment Result}
\label{tab:Outlier Detection Experiment Result}
\begin{tabular}{cccc}
Dimension  &  k = 3  &  k = 4  & k = 5  \\
\hline
1   & 1 m 15.15 s  & 1 m 6.48 s   & 1 m 6.27 s             \\
3   & 1 m 7.13 s    & 1 m 4.97 s   & 1 m 5.52 s             \\
5   & 1 m 5.94 s    & 1 m 5.30 s   & 1 m 6.82 s             \\
10 & 1 m 7.64 s    & 1 m 12.36 s & 1 m 11.18 s           \\
15 & 1 m 7.57 s    & 1 m 9.12 s   & 1 m 7.92 s             \\

\end{tabular}
\end{table}

\begin{table}
\caption{Scaling and Normalization Experiment Result}
\label{tab:Scaling and Normalization Experiment Result}
\begin{tabular}{lccc}
 	                      &  311 Service  &  Permit    &  Job Application \\ &Requests&Issuance&Filings   \\
\hline
Standard Scale   & 3 m 8.15 s     & 1 m 25.57 s & 1 m 19.96 s            \\
Min-max Scale  &  3 m 7.15 s   & 1 m 25.95 s  & 1 m 20.07 s             \\
Max-abs Scale  & 3 m 7.15 s     &  1 m 24.48 s  & 1 m 19.90 s             \\
Normalization    & 1 m 18.95 s     &  38.41 s & 39.48 s             \\

\end{tabular}
\end{table}

\section{Conclusions}
Due to the lack of advance data cleaning features on Spark, we propose PyPandas, a data cleaning toolkit built on PySpark. We provide advance data cleaning features such as outlier detection, data scaling, and text pattern searching and replacement.

%\section{reference}
\bibliographystyle{ACM-Reference-Format}
\bibliography{citation}

\end{document}


text:
\section{Introduction}
\label{sec:introduction}

The value of profiling code is indisputable.  \R's own \code{Rprof()} function
is extremely useful, but its profiling capabilities are limited to simple
timings of \R functions. This is a very good starting point in performance
analysis and can quickly help the \R programmer focus in on bottlenecks.  But
for more experienced developers (especially those working with compiled code)
additional performance information can be invaluable. Access to low-level
hardware counter data can have tremendous impact when trying to understand and
optimize performance of compiled code.

The \thispackage~\citep{Schmidt2014pbdPAPIpackage} package offers access to
this low-level hardware counter information by way of the high-level \C library
\PAPI~\citep{mucci1999papi}.  Therefore, an installation of \PAPI is required in
order to use the package.  For convenience, we bundle \PAPI version \PAPIversion
with \thispackage, which will install by default.  However, with appropriate
configure arguments, one can easily build \thispackage with an existing system
installation of \PAPI.  See Section~\ref{sec:installation} for details.

The current main features of \thispackage include:
\begin{enumerate}
  \item Simple, high-level interfaces that mimic \R's own profiling syntax.
  \item A low-level interface that mimics \PAPI's native calls, with extremely
  general functionality.
  \item A comprehensive set of package demonstrations.
  \item This vignette.
\end{enumerate}

Note that the \pkg{pbdPAPI} package is not officially affiliated with the
\pkg{PAPI} project.

%%% Generic message for vignettes
\subsection{Installation Issues and Reporting Bugs}

\secref{sec:installation} contains useful information about how to install
\thispackage.  Additionally, Sections~\ref{sec:use}, \ref{sec:examples}, and
\ref{sec:moreinfo} offer useful information about using \thispackage.

If something goes wrong with installation or package use, please feel free to
make use of our google group \url{http://group.r-pbd.org/}.  We also actively
monitor a mailing list if you wish to contact us directly:
\href{mailto:RBigData@gmail.com}{RBigData@gmail.com}

%%% pbdPAPI specific
For installation issues, please try to give us as much information as
reasonably possible to help you.  If \thispackage installs but you have trouble
using it (for example, a function explicitly encourages you to report an error
to us), please provide us the output of \code{pbdPAPI:::hw.info.internal()}
(note the three colons) and \code{hw.info()}.

max_stars_repo_name: wrathematics/pbdPAPI