In-app advertising is a complex market worth billions of dollars per year, yet it has been studied significantly less than traditional web display ads. In this paper we study an important but often overlooked feature of ads in mobile apps (mostly absent in traditional web ads), that of ad refreshes : A user is shown a stream of banner ads during the app session, in which each ad is displayed in the ad slot for a certain amount of time (the refresh rate) before the ad-slot is refreshed to the next ad. Data analysis on our large-scale experiments that vary refresh rates reveals a surprising result, that cannot be explained by existing user click models: Varying ads» refresh almost preserves total number of clicks. We propose a new, natural, "two-phase" click model for this setting that explains this independence, as well as our measurements of the click-through rate as a function of the impression»s time-on-screen and of ad-repeat counts. The new click model leads to a clean formulation of the problem of auctioning the entire user-session: i.e., determining online, both the sequence of winning ads as well as the amount of time to display each one. We complement the theoretical auction design with results from a live-traffic experiment with its implementation. Our experiments and analysis provide the theoretical foundation for AdMob»s "Google-optimized refresh rate" feature, used by many mobile apps for better monetization of ads shown to millions of users.

We study time-critical search, where users have urgent information needs in the context of an acute problem. As examples, users may need to know how to stem a severe bleed, help a baby who is choking on a foreign object, or respond to an epileptic seizure. While time-critical situations and actions have been studied in the realm of decision-support systems, little has been done with time-critical search and retrieval, and little direct support is offered by search systems. Critical challenges with time-critical search include accurately inferring when users have urgent needs and providing relevant information that can be understood and acted upon quickly. We leverage surveys and search log data from a large mobile search provider to (a) characterize the use of search engines for time-critical situations, and (b) develop predictive models to accurately predict urgent information needs, given a query and a diverse set of features spanning topical, temporal, behavioral, and geospatial attributes. The methods and findings highlight opportunities for extending search and retrieval to consider the urgency of queries.

Circumlocution is when many words are used to describe what could be said with fewer, e.g., "a machine that takes moisture out of the air" instead of "dehumidifier." Web search is a perfect backdrop for circumlocution where people struggle to name what they seek. In some domains, not knowing the correct term can have a significant impact on the search results that are retrieved. We study the medical domain, where professional medical terms are not commonly known and where the consequence of not knowing the correct term can impact the accuracy of surfaced information, as well as escalation of anxiety, and ultimately the medical care sought. Given a free-form colloquial health search query, our objective is to find the underlying professional medical term. The problem is complicated by the fact that people issue quite varied queries to describe what they have. Machine-learning algorithms can be brought to bear on the problem, but there are two key complexities: creating high-quality training data and identifying predictive features. To our knowledge, no prior work has been able to crack this important problem due to the lack of training data. We give novel solutions and demonstrate their efficacy via extensive experiments, greatly improving over the prior art.

One of the most important innovations of social networking websites is the notion of a "feed", a sequence of news items presented to the user as a stream that expands as the user scrolls down. The common method for monetizing such streams is to insert ads in between news items. In this paper, we model this setting, and observe that allocation and pricing of ad insertions in a stream poses interesting algorithmic and mechanism design challenges. In particular, we formulate an optimization problem that captures a typical stream ad placement setting. We give an approximation algorithm for this problem that provably achieves a value close to the optimal, and show how this algorithm can be turned into an incentive compatible mechanism. Finally, we conclude with a simple practical algorithm that makes the allocation decisions in an online fashion. We prove this algorithm to be approximately welfare-maximizing and show that it also has good incentive properties.

Recent work in commerce search has shown that understanding the semantics in user queries enables more effective query analysis and retrieval of relevant products. However, due to lack of sufficient domain knowledge, user queries often include terms that cannot be mapped directly to any product attribute. For example, a user looking for designer handbags might start with such a query because she is not familiar with the manufacturers, the price ranges, and/or the material that gives a handbag designer appeal. Current commerce search engines treat terms such as designer as keywords and attempt to match them to contents such as product reviews and product descriptions, often resulting in poor user experience.

Historical prices are important information that can help consumers decide whether the time is right to buy a product. They provide both a context to the users, and facilitate the use of prediction algorithms for forecasting future prices. To produce a representative price history, one needs to consider all offers for the product. However, matching offers to a product is a challenging problem, and mismatches could lead to glaring errors in price history. We propose a principled approach to filter out erroneous matches based on a probabilistic model of prices. We give an efficient algorithm for performing inference that takes advantage of the structure of the problem. We evaluate our results empirically using merchant offers collected from a search engine, and measure the proximity of the price history generated by our approach to the true price history. Our method outperforms alternatives based on robust statistics both in tracking the true price levels and the true price trends.

This paper uncovers a new phenomenon in web search that we call domain bias --- a user's propensity to believe that a page is more relevant just because it comes from a particular domain. We provide evidence of the existence of domain bias in click activity as well as in human judgments via a comprehensive collection of experiments. We begin by studying the difference between domains that a search engine surfaces and that users click. Surprisingly, we find that despite changes in the overall distribution of surfaced domains, there has not been a comparable shift in the distribution of clicked domains. Users seem to have learned the landscape of the internet and their click behavior has thus become more predictable over time. Next, we run a blind domain test, akin to a Pepsi/Coke taste test, to determine whether domains can shift a user's opinion of which page is more relevant. We find that domains can actually flip a user's preference about 25% of the time. Finally, we demonstrate the existence of systematic domain preferences, even after factoring out confounding issues such as position bias and relevance, two factors that have been used extensively in past work to explain user behavior. The existence of domain bias has numerous consequences including, for example, the importance of discounting click activity from reputable domains.

Most e-commerce sites to-date have focused on helping consumers decide what to buy and where to buy. We study the complementary question of helping consumers decide when to buy, focusing on consumer durables. We introduce a utility-based model for evaluating different approaches to this question. We focus on how best to make use of forecasts in making recommendations, and propose three natural strategies. We establish a relationship between these strategies, and show that one of them is optimal. We conduct a large-scale experimental study to test the performance and robustness of these strategies. Across a wide range of conditions, the best strategy obtains 90% of the maximum possible gains.

Web search engines incorporate results from structured data sources to answer semantically rich user queries, i.e. Samsung 50 inch led tv can be answered from a table of television data. However, users are not domain experts and quite often enter values that do not match precisely the underlying data, so a literal execution will return zero results. A search engine would prefer to return at least a minimum number of results as close to the original query as possible while providing a time-bound execution guarantee. In this paper, we formalize these requirements, show the problem is NP-Hard and present approximation algorithms that produce rewrites that work in practice. We empirically validate our algorithms on large-scale data from a major search engine.

Keeping in pace with the increasing importance of commerce conducted over the Web, several e-commerce websites now provide admirable facilities for helping consumers decide what product to buy and where to buy it. However, since the prices of durable and high-tech products generally fall over time, a buyer of such products is often faced with a dilemma: Should she buy the product now or wait for cheaper prices?

Large web search engines process billions of queries each day over tens of billions of documents with often very stringent requirements for a user's search experience, in particular, low latency and highly relevant search results. Index generation and serving are key to satisfying both these requirements. For example, the load to search engines can vary drastically when popular events happen around the world. In the case when the load is exceeding what the search engine can serve, queries will get dropped. This results in an un- graceful degradation in search quality. Another example that could increase the query load and affect the user's search experience are ambiguous queries which often result in the execution of multiple query alterations in the back end.

We study an online advertising model in which the merchant reimburses a portion of the transacted amount to the customer in a form of rebate. The customer referral and the rebate transfer might be mediated by a search engine. We investigate how the merchants can set rebate rates across different products to maximize their revenue. We consider two widely used demand models in economics---linear and log-linear---and explain how the effects of rebates can be incorporated in these models. Treating the parameters estimated as inputs to a revenue maximization problem, we develop convex optimization formulations of the problem and combinatorial algorithms for solving them. We validate our modeling assumptions using real transaction data. We conduct an extensive simulation study to evaluate the performance of our approach on maximizing revenue, and found that it generates significantly higher revenues for merchants compared to other rebate strategies. The rebate rates selected are extremely close to the optimal rates selected in hindsight.

We study the problem of answering ambiguous web queries in a setting where there exists a taxonomy of information, and that both queries and documents may belong to more than one category according to this taxonomy. We present a systematic approach to diversifying results that aims to minimize the risk of dissatisfaction of the average user. We propose an algorithm that well approximates this objective in general, and is provably optimal for a natural special case. Furthermore, we generalize several classical IR metrics, including NDCG, MRR, and MAP, to explicitly account for the value of diversification. We demonstrate empirically that our algorithm scores higher in these generalized metrics compared to results produced by commercial search engines.

We introduce a new approach to analyzing click logs by examining both the documents that are clicked and those that are bypassed-documents returned higher in the ordering of the search results but skipped by the user. This approach complements the popular click-through rate analysis, and helps to draw negative inferences in the click logs. We formulate a natural objective that finds sets of results that are unlikely to be collectively bypassed by a typical user. This is closely related to the problem of reducing query abandonment. We analyze a greedy approach to optimizing this objective, and establish theoretical guarantees of its performance. We evaluate our approach on a large set of queries, and demonstrate that it compares favorably to the maximal marginal relevance approach on a number of metrics including mean average precision and mean reciprocal rank.

We study coalitional games where the value of cooperation among the agents are solely determined by the attributes the agents possess, with no assumption as to how these attributes jointly determine this value. This framework allows us to model diverse economic interactions by picking the right attributes. We study the computational complexity of two coalitional solution concepts for these games -- the Shapley value and the core. We show how the positive results obtained in this paper imply comparable results for other games studied in the literature.

We present a new approach to representing coalitional games based on rules that describe the marginal contributions of the agents. This representation scheme captures characteristics of the interactions among the agents in a natural and concise manner. We also develop efficient algorithms for two of the most important solution concepts, the Shapley value and the core, under this representation. The Shapley value can be computed in time linear in the size of the input. The emptiness of the core can be determined in time exponential only in the treewidth of a graphical interpretation of our representation.

In this paper we investigate the computational problem of predicting RNA secondary structures that allow any kinds of pseudoknots. The general belief is that allowing pseudoknots makes the problem very difficult. Existing polynomial-time algorithms, which aim at structures that optimize some energy functions, can only handle a certain types of pseudoknots. In this paper we initiate the study of approximation algorithms for handling all kinds of pseudoknots. We focus on predicting RNA secondary structures with a maximum number of stacking pairs and obtain two approximation algorithms with worst-case approximation ratios of 1/2 and 1/3 for planar and general secondary structures, respectively. Furthermore, we prove that allowing pseudoknots would make the problem of maximizing the number of stacking pairs on planar secondary structure to be NP-hard. This result should be contrasted with the recent NP-hard results on psuedoknots which are based on optimizing some peculiar energy functions.