Selecting the right audience for an advertising campaign is one of the most challenging, time-consuming and costly steps in the advertising process. To target the right audience, advertisers usually have two options: a) market research to identify user segments of interest and b) sophisticated machine learning models trained on data from past campaigns. In this paper we study how demand-side platforms (DSPs) can leverage the data they collect (demographic and behavioral) in order to learn reputation signals about end user convertibility and advertisement (ad) quality. In particular, we propose a reputation system which learns interest scores about end users, as an additional signal of ad conversion, and quality scores about ads, as a signal of campaign success. Then our model builds user segments based on a combination of demographic, behavioral and the new reputation signals and recommends transparent targeting rules that are easy for the advertiser to interpret and refine. We perform an experimental evaluation on industry data that showcases the benefits of our approach for both new and existing advertiser campaigns.

Online media provides opportunities for marketers through which they can deliver effective brand messages to a wide range of audiences at scale. Advertising technology platforms enable advertisers to reach their target audience by delivering ad impressions to online users in real time. In order to identify the best marketing message for a user and to purchase impressions at the right price, we rely heavily on bid prediction and optimization models. Even though the bid prediction models are well studied in the literature, the equally important subject of model evaluation is usually overlooked or not discussed in detail. Effective and reliable evaluation of an online bidding model is crucial for making faster model improvements as well as for utilizing the marketing budgets more efficiently. In this paper, we present an experimentation framework for bid prediction models where our focus is on the practical aspects of model evaluation. Specifically, we outline the unique challenges we encounter in our platform due to a variety of factors such as heterogeneous goal definitions, varying budget requirements across different campaigns, high seasonality and the auction-based environment for inventory purchasing. Then, we introduce return on investment (ROI) as a unified model performance (i.e., success) metric and explain its merits over more traditional metrics such as click-through rate (CTR) or conversion rate (CVR). Most importantly, we discuss commonly used evaluation and metric summarization approaches in detail and propose a more accurate method for online evaluation of new experimental models against the baseline. Our meta-analysis-based approach addresses various shortcomings of other methods and yields statistically robust conclusions that allow us to conclude experiments more quickly in a reliable manner. We demonstrate the effectiveness of our evaluation strategy on real campaign data through some experiments.

Real-Time Bidding allows an advertiser to purchase media inventory through an auction system that unfolds in the order of milliseconds. Media providers are increasingly being integrated into such programmatic buying platforms. It is typical for a contemporary Real-Time Bidding system to receive millions of bid requests per second at peak time, and have a large portion of these to be irrelevant to any advertiser. Meanwhile, given a valuable bid request, tens of thousands of advertisements might be qualified for scoring. We present our efforts in building selection models for both bid requests and advertisements to handle this scalability challenge. Our bid request model treats the system load as a hierarchical resource allocation problem and directs traffic based on the estimated quality of bid requests. Next, our exploration/exploitation advertisement model selects a limited number of qualified advertisements for thorough scoring based on the expected value of a bid request to the advertiser given its features. Our combined bid request and advertisement model is able to win more auctions and bring more value to clients by stabilizing the bidding pipeline. We empirically show that our deployed system is capable of handling 5x more bid requests.

We study online meta-learners for real-time bid prediction that predict by selecting a single best predictor among several subordinate prediction algorithms, here called "experts". These predictors belong to the family of context-dependent past performance estimators that make a prediction only when the instance to be predicted falls within their areas of expertise. Within the advertising ecosystem, it is very common for the contextual information to be incomplete, hence, it is natural for some of the experts to abstain from making predictions on some of the instances. Experts' areas of expertise can overlap, which makes their predictions less suitable for merging; as such, they lend themselves better to the problem of best expert selection. In addition, their performance varies over time, which gives the expert selection problem a non-stochastic, adversarial flavor. In this paper we propose to use probability sampling (via Thompson Sampling) as a meta-learning algorithm that samples from the pool of experts for the purpose of bid prediction. We show performance results from the comparison of our approach to multiple state-of-the-art algorithms using exploration scavenging on a log file of over 300 million ad impressions, as well as comparison to a baseline rule-based model using production traffic from a leading DSP platform.

In digital advertising, advertisers want to reach the right audience over media channels such as display, mobile, video, or social at the appropriate cost. The right audience for an advertiser consists of existing customers as well as valuable prospects, those that can potentially be turned into future customers. Identifying valuable prospects is called the audience extension problem because advertisers find new customers by extending the desirable criteria for their starting point, which is their existing audience or customers. The complexity of the audience extension problem stems from the difficulty of defining desirable criteria objectively, the number of desirable criteria (such as similarity, diversity, performance) to simultaneously satisfy, and the expected runtime (a few minutes) to find a solution over billions of cookie-based users. In this paper, we formally define the audience extension problem, propose an algorithm that extends a given audience set efficiently under multiple desirable criteria, and experimentally validate its performance. Instead of iterating over individual users, the algorithm takes in Boolean rules that define the seed audience and returns a new set of Boolean rules that corresponds to the extended audience that satisfy the multiple criteria.

This paper gives an overview of Turn Data Management Platform (DMP). We explain the purpose of this type of platforms, and show how it is positioned in the current digital advertising ecosystem. We also provide a detailed description of the key components in Turn DMP. These components cover the functions of (1) data ingestion and integration, (2) data warehousing and analytics, and (3) real-time data activation. For all components, we discuss the main technical and research challenges, as well as the alternative design choices. One of the main goals of this paper is to highlight the central role that data management is playing in shaping this fast growing multi-billion dollars industry.

In targeted display advertising, the goal is to identify the best opportunities to display a banner ad to an online user who is most likely to take a desired action such as purchasing a product or signing up for a newsletter. Finding the best ad impression, i.e., the opportunity to show an ad to a user, requires the ability to estimate the probability that the user who sees the ad on his or her browser will take an action, i.e., the user will convert. However, conversion probability estimation is a challenging task since there is extreme data sparsity across different data dimensions and the conversion event occurs rarely. In this paper, we present our approach to conversion rate estimation which relies on utilizing past performance observations along user, publisher and advertiser data hierarchies. More specifically, we model the conversion event at different select hierarchical levels with separate binomial distributions and estimate the distribution parameters individually. Then we demonstrate how we can combine these individual estimators using logistic regression to accurately identify conversion events. In our presentation, we also discuss main practical considerations such as data imbalance, missing data, and output probability calibration, which render this estimation problem more difficult but yet need solving for a real-world implementation of the approach. We provide results from real advertising campaigns to demonstrate the effectiveness of our proposed approach.

Search engines are important resources for finding information on the Web. They are also important for publishers and advertisers to present their content to users. Thus, user satisfaction is key and must be quantified. In this tutorial, we give a practical review of web search metrics from a user satisfaction point of view. We cover metrics for relevance, comprehensiveness, coverage, diversity, discovery freshness, content freshness, and presentation. We will also describe how these metrics can be mapped to proxy metrics for the stages of a generic search engine pipeline. The practitioners can apply these metrics readily and the researchers can get motivation for new problems to work on, especially in formalizing and refining metrics.

Microblogging as introduced by Twitter is becoming a source of tracking real-time news. Although identifying the highest quality or most useful posts or tweets from Twitter for breaking news is still an open problem, major web search engines seem convinced of the value of such posts and have already started allocating part of their search results pages to them. In this paper, we study a different aspect of the problem for a search engine: instead of the value of the posts, we study the value of the (shortened) URLs referenced in these posts. Our results indicate that unlike frequently bookmarked URLs, which are generally of high quality, frequently tweeted URLs tend to fall in two opposite categories: they are either high in quality, or they are spam. Identifying the quality category of a URL is not trivial, but the combination of characteristics can reveal some trends.

Output URL bidding is a new bidding mechanism for sponsored search, where advertisers bid on search result URLs, as opposed to keywords in the input query. For example, an advertiser may want his ad to appear whenever the search result includes the sites www.imdb.com and en.wikipedia.org, instead of bidding on keywords that lead to these sites, e.g., movie titles or actor names. In this paper we study the tradeoff between the simplicity and the specification power of output bids and we explore their utility for advertisers. We first present a model to derive output bids from existing keyword bids. Then, we use the derived bids to experimentally study output bids and contrast them to input query bids. Our main results are the following: (1) Compact output bids that mix both URLs and hosts have the same specification power as more lengthy input bids; (2) Output bidding can increase the recall of relevant queries; and (3) Output and input biding can be combined into a hybrid mechanism that combines the benefits of both.

We consider the coverage testing problem where we are given a document and a corpus with a limited query interface and asked to find if the corpus contains a near-duplicate of the document. This problem has applications in search engines for competitive coverage testing. To solve this problem, we propose approaches that work in three main steps: generate a query signature from the document, query the corpus using the query signature and scrape the returned results, and validate the similarity between the input document and the returned results. We discuss techniques to control and bound the performance of these methods. We perform large-scale experimental validation and show that these methods perform well across different search engine corpora and documents in multiple languages. They also are robust against performance parameter variations.

We study non-parametric measures for the problem of comparing distributions, which arise in anomaly detection for continuous time series. Non-parametric measures take two distributions as input and produce two numbers as output: the difference between the input distributions and the statistical significance of this difference. Some of these measures, such as Kullback-Leibler measure, are defined for comparing probability distribution functions (PDFs) and some others, such as Kolmogorov-Smirnov measure, are for cumulative distribution functions (CDFs). We first show how to adapt the PDF based measures to compare CDFs, resulting in a total of 23 CDF based measures. We then provide a unified functional form that subsumes all these measures. We present our methodology to determine the significance (of the measures) by simulations only. Finally, we evaluate these measures for the anomaly detection in continuous time series.

Human computation is an effective way to channel human effort spent playing games to solving computational problems that are easy for humans but difficult for computers to automate. We propose Thumbs-Up, a new game for human computation with the purpose of playing to rank search result. Our experience from users shows that Thumbs-Up is not only fun to play, but produces more relevant rankings than both a major search engine and optimal rank aggregation using the Kemeny rule.

In order to return relevant search results, a search engine must keep its local repository synchronized to the Web, but it is usually impossible to attain perfect freshness. Hence, it is vital for a production search engine continually to monitor and improve repository freshness. Most previous freshness metrics, formulated in the context of developing better synchronization policies, focused on the web crawler while ignoring other parts of a search engine. But, the freshness of documents in a web crawler does not necessarily translate directly into the freshness of search results as seen by users. We propose metrics for measuring freshness from a user’s perspective, which take into account the latency between when documents are crawled and when they are viewed by users, as well as the variation in user click and view frequency among different documents. We also describe a practical implementation of these metrics that were used in a production search engine.

Social bookmarking has emerged as a growing source of human generated content on the web. In essence, bookmarking involves URLs and tags on them. In this paper, we perform a large scale study of the usefulness of bookmarked URLs from the top social bookmarking site Delicious. Instead of focusing on the dimension of tags, which has been covered in the previous work, we explore social bookmarking from the dimension of URLs. More specifically, we investigate the Delicious URLs and their content to quantify their value to a search engine. For their value in leading to good content, we show that the Delicious URLs have higher quality content and more external outlinks. For their value in satisfying users, we show that the Delicious URLs have more clicked URLs as well as get more clicks. We suggest that based on their value, the Delicious URLs should be used as another source of seed URLs for crawlers.

A system of difference constraints is a formal model of temporal and spatial constraints in many areas such as scheduling, constraint satisfaction, and layout compaction. During construction of such a system, constraint violations often arise, and they need to be resolved. Previous algorithms for this task fall into two groups: those algorithms that are fast but cannot resolve all violations, and those algorithms that can resolve all violations but are exponentially slow. We propose the first algorithms that are fast as well as able to resolve all violations. Moreover, unlike the previous algorithms, our algorithms support the ordering of violations using their inherent criticality or user-defined priority. We provably and experimentally justify the efficiency and efficacy of our algorithms.

Web graphs are approximate snapshots of the web, created by search engines. Their creation is an error-prone procedure that relies on the availability of Internet nodes and the faultless operation of multiple software and hardware units. Checking the validity of a web graph requires a notion of graph similarity. Web graph similarity helps measure the amount and significance of changes in consecutive web graphs. These measurements validate how well search engines acquire content from the web. In this paper we study five similarity schemes: three of them adapted from existing graph similarity measures and two adapted from well-known document and vector similarity methods. We compare and evaluate all five schemes using a sequence of web graphs for Yahoo! and study if the schemes can identify anomalies that may occur due to hardware or other problems.

Parasitic interconnect corner methods are known to be inaccurate. This paper explains the sources of their errors and shows that errors in excess of 22% can occur in the predicted corner delays of a multi-layer stage in the presence of process variations. It is shown that exhaustive corner search methods are infeasible in practice as they have an exponential complexity in terms of required SPICE simulations with respect to the number of layers a stage is routed through. This exponential complexity is reduced to a linear one with a new simulation-based search method with the aid of stage delay properties. The ideas behind the simulation-based methodology are shown to be expandable to an analytical-based multi-layer performance corner location methodology. The simulated best/worst case delays based on these analytical corners produce errors below 4% as compared to the exhaustive search simulation based method.

Map-Reduce is a programming model that enables easy development of scalable parallel applications to process a vast amount of data on large clusters of commodity machines. Through a simple interface with two functions, map and reduce, this model facilitates parallel implementation of many real-world tasks such as data processing jobs for search engines and machine learning.

A methodology is proposed to exploit the interdependence between setup- and hold-time constraints in static timing analysis (STA). The methodology consists of two phases. The first phase includes the interdependent characterization of sequential cells, resulting in multiple constraint pairs. The second phase includes an efficient algorithm that exploits these multiple pairs in STA. The methodology improves accuracy by removing optimism and reducing unnecessary pessimism. Furthermore, the tradeoff between setup and hold times is exploited to significantly reduce timing violations in STA. These benefits are validated using industrial circuits and tools, exhibiting up to 53% reduction in the number of constraint violations as well as up to 48% reduction in the worst negative slack, which corresponds to a 15% decrease in the clock period

This paper introduces a fast analytical model for determining accurate parasitic values for best- and worst-case delays of a stage under interconnect process variations. The inputs to the model are the nominal values for each interconnect and device parameter and the amount of variation in each interconnect parameter. The outputs of the model are the interconnect parameter dimensions within the range of process variation that yield the best- and worst-case delay of a stage. Simulations show that our model accurately predicts the performance corners of a stage while those predicted by traditional best/worst-case analysis methodologies can have an error of up to 28.42%.

In digital circuit design, it is typically assumed that cell delay increases with decreasing voltage and increasing temperature. This assumption is the basis of the cornering approach with cell libraries in static timing analysis (STA). However, this assumption breaks down at low supply voltages because cell delay can decrease with increasing temperature. This phenomenon is caused by a competition between mobility and threshold voltage to dominate cell delay. We refer to this phenomenon as the inverted temperature dependence (ITD). Due to ITD, it becomes very difficult to analytically determine the temperatures that maximize or minimize the delay of a cell or a path. As such, ITD has profound consequences for STA: (1) ITD essentially invalidates the approach of defining corners by independently varying voltage and temperature; (2) ITD makes it more difficult to find short paths, leading to difficulties in detecting hold time violations; and (3) the effect of ITD will worsen as supply voltages decrease and threshold voltage variations increase. This article analyzes the consequences of ITD in STA and proposes a proper handling of ITD in an industrial sign-off STA tool. To the best of our knowledge, this article is the first such work.

Optimum cycle ratio (OCR) algorithms are fundamental to the performance analysis of (digital or manufacturing) systems with cycles. Some applications in the computer-aided design field include cycle time and slack optimization for circuits, retiming, timing separation analysis, and rate analysis. There are many OCR algorithms, and since a superior time complexity in theory does not mean a superior time complexity in practice, or vice-versa, it is important to know how these algorithms perform in practice on real circuit benchmarks. A recent published study experimentally evaluated almost all the known OCR algorithms, and determined the fastest one among them. This article improves on that study in the following ways: (1) it focuses on the fastest OCR algorithms only; (2) it provides a unified theoretical framework and a few new results; (3) it runs these algorithms on the largest circuit benchmarks available; (4) it compares the algorithms in terms of many properties in addition to running times such as operation counts, convergence behavior, space requirements, generality, simplicity, and robustness; (5) it analyzes the experimental results using statistical techniques and provides asymptotic time complexity of each algorithm in practice; and (6) it provides clear guidance to the use and implementation of these algorithms together with our algorithmic improvements.

The goal of this paper is to identify the most efficient algorithms for the optimum mean cycle and optimum cost to time ratio problems and compare them with the popular ones in the CAD community.These problems have numerous important applications in CAD, graph theory, discrete event system theory, and manufacturing systems.In particular, they are fundamental to the performance analysis of digital systems such as synchronous, asynchronous, dataflow, and embedded real-time systems.For instance, algorithms for these problems are used to compute the cycle period of any cyclic digital system.Without loss of generality, we discuss these algorithms in the context of the minimum mean cycle problem (MCMP).We performed a comprehensive experimental study of ten leading algorithms for MCMP.We programmed these algorithms uniformly and efficiently.We systematically compared them on a test suite composed of random graphs as well as benchmark circuits.Above all, our results provide important insight into the performance of these algorithms in practice.One of the most surprising results of this paper is that Howard's algorithm, known primarily in the stochastic control community, is by far the fastest algorithm on our test suite although the only known bound on its running time is exponential.We provide two stronger bounds on its running time.

An embedded system (the system) continuously interacts with its environment under strict timing constraints, called the external constraints, and it is important to know how these external constraints translate to time budgets, called the internal constraints, on the tasks of the system. Knowing these time budgets reduces the complexity of the system's design and validation problem and helps the designers have a simultaneous control on the system's functional as well as temporal correctness from the beginning of the design ow. The translation is carried out by rst deriving the rate of each task in the system, hence the term \\rate derivation", using the system's task structure and the rates of the input stimuli coming into the system from its environment. The derived task rates are later used to derive and validate the rest of the internal as well as external constraints. This paper proposes a general task graph model to represent the system's task structure, techniques for deriving and validating the system's timing constraints, and a hardware/software codesign methodology that puts everything together. 1 1

Maximum and minimum mean cycle problems are important problems with many applications in performance analysis of synchronous and asynchronous digital systems including rate analysis of embedded systems, in discrete-event systems, and in graph theory. Karp's algorithm is one of the fastest and most common algorithms for these problems. We present this paper mainly in the context of the maximum mean cycle problem. We show that Karp's algorithm processes more nodes and arcs than needed to find the maximum cycle mean of a digraph. This observation motivated us to propose a new graph-unfolding scheme that remedies this deficiency and leads to two faster algorithms with different characteristics. Theoretical analysis tells us that our algorithms always run faster than Karp's algorithm and that they are among the fastest to date. Experiments on small benchmark graphs confirm this fact for most of the graphs. These algorithms have been used in building a framework for analysis of timing constraints for embedded systems.

We address the problem of timing constraint derivation and validation for reactive and real-time embedded systems. We assume that such a system is structured into its tasks, and the structure is modeled using a task graph. Our solution uses the timing behavior committed by the environment to the system first to derive the timing constraints on the system's internal behavior and then use them to derive and validate the timing constraints on the system's external behavior. Our solution consists of the following contributions: a generalized task graph model, a comprehensive classification of timing constraints, algorithms for derivation and validation of timing constraints of the system modeled in the generalized task graph model, a codesign methodology that combines the model and the algorithms, and the implementation of this methodology in a tool called RADHA-RATAN. The main advantages of our solution are that it simplifies the problem of ensuring timing correctness of the system by reducing the complexity of the problem from system level to task level, and that it makes the codesign methodology timing-driven in that our solution makes it possible to maintain a handle on the system's timing correctness from very early stages in the system's design flow.

Embedded systems consist of interacting components that are required to deliver a specific functionality under constraints on execution rates and relative time separation of the components. In this article, we model an embedded system using concurrent processes interacting through synchronization. We assume that there are rate constraints on the execution rates of processes imposed by the designer or the environment of the system, where the execution rate of a process is the number of its executions per unit time. We address the problem of computing bounds on the execution rates of processes constituting an embedded system, and propose an interactive rate analysis framework. As part of the rate analysis framework we present an efficient algorithms for checking the consistency of the rate constraints. Bounds on the execution rate of each process are computed using an efficient algorithm based on the relationship between the execution rate of a process and the maximum mean delay cycles in the process graph. Finally, if the computed rates violate some of the rate constraints, some of the processes in the system are redesigned using information from the rate analysis step. This rate analysis framework is implemented in a tool called RATAN. We illustrate by an example how RATAN can be used in an embedded system design.

We propose a machine architecture that integrates programmable logic into key components of the system with the goal of customizing architectural mechanisms and policies to match an application. This approach presents an improvement over the traditional approach of exploiting programmable logic as a separate co-processor by pre-serving machine usability through software and on a traditional computer architecture by providing application-specific hardware. We present two case studies of architectural customization to enhance latency tolerance and efficiently utilize network bisection on multiprocessors for sparse matrix computations. We demonstrate that application-specific hardware and policies can provide substantial improvements in performance on a per application basis. Based on these preliminary results, we propose that an application-driven machine customization provides a promising approach to achieve high performance and combat performance fragility.

All the previous Kernighan-Lin-based (KL-based) circuit partitioning algorithms employ the locking mechanism, which enforces each cell to move exactly once per pass. In this paper, we propose two novel approaches for multiway circuit partitioning to overcome this limitation. Our approaches allow each cell to move more than once. Our first approach still uses the locking mechanism but in a relaxed way. It introduces the phase concept such that each pass can include more than one phase, and a phase can include at most one move of each cell. Our second approach does not use the locking mechanism at all. It introduces the mobility concept such that each cell can move as freely as allowed by its mobility. Each approach leads to KL-based generic algorithms whose parameters can be set to obtain algorithms with different performance characteristics. We generated three versions of each generic algorithm and evaluated them on a subset of common benchmark circuits in comparison with Sanchis' algorithm (FMS) and the simulated annealing algorithm (SA). Experimental results show that our algorithms are efficient, they outperform FMS significantly, and they perform comparably to SA. Our algorithms perform relatively better as the number of parts in the partition increases as well as the density of the circuit decreases. This paper also provides guidelines for good parameter settings for the generic algorithms.