Finding Needle in a Million Metrics: Anomaly Detection in a Large-scale Computational Advertising Platform
% You can go ahead and credit any number of authors here
% e.g. one 'row of three' or two rows (consisting of one row of three % and a second row of one
two or three). % % The command \alignauthor (no curly braces needed) should % precede each author name
affiliation/snail-mail address and % e-mail address. Additionally
tag each line of % affiliation/address with \affaddr
and tag the % e-mail address with \email. % % 1st. author \alignauthor Bowen Zhou
\affaddr{Turn Inc.
Online media offers opportunities to marketers to deliver brand messages to a large audience. Advertising technology platforms enables the advertisers to find the proper group of audiences and deliver ad impressions to them in real time. The recent growth of the real time bidding has posed a significant challenge on monitoring such a complicated system. With so many components we need a reliable system that detects the possible changes in the system and alerts the engineering team. In this paper we describe the mechanism that we invented for recovering the representative metrics and detecting the change in their behavior. We show that this mechanism is able to detect the possible problems in time by describing some incident cases.
ACMTargetAd2016.tex
% This is "sig-alternate.tex" V2.1 April 2013
% This file should be compiled with V2.5 of "sig-alternate.cls" May 2012
%
% This example file demonstrates the use of the 'sig-alternate.cls'
% V2.5 LaTeX2e document class file. It is for those submitting
% articles to ACM Conference Proceedings WHO DO NOT WISH TO
% STRICTLY ADHERE TO THE SIGS (PUBS-BOARD-ENDORSED) STYLE.
% The 'sig-alternate.cls' file will produce a similar-looking,
% albeit, 'tighter' paper resulting in, invariably, fewer pages.
%
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V2.5) produces:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) NO page numbers
%
% as against the acm_proc_article-sp.cls file which
% DOES NOT produce 1) thru' 3) above.
%
% Using 'sig-alternate.cls' you have control, however, from within
% the source .tex file, over both the CopyrightYear
% (defaulted to 200X) and the ACM Copyright Data
% (defaulted to X-XXXXX-XX-X/XX/XX).
% e.g.
% \CopyrightYear{2007} will cause 2007 to appear in the copyright line.
% \crdata{0-12345-67-8/90/12} will cause 0-12345-67-8/90/12 to appear in the copyright line.
%
% ---------------------------------------------------------------------------------------------------------------
% This .tex source is an example which *does* use
% the .bib file (from which the .bbl file % is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission, you *NEED* to 'insert'
% your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% ================= IF YOU HAVE QUESTIONS =======================
% Questions regarding the SIGS styles, SIGS policies and
% procedures, Conferences etc. should be sent to
% Adrienne Griscti (griscti@acm.org)
%
% Technical questions _only_ to
% Gerald Murray (murray@hq.acm.org)
% ===============================================================
%
% For tracking purposes - this is V2.0 - May 2012

\documentclass{sig-alternate-05-2015}
\usepackage{subfigure}

% For algorithms in ACM template
\makeatletter
\newif\if@restonecol
\makeatother
\let\algorithm\relax
\let\endalgorithm\relax
\usepackage[ruled,vlined,linesnumbered,commentsnumbered]{algorithm2e}

\usepackage{url}
\urlstyle{rm}

\usepackage{verbatim}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{algorithmic}

\usepackage{subfigure}

\usepackage{color}
\definecolor{gray}{gray}{0.95}
\usepackage{listings}
\lstset{%
	basicstyle={\small\ttfamily},
	numberstyle=\tiny,
	backgroundcolor=\color{gray},
	breaklines=true,
	breakatwhitespace=true,
	breakindent=0pt}
	
\usepackage{url}

\newcommand{\var}[1]{{\operatorname{\mathit{#1}}}}

\newcounter{def_count}
\setcounter{def_count}{0}
\newtheorem{definition}[def_count]{Definition}

\newcounter{theorem}
\setcounter{theorem}{0}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{theorem}{Theorem}

\def\NoNumber#1{{\def\alglinenumber##1{}\State #1}\addtocounter{ALG@line}{-1}}


\begin{document}

% Copyright
%\setcopyright{acmcopyright}
%\setcopyright{acmlicensed}
%\setcopyright{rightsretained}
%\setcopyright{usgov}
%\setcopyright{usgovmixed}
%\setcopyright{cagov}
%\setcopyright{cagovmixed}


% DOI
%\doi{10.475/123_4}

% ISBN
%\isbn{123-4567-24-567/08/06}

%Conference
%\conferenceinfo{PLDI '13}{June 16--19, 2013, Seattle, WA, USA}

%\acmPrice{\$15.00}

%
% --- Author Metadata here ---
%\conferenceinfo{WOODSTOCK}{'97 El Paso, Texas USA}
%\CopyrightYear{2007} % Allows default copyright year (20XX) to be over-ridden - IF NEED BE.
%\crdata{0-12345-67-8/90/01}  % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.
% --- End of Author Metadata ---

\permission{Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.}
\conferenceinfo{TargetAd 2016: 2nd International Workshop on Ad Targeting at Scale,}{WSDM, February 22--25, 2016, San Francisco, CA, USA.}
\copyrightetc{{\em TargetAd 2016: 2nd International Workshop on Ad Targeting at Scale, WSDM, February 22--25, 2016, San Francisco, CA, USA.}}
\crdata{}


\title{Finding Needle in a Million Metrics: Anomaly Detection in a Large-scale Computational Advertising Platform}
%
% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

\numberofauthors{2} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%
\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
\alignauthor
Bowen Zhou\\
       \affaddr{Turn Inc.}\\
       \affaddr{901 Marshal St.}\\
       \affaddr{Redwood City, CA}\\
       \email{bzhou@turn.com}
% 2nd. author
\alignauthor
Shahriar Shariat\\
       \affaddr{Turn Inc.}\\
       \affaddr{901 Marshal St.}\\
       \affaddr{Redwood City, CA}\\
       \email{sshariat@turn.com}
}
% There's nothing stopping you putting the seventh, eighth, etc.
% author on the opening page (as the 'third row') but we ask,
% for aesthetic reasons that you place these 'additional authors'
% in the \additional authors block, viz.
\date{23 November 2015}
% Just remember to make sure that the TOTAL number of authors
% is the number that will appear on the first page PLUS the
% number that will appear in the \additionalauthors section.

\maketitle
\begin{abstract}
Online media offers opportunities to marketers to deliver brand messages to a large audience. Advertising technology platforms enables the advertisers to find the proper group of audiences and deliver ad impressions to them in real time. The recent growth of the real time bidding has posed a significant challenge on monitoring such a complicated system. With so many components we need a reliable system that detects the possible changes in the system and alerts the engineering team. In this paper we describe the mechanism that we invented for recovering the representative metrics and detecting the change in their behavior. We show that this mechanism is able to detect the possible problems in time by describing some incident cases.

\end{abstract}


%
% The code below should be generated by the tool at
% http://dl.acm.org/ccs.cfm
% Please copy and paste the code instead of the example below. 
%
\begin{CCSXML}
<ccs2012>
<concept>
<concept_id>10002951.10003227.10003447</concept_id>
<concept_desc>Information systems~Computational advertising</concept_desc>
<concept_significance>500</concept_significance>
</concept>
</ccs2012>
\end{CCSXML}

\ccsdesc[500]{Information systems~Computational advertising}

%
% End generated code
%

%
%  Use this command to print the description
%
\printccsdesc

% We no longer use \terms command
%\terms{Theory}

\keywords{Anomaly detection, Change point detection, Computational advertising}

\section{Introduction}
\label{sec:intro}
Online advertising has enabled the marketers to engage with the proper audiences in real time. This has resulted in exponential growth of online advertising and, in particular, real time bidding \cite{Yuan14}. The real time bidding platforms are complicated systems with many moving parts. Such platforms, typically, are highly distributed with low latency requirements. They offer variety of targeting and biding options and have diverse set of clients with radically different requirements, goals and budgets. The simple implication of such a heterogeneous environment is that, the likelihood of failure is not negligible. In other words, there is always a module, third party data or incoming traffic that can change and result in an abrupt and unexpected behavior of the system that can affect the entire set of advertisers, or just a group of advertising campaigns.

In order to monitor the health of the system, we, at Turn, have thousands of metrics that are monitored by various mechanisms. Many of such monitoring systems, rely on some anomaly detection algorithm. There has been a significant research work on anomaly detection. Refer to \cite{Chandola09,Chandola12} for comprehensive surveys on many anomaly detection algorithms and their applications. More recent works, such as \cite{Laptev15}, mainly focus on post processing techniques that reduce the false alarms and increase the quality of an anomaly detection task.Depending on the nature of the metric and its limitations, such as availability of labels, historical data, etc. , one needs to decide to choose from variety of algorithms and processing techniques.

 An important class of metrics is the final performance indicators. In advertising, these indicators include campaign's spending, number of submitted ad impressions, click through rate (CTR), conversion rate (CVR), etc. These metrics are the most interesting indicators for the advertisers. However, they are difficult to monitor since they are dependent on the incoming traffic, system performance and even the campaign setup, such as budget, audience targeting criteria, etc. 

We pose the monitoring of the final campaign performance metrics as a \emph{contextual anomaly detection} problem \cite{Chandola09}. We show that by clustering the relevant campaigns and selecting an appropriate representative for each cluster and other computational techniques, one can use a standard, and yet robust, anomaly detection algorithm to achieve a superior monitoring system. The contributions of this papers are:
\begin{itemize}
\item Enumerating and explaining the requirements and challenges of imposing a monitoring system on campaign performance metrics.
\item Proposing a method, based on correlation and statistical testing for representing the clusters of similar campaigns.
\item Presenting a comprehensive system for real time monitoring and alerting on final campaign performance metrics.
\end{itemize}

The rest of the paper is organized as follows. In \S~\ref{sec:background} we present some background on demand side platforms and its monitoring requirements. The detail of the system design and methodology is presented in \S~\ref{sec:design}. The evaluation of the the proposed system is presented in \S~\ref{sec:eval} and the paper is concluded by \S~\ref{sec:conclusion}.

\section{Background}
\label{sec:background}
A demand side platform (DSP), manages marketing campaigns of several advertisers simultaneously by identifying the target audience matching the campaign requirements and making real time bidding decisions on behalf of the advertisers to purchase ad impressions at the `best' price. Therefore, many advertisers have been compelled to use DSPs to deliver their branding messages to the right audience at scale. On the other hand, more users around the world are using the Internet to access the information on daily basis. Consequently, more advertising budgets together with more incoming traffic, have posed a great challenge on DSPs to scale and maintain the quality of service. In this section, we briefly describe the relevant background on the general design of a DSP and the overall monitoring system to set the stage for our proposed framework.
\subsection{Demand Side Platform}
\begin{figure}
\centering
\includegraphics[scale=.5]{DSP-schema.pdf}
\caption{The schematic design of a typical demand side platform.}
\label{lbl:DSP-schema}
\end{figure}
Figure \ref{lbl:DSP-schema} depicts the overall architecture of a demand side platform. The exchange (or the supply side platform) submits a bid request that describes the inventory by specifying the URL, position of the ad, acceptable ad format, ect., and, if available, a user ID. The request is received by the \emph{presentation server}, where it is decoded and augmented by a user profile that is extracted from a profile server, based on the provided user ID. This decoded message, sometimes called an \emph{adCall}, is then submitted to an \emph{ad server}. Ad server, receives the adCall, the set of ads and their budget, and determines the set of ads that are qualified to bid for the inventory. For each qualified ad, a bid is estimated that quantifies the value of the inventory to the advertiser for that specific ad. For instance, if the advertiser value a click at 2\$ and the the bid estimation algorithm estimates that the probability of the click is 1\%, then the bid price for this ad, inventory and user is 0.02\$. Refer to~\cite{Lee12,Shariat15}, for more detail on bid prediction and model evaluation.

After producing a bid for each one of the qualified ads, the ad server submits back the ad that has the highest estimated bid price, to the presentation server, which, after encoding, sends this information back to the exchange. The ad exchange platform, conduct an auction to identify the winner ad submitted by multiple DPS. If the submitted ad wins the auction, the DSP will be notified to serve the corresponding ad impression. This entire process needs to be completed within at most 100 millisecond including the network delay.

An important component in the above work flow, is a service that we call the \emph{control server}. Control server maintains the real time budget of each campaign, the number of impressions, the spending, clicks and conversion attributed to each campaign. The main duty of the control server is to allocate~\cite{Geyik14} and pace~\cite{Xu15} the budget of each campaign through its lifetime. Therefore, in contrast to other services, the control server is a singleton. The ad serving services, namely presentation, profile and ad servers, are highly distributed services. Therefore, a centralized service, i.e. the control server, is required to gather the information, specially, about the spending and remaining budget. This property gives the control server a unique position as the source of truth. Therefore, our anomaly detection mechanism is deployed in the control server. 

\subsection{Monitoring}
Having a highly complicated and distributed architecture, a DSP is prone to falter at any time. There are generally two sources of failure: i)internal and ii) external.

\textbf{Internal}: A bug in the most recent release is probably the most common internal issue. Despite comprehensive testing, it is still possible that a faulty code is deployed in the production. This can cause immediate crashes in the system or, it might cause only a set of campaigns to perform slightly worse. 

\textbf{External}: A DSP is dependent on its exchange partners. If they fail to provide a robust and reliable traffic, the performance of a DSP can be greatly affected. Also, many advertisers would like to use third-party or first-party data. For instance, an advertiser might need to use its own marketing data for targeting the correct audience. In that case, the DSP needs to ingest that data and use them during the ad serving. Another example is when an advertiser wants to use a mechanism offered by a third-party provider for filtering the web sites that its ads are served to. A failure on part of a data provider can cause the system to behave abnormally, despite the fact that all internal systems are performing as expected.

There is also, more sensitive services, such as fraud detection for which, one might want to use a combination of external and internal solutions.

One needs to impose monitoring systems on all the relevant metrics from incoming traffic to messages passed between the services and the internal health of each service such as its memory and CPU usage (per machine). It is evident that there are thousands of metrics that need to be monitored. 

A set of important metrics that represent the health of system and needs to be watched closely is the final output of the system. That is, the ad serving and the possible outcomes, i.e. clicks and conversions. Actually, as long as the campaigns are serving ads and spend their budget and observe clicks and conversions at a \emph{stable} pace, there is no urgent problem. Essentially, if for instance, an exchange partner fails but majority of the campaigns are able to switch their ad serving to another exchange, the urgency of the issue is much less than a failure that stops some campaigns from spending their budget. 

Therefore, our focus in this paper is to impose a reliable and robust monitoring system on the final output of the system, which is campaign spending and performance. 

\subsection{Goals}
The goal of our anomaly detection system is to issue an alert about once the DSP is not functioning as expected, in a timely manner so the engineers could investigate and fix the issues before considerable damage is caused.
\begin{itemize}
	\item The metric itself, must be as informative as possible. That is, once the alert is initiated, we must have a quick way to isolate the cause of malfunctioning.
    \item The alert should have a reasonably high precision. As we mentioned earlier, the alerts that are generated on the final campaign performance metrics are considered as a high priority and thus, it is important that we employ a reliable and precise mechanism for initiating them. We do not want to miss an incident either and therefore, we require the detection algorithm to posses a reasonable discovery rate as well. In fact we would prefer a to have a few false alarms in the interest of a higher discovery rate. 
	\item The alerts should be triggered within reasonable amount of time, typically a couple of hours since the onset of an incident.
\end{itemize}
 The latency requirement poses a challenge on the control server. To attain a holistic view of the campaign performance, the anomaly detection system collects data from all campaigns, which imposes overhead to several latency-sensitive core components in the DSP, such as budget pacing and data collection. As a result we need to minimize the performance impact by running the detection system less frequently and hence tolerate longer failure-to-detection latencies.


\input{design}
\input{eval}

%
% The following two commands are all you need in the
% initial runs of your .tex file to
% produce the bibliography for the citations in your paper.
%\bibliographystyle{abbrv}
%\bibliography{acmTargetAd}  % sigproc.bib is the name of the Bibliography in this case
\input{acmTargetAd.bbl}
% You must have a proper ".bib" file
%  and remember to run:
% latex bibtex latex latex
% to resolve all references
%
% ACM needs 'a single self-contained file'!
%
%APPENDICES are optional
%\balancecolumns
%\appendix

\end{document}

design.tex
\section{Design}
\label{sec:design}
\begin{comment}
\begin{figure}
	\centering
	\includegraphics[width=\linewidth]{weekly-periodic-usd}
	\caption{Periodic Patterns in a Performance Metric.}
	\label{fig:periodic}
\end{figure}

Change is the only constant in the realm of real-time bidding. Every bid request originated at publisher sites traverses a myriad of distributed systems running at ad exchanges and DSPs. Thousands of campaigns are analyzed by a DSP to figure out if the bid request matches their targeting criteria and if a campaign can afford the cost of the impression. The DSP system observes millions of advertisement opportunities coming in as bid requests every second from ad exchanges. It assemblies the real-time data contained by the bid requests and the historical data from local storage systems to identify the targeted audience and estimate the bid price using statistical modeling. The DSP system often employs smart budget pacing~\cite{Xu15} and allocation~\cite{Geyik14} algorithms to meet delivery goals and maximize the ROI of campaigns. The performance of campaigns is influenced by many of these aforementioned components and the interaction among them.

\subsection{Factors}
\label{sec:factors}

The volume of qualified traffic determines the top line for the performance of a campaign. The targeting criteria of a campaign include various requirements for both the audience and the context, for example, age, gender, income, geo locations, behavioral properties, content displayed, and so on. Among all the bid requests received by a DSP, only those that satisfy the targeting criteria of a campaign can be deemed as qualified traffic. For example, a campaign for diapers may just be interested in parents of small children. Traffic is an external factor that can cause significant change in the performance of a campaign and out of the control of a DSP. But it is usually stable with a short term of a few months to a year and exhibits predictable weekly and seasonal patterns. Figure~\ref{fig:periodic} shows an example of periodically changing performance metrics.

Campaign setup also has a significant impact on the performance. For example, the bidding price largely determines the winning chance of a campaign in auctions of its targeted audience. For another example, the budget schedule of a campaign dictates the amount of money available for buying impressions of its targeted audience and the set period of time impressions should be served for the campaign. Notice the campaign setup can be updated by a client at any moment during the lifetime of the campaign, and as a result, the performance of the campaign becomes incomparable before and after the modification of the campaign. An anomaly detection system for such performance metrics must take these modifications into consideration to mitigate potential false positive results.

Last but not least, a DSP itself is the mastermind behind all campaign executions. It is usually implemented as a massive distributed systems running in data centers located at multiple geographic locations. Each component provides a focused group of services as the interface to other components and internally implements the business logic to fulfill the desired functionalities of these services. Different components communicate with messages transmitted through the LAN within a data center or the Internet across different data centers. The complexity comes from the requirements for low latency and high scalability. Any fluctuation on a DSP could cast a significant impact on the performance of campaigns. System enhancements, such as a faster bid request filtering algorithm, could boost the delivery or ROI of campaigns. On the other hand, system issues, such as hardware or software failures, may hurdle the delivery of campaigns or even stop it entirely.

\subsection{Goals}

The goal of our anomaly detection system is to alert for malfunctioning in a DSP in a timely manner so the engineers could investigate and fix the issues before considerable damage is caused.
\begin{itemize}
	\item Ideally, the detection system should only alert for the metric anomalies introduced by a DSP itself, not those caused by traffic fluctuation or campaign configuration.
	\item Secondly, an alert should be triggered within reasonable amount of time, typically a couple of hours since the beginning of an issue.
\end{itemize}
 The latency requirement is a compromise between performance and usability. To get the holistic view of the campaign performance, the anomaly detection system collects data from all campaigns, which imposes overhead to several latency-sensitive core components in the DSP platform, as a result we need to minimize the performance impact by running the detection system less frequently and hence tolerate longer failure-to-detection latencies. Besides, the current detection latency is sufficient to serve as an issue notification mechanism since engineers would usually take hours or even days to fix an issue. The detection latency is hardly the bottleneck in the problem resolving workflow.
\end{comment}


Millions of metrics are being generated constantly for all the campaigns running on Turn's platform, every one of which needs to be monitored and analyzed in real time to identify anomalous behaviors since system issues can occur at any part of the platform. The overhead could easily bring the platform to its knees especially so considering the sub-100-millisecond latency requirement imposed on bidding by ad exchanges. In this section, we present the design of our anomaly detection system which sieves through millions of metrics efficiently to find abnormal behaviors within a reasonable amount of time. The key idea of our design is to apply filtering and aggregation to the metrics before running the anomaly detection algorithm against the resulting data of a much smaller amount.

\begin{figure}
	\centering
	\includegraphics[width=\linewidth]{targetad16-workflow}
	\caption{The Campaign Monitoring and Anomaly Detection Workflow.}\label{fig:workflow}
\end{figure}

As illustrated by Figure~\ref{fig:workflow}, the workflow of the anomaly detection system consists of four steps: (a) identifying stable campaigns by looking at campaign setup and behavior correlation; (b) aggregating the metrics over clusters of stable campaigns; (c) generating and storing time series from the aggregated metrics; (d) detecting anomalies using a simple algorithm designed to identify under-performing metrics. As described in Section~\ref{lbl:DSP-schema}, the control server, as a centralized service that maintains all campaign performance metrics, is the most suitable place to implement the anomaly detection system. The first two steps, stable campaign identification and metric aggregation are running on the control server. Time series data is submitted from a dedicated reporter thread running on the control server and stored in a distributed time series database. Finally, the anomaly detector is deployed as a separate service that ingest time series from the database to find anomalies and alert for system issues.


\subsection{Stable Campaign Identification}

Let $S_{stable}$ denote the set of \emph{stable} campaings. Given a metric, we scan all campaigns periodically and select the appropriate ones to include in (or exclude from) $S_{stable}$. Particularly, all campaigns are included $S_{stable}$ in the beginning, which is then prune through a two-step process detailed in the section. The selection of stable campaigns are refreshed every hour and cached in the memory by the control server.

\begin{table}
	\caption{Stability Checks for Campaign Setup}
	\label{tab:checks}
	\centering
	\begin{tabular}{|l|l|}
		\hline
		\textbf{Name} & \textbf{Requirement} \\
		\hline
		\hline
		Currency & US Dollar \\
		\hline
		Status & Active \\
		\hline
		Duration & > $p$ Days\\
		%\hline
		%Budget & Auto-allocated \\
		\hline
	\end{tabular}
\end{table}

\subsubsection{Campaign Setup}

During the first step, the configurations of all campaigns are checked against a set of pre-defined rules presented Table~\ref{tab:checks}. The campaigns that fail any of these tests in Table~\ref{tab:checks} are removed from $S_{stable}$. The check list is determined primarily based on our experience in tuning numerous campaigns. 

The anomaly detection system considers only US dollar based campaigns because the campaigns the number of campaigns that run on this currency represent a sufficiently large portion of the system. Furthermore, mixing the currencies will add to the already significant noise that the system carries. Note that the intention of this system is to catch system-wide failures and not campaign specific problems.
\begin{comment}
(a) dollar is one of the most dominant currencies among campaigns running on Turn's platform which provides a comprehensive sample of all campaigns; (b) the dollar based campaigns have a more stable and predictable performance since they usually run for a long period and deliver a large number of impressions which would provide enough data points for our model to discern between stable and unstable behaviors; (c) it would add more noise than signal to the data if we mixed campaigns of multiple currencies since they usually base on different time zones hence have distinguish traffic patterns. 
\end{comment}
Furthermore, we only consider active campaigns to monitor the current status of the platform. Therefore the campaigns paused by advertisers or stopped due to budget exhaustion are also excluded from $S_{stable}$. On the other hand, we also avoid the campaigns started a short period ago since there is not much data for us to analyze when the campaigns are still in the optimization mode.


%===Shahriar:remove this part or explain===

%Finally, the campaigns with a manually allocated budget are also skipped since advertisers can make arbitrary changes to the budgets of these campaigns and the resulting behaviors are highly inconsistent over the time.


\subsubsection{Traffic Seasonality}

\begin{figure}
	\centering
	\includegraphics[width=.6\linewidth]{weekly-periodic-usd3}
	\caption{Seasonal Patterns in a Performance Metric.}
	\label{fig:seasonl}
\end{figure}

Now $S_{stable}$ contains only campaigns that have passed all the stability checks for campaign setup mentioned above. However, a stable campaign setup itself does not guarantee a stable performance since the incoming traffic qualified for a given campaign can vary over the time and make the campaign performance difficult to predict. Figure~\ref{fig:seasonl} illustrates the seasonal behaviors over the hour of the day and the day of the week of a performance metric due to traffic seasonality. 

%===Shahriar:the notation is confusing here...what is $l$? what is its relation to $w_1$ and $w_2$?===

To exclude the impact from traffic fluctuation, we compare the behavior of a campaign between two moving windows $w_1$ and $w_2$, each of $l$ hours long, dispersed by a $p$-day period, to determine if the campaign preserves the same behavior over $w_1$ and $w_2$ albeit the traffic patterns. Other things being equal, $w_1$ and $w_2$ should behavior similarly if an $l$-hour-long pattern repeats every $p$ days in the volume of the traffic. For the sake of simplicity, we apply $l=24$ and $p=1,7$ in our system to capture daily and weekly patterns in the traffic. The proper values for $l$ and $p$ can be learned from the time series itself using statistical modeling techniques, which we leave for future exploration.

\begin{figure}
	\centering
	\includegraphics[width=.45\linewidth]{stable}
	\includegraphics[width=.45\linewidth]{unstable}
	\caption{Identify stable campaigns using week-over-week behavior correlations.}\label{fig:stable}
\end{figure}

To quantify the behavior similarity between $w_1$ and $w_2$, we track the performance metric over the two time windows and discretize the curve into two vectors $v_1$ and $v_2$ that consist of hourly aggregated values for $w_1$ and $w_2$, respectively. Let $C_{w_1, w_2, l, p}$ denote the correlation of $v_1$ and $v_2$. We use $C_{w_1, w_2, l, p}$ as the measure of behavior similarity between $w_1$ and $w_2$. Furthermore, campaigns in $S_{stable}$ is filtered using $C_{w_1, w_2, l, p}$ and a constant $0< \delta < 1$ by this inequality:
\begin{align}
C_{w_1, w_2, l, p} > \delta
\end{align}

Since the current hour may exhibit anomalous behavior due to unforeseeable system issues, we introduce a delay of $x$ hours between the end hour of $w_1, w_2$ and the current hour. Essentially, as long as a campaign performs stably till $x$ hours ago, the campaign would be considered to have a correlated behavior by our system.

%The behavior correlation measures not only the stability but also the activeness of a campaign. For campaigns whose impressions are distributed sparsely over the time, it is difficult to observe enough data points to manifest the correlated behavior. In this sense, the behavior correlation is skewed statistic that biases for more active campaigns. This property of the statistic serves our purpose well since the more active campaigns generally have a more stable behavior which makes the occasional anomalies easier to be detected.


\subsection{Change Metric Generation}
\label{sec:metric}

Starting from the set of stable campaigns $S_{stable}$, we split the stable campaigns into clusters and aggregate the raw metrics in each cluster. Metric aggregation is performed over selected clusters of campaigns such that the anomaly detection system can cover different parts of the platform through monitoring the aggregated metrics. Campaigns are clustered according to the criteria used for targeted advertising or the media channels where the ads are served. Because our code base is constructed in a way that each targeting criterion or media channel is handled by a relatively self-sufficient module, we can easily pinpoint an issue in the platform according to the aggregated metrics that manifest the issue. The anomaly detection system considers the most common targeting criteria as listed in Table~\ref{tab:targeting} and four major media channels, namely display, video, mobile and social networks when clustering the campaigns.

\begin{table}
	\caption{Metric Aggregation based on Targeting Criteria of Campaigns}
	\label{tab:targeting}
	\centering
	\begin{tabular}{|l|p{5cm}|}
		\hline
		\textbf{Name} & \textbf{Target}\\
		\hline
		\hline
		Demographic & Users of particular demographic traits, such as age and gender.\\
		\hline
		Contextual & Content category, page quality, brand safety, etc.\\
		\hline
		Behavioral & Users that satisfy certain behavioral rules, e.g. having visited the advertiser's site before.\\
		\hline
		Dayparting & Particular time periods in a day.\\
		\hline
		Device & Particular types of devices, such PC, iOS, Android, etc.\\
		\hline
		Site List & Including or excluding a list of sites.\\
		\hline
	\end{tabular}
\end{table}

%The aggregated time series are formed by applying an aggregation function to all the raw series from a campaign cluster. Given the time series $M_{i,j}$ collected from the $i$-th metric for the $j$-th campaign in a cluster $C$, applying the aggregation function $g$ over the raw metric series collected from $C$ gives the aggregated time series $N_i$ as
%\begin{align}
%N_i = g(\{M_{i,j}|j \in C\})
%\end{align}
%Essentially any function that reduces a vector of values into a scalar can be used as the aggregation function, for example, sum and mean are employed in our detection system.

%===Shahriar: explain the downsampling more clearly. Do you sample only the time points at the specific hour or you are summing up everything within an hour? ====

Downsampling is then performed on the aggregated time series to reduce to one data point per hour by summing up all data points within every hour. In doing so we preserve sufficient information for detecting anomalous behaviors within a couple of hours while avoiding the overhead that would incur if the original time series were transferred and analyzed. The sampled time series is transformed into a differential series by taking the difference of the metric between each pair of data points whose timestamps differ by $p$ days. We call the hourly differential time series \emph{change metric} to distinguish from the raw performance metric. The change metric is the final form of the data which is then stored in the time series database.


\subsection{Time Series Storage}

Time series are generated on the control server and then submitted to OpenTSDB~\cite{opentsdb}, a distributed time series database built on top of HBase~\cite{hbase}. OpenTSDB serves the persistence layer for the time series data and the feed for the anomaly detector.

Each sample in the time series consists of the timestamp when the entry is submitted, the value of the metric and a list of tags. The timestamps are written with second resolution. In case of duplicated data points for the same timestamp, the most recent value is recorded. Tags are a set of optional key-value pairs associated with the time series to provide additional information about the aggregation. Samples of the time series are taken periodically by the dedicated reporter thread on the control server and submitted to OpenTSDB through HTTP messages. A message begins with the operation name, followed by the metric name, the timestamp and the metric value, finally ends with the list of tags, as illustrated by the example below:
\begin{lstlisting}
   put proc.net.tcp.connections 1417642359 2 remote_host=50.116.234.5 direction=in state=established domain=sjc2 host=app454
\end{lstlisting}
The reporter thread collects data for the lightweight metrics in real time and reads the resource-intensive metrics from a cache refreshed less frequently by the control server to prevent performance degradation in the mission-critical parts of the control server, such as budget enforcement which deals with money.

OpenTSDB is deployed in a dedicated cluster to provide a scalable and reliable store for the enormous amount of time series data generated by thousands of machines in our production system. Upon the arrival of each sample, it performs compression to generate more compacted data that is faster to query and more suitable for dashboards and graphs spanning more than a few hours of data. OpenTSDB provides a convenient user interface for querying and visualizing the stored time series. It also supplies a set of HTTP APIs that enable querying, inserting and deleting the data in batches. Our anomaly detector is one of the consumers of the time series data stored in the OpenTSDB cluster and employs the batch APIs to fetch the data set to analyze.


\subsection{Anomaly Detection}

In this subsection, we describe our standard anomaly detection algorithm applied onto the change metric defined in Section~\ref{sec:metric}. The algorithm is presented in Table \ref{alg:anomaly-detect}. We assume a Gaussian distribution, $N(\mu, \sigma)$, on the input time series, that is $d_t, \forall t$. Essentially, the algorithm denotes a $d_i$ as anomalous if $|d_i-\mu| > \beta \sigma$ where $0\leq \beta \leq 3$ is a parameter that depends on the discovered anomalies. To make the algorithms more robust, one needs to limit its memory. To accomplish this, we use a decaying factor, namely $0 \leq \alpha \leq 1$, to smoothly discount the past during the calculation of running sum of time points. Therefore, the algorithm can easily be applied to any time-series and requires us to keep only three variables in the memory.
\begin{algorithm}
	\caption{Anomaly detection algorithm}
	\begin{algorithmic}
		\STATE{\textbf{Input}}
		\STATE{$d_t$}
		\STATE{\textbf{Initialization}}\\
		\STATE{$\mathcal{X},\mathcal{X}^2,n$}
		\WHILE{$d_t$ is valid}
		\STATE{$\mu = \frac{\mathcal{X}}{n}$,$\sigma=\sqrt{\frac{\mathcal{X}^2}{n}-\left(\frac{\mathcal{X}}{n}\right)^2}$}
	
		\IF{$|d_t-\mu| > \beta \sigma$}
		\IF{$d_t < 0$}
		\STATE{$a_t = Anomaly$}
		\STATE{$shrink(\beta)$}
		\ENDIF
		\ELSE
		\STATE{$\mathcal{X}= \alpha \mathcal{X} + d_t$}
		\STATE{$\mathcal{X}^2=\alpha \mathcal{X}^2+d_t^2$}
		\STATE{$n = \alpha n + 1$}
		\ENDIF
		\ENDWHILE
	\end{algorithmic}
	\label{alg:anomaly-detect}
\end{algorithm}

The initialization phase of the algorithm takes a small initial part of the time series as the training data and estimates the values for $\mathcal{X}, \mathcal{X}^2, n$ based on the training data which is assumed anomaly-free. In the main loop of the algorithm, $\mathcal{X}, \mathcal{X}^2, n$ are updated for every data points falling within the $\mu \pm \beta \sigma$ range. Note only the negative outliers are deemed true anomalies and decrease the range of normal data points by shrinking $\beta$, the rest including both normal data points and positive outliers are considered normal by the algorithm. The focus of our work is on detecting anomalies when they indicate a negative change. While a positive change can be anomalous as well, they are controlled and detected by other systems. For instance, if we start receiving abnormally large number of clicks, then our fraud detection modules start to investigate the issue. Therefore, our system follows an asymmetric  design that focuses on \emph{under-performing}. Also, a sudden jump is system's performance metrics is expected when an issue is resolved.
\begin{comment}
This asymmetric design is because the majority of time series we are monitoring in Turn's platform are performance metrics of campaigns, for which under-performing is anomalous while outperforming is welcomed and sometime expected as soon as a system issue is resolved for under-delivered campaigns. 
\end{comment}
We use $\beta$ as the shrinkage for the normal range and diminish the range proportionally according to the percentage of anomalies detected in a moving window. Denote $N_{normal}$ the number of normal points in the window and $N_{abnormal}$ the number of anomalies. Then $\beta$ is updated in function $shrink(\beta)$ as follows:

%==Shahriar: Is this correct? it means that $\beta$ will never recover...you start from $\beta=3$ and at the end you reach, let's say $\beta=2.5$, then it will stay at $\beta=2.5$ for ever. ====

\begin{align}
\beta = 3 \cdot \frac{N_{normal}}{N_{normal} + N_{abnormal}}
\end{align}


eval.tex
\section{Evaluation}
\label{sec:eval}

\begin{figure*}[tbhp]
	\includegraphics[width=\linewidth]{underspend_detection_3sigma_annotated}
	\caption{The anomaly detection algorithm is applied to a real performance metric collected over three months. \textcolor{red}{Red} boxes highlight the periods in which the incidents occurred. \textcolor{green}{Green} diamonds are the data points flagged as anomalous by our tool. The upper and lower bounds are determined by $\mu \pm \beta \sigma$ in Algorithm~\ref{alg:anomaly-detect}.}
	\label{fig:anomaly-detection}
	\vspace{-0.5cm}
\end{figure*}
\begin{comment}
Our anomaly detection system was deployed in production since June 2015 and has successfully alarmed for two major system problems in the platform since its debut. In this section, we present an preliminary evaluation of the anomaly detection system using the data from a real performance metric collected from the last week of June to the end of September.
\end{comment}
This section presents our experience applying the anomaly detection system to a real performance metric during a period in which four incidents were discovered by the tool. Two of the issues were transient and resolved by themselves. The other two issues were caused by program errors. Three of the incidents lasted for less than a day, while the last one got fixed a week after its inception. Our tool successfully detected all four issues and demonstrated its robustness against both short-living and long-lasting issues. The final change metric retrieved by the anomaly detector consists of 2185 data points, out of which 160 points are anomalous as they concur with system issues in time. One week worth of data is used as the training data to initialize the anomaly detection algorithm and the rest of the data is used to evaluate the performance of the system. Note we omit the numbers and exact timestamps associated with the metrics in the results presented here to comply with the company's regulations.

\subsection{Metric Stability}

We compare the metrics obtained from all campaigns running on Turn's platform and those including only stable campaigns. The day-over-day change metrics (i.e. $p=1$) in Figure~\ref{fig:compare-daily-metric} is evidently more informative than the all-campaign metric in Figure~\ref{fig:compare-daily-all} regarding the occurrences of system issues. The week-over-week change metrics (i.e. $p=7$) in Figure~\ref{fig:compare-weekly-metric} shows a highly stabilized behavior which leaves the negative spikes caused by system issues apparent to identify. On the contrary, the week-over-week all-campaign metric in Figure~\ref{fig:compare-weekly-all} reveals little information about system health as it is contaminated by strong noise. In our final configuration of the anomaly detection system, we use the week-over-week metric in Figure~\ref{fig:compare-weekly-metric} as the input to the detector.

\begin{figure}[tbhp]
	\centering
	\subfigure[A day-over-day metric that includes all campaigns.]{%
		\includegraphics[width=\linewidth]{daily-all-3m}\label{fig:compare-daily-all}%
	}
	\subfigure[Day-over-day change metrics that include only stable campaigns.]{%
		\includegraphics[width=\linewidth]{daily-metric-3m}\label{fig:compare-daily-metric}%
	}
	\caption{The daily metrics are unstable in general due to traffic fluctuation during the course of the week, and difficult to correlate with the occurrence of system issues.}
\end{figure}

\begin{figure}[tbhp]
	\centering
	\subfigure[A week-over-week metric that includes all campaigns.]{%
		\includegraphics[width=\linewidth]{weekly-all-3m}\label{fig:compare-weekly-all}%
	}
	\subfigure[Week-over-week change metrics that include only stable campaigns.]{%
		\includegraphics[width=\linewidth]{weekly-metric-3m}\label{fig:compare-weekly-metric}%
	}
	\caption{The weekly metrics from stable campaigns are highly correlated with prior system issues.}
\end{figure}

\subsection{Accuracy}

We also evaluate the accuracy of the anomaly detection system using the same data set described above. The week-over-week change metric derived from the original time series is used for the numbers presented here. We employ the standard $F_1$ measure defined in Equation~\ref{eq:f1} to quantify the accuracy of the anomaly detection system. In Equation~\ref{eq:f1}, \emph{precision} denotes the ratio of true anomalies among all detected data points, and \emph{recall} the percentage of anomalies that are detected.
\begin{align}
\var{F_1-Score} = 2 \cdot \frac{Precision \cdot Recall}{Precision + Recall}\label{eq:f1}
\end{align}
Figure~\ref{fig:anomaly-detection} illustrates the result of the experiment: 157 true anomalies and 12 false positives are identified and 3 anomalies missed. The system has a precision of 92.9\% and a recall of 98.1\%. The $F_1$ measure is 0.954 based on the precision and the recall. The false positives are mostly borderline cases which overlay or slightly exceed the lower bound for anomaly detection, while all of the missed anomalies locate close to the beginning of incidents when it is difficult to discern between normal and abnormal behaviors based on metrics.


\section{Conclusion}
\label{sec:conclusion}

We present an anomaly detection system that identifies system issues based on self-correlated behavior of stable campaigns in a large-scale DSP. The system has been deployed in our production cluster and successfully detected several major system problems which otherwise would not be discovered until severe consequences are caused.
acmTargetAd.bbl
\begin{thebibliography}{10}

\bibitem{hbase}
{Apache HBase}.
\newblock \url{https://hbase.apache.org/}.

\bibitem{opentsdb}
{OpenTSDB}.
\newblock \url{http://opentsdb.net/}.

\bibitem{Chandola09}
V.~Chandola, A.~Banerjee, and V.~Kumar.
\newblock Anomaly detection: A survey.
\newblock {\em ACM computing surveys (CSUR)}, 41(3):15, 2009.

\bibitem{Chandola12}
V.~Chandola, A.~Banerjee, and V.~Kumar.
\newblock Anomaly detection for discrete sequences: A survey.
\newblock {\em Knowledge and Data Engineering, IEEE Transactions on},
  24(5):823--839, 2012.

\bibitem{Geyik14}
S.~C. Geyik, A.~Saxena, and A.~Dasdan.
\newblock Multi-touch attribution based budget allocation in online
  advertising.
\newblock In {\em ADKDD}, 2014.

\bibitem{Laptev15}
N.~Laptev, S.~Amizadeh, and I.~Flint.
\newblock Generic and scalable framework for automated time-series anomaly
  detection.
\newblock In {\em SIGKDD}, 2015.

\bibitem{Lee12}
K.-C. Lee, B.~Orten, A.~Dasdan, and W.~Li.
\newblock Estimating conversion rate in display advertising from past
  erformance data.
\newblock In {\em SIGKDD}, 2012.

\bibitem{Shariat15}
S.~Shariat, B.~Orten, and A.~Dasdan.
\newblock Online model evaluation in a large-scale computational advertising
  platform.
\newblock In {\em ICDM}, 2015.

\bibitem{Xu15}
J.~Xu, K.-C. Lee, W.~Li, H.~Qi, and Q.~Lu.
\newblock Smart pacing for effective online ad campaign optimization.
\newblock In {\em SIGKDD}, 2015.

\bibitem{Yuan14}
Y.~Yuan, F.~Wang, J.~Li, and R.~Qin.
\newblock A survey on real time bidding advertising.
\newblock In {\em SOLI}, 2014.

\end{thebibliography}
