A growing trend in commercial search engines is the display of specialized content such as news, products, etc. interleaved with web search results. Ideally, this content should be displayed only when highly relevant to the search query, as it competes for space with ``regular' results and advertisements. One measure of the relevance to the search query is the click-through rate the specialized content achieves when displayed; hence, if we can predict this click-through rate accurately, we can use this as the basis for selecting when to show specialized content. In this paper, we consider the problem of estimating the click-through rate for dedicated news search results. For queries for which news results have been displayed repeatedly, the click-through rate can be tracked online; however, the key challenge for which ``new' queries to display news results remains. In this paper we propose a supervised model that offers accurate prediction of news click-through rates and satisfies the requirement of adapting quickly to emerging news events. We evaluate our technique using a large corpus of real news click-through data obtained from a major commercial search engine.

A frame rule enables local reasoning by providing a mechanism to preserve facts that are unchanged across a procedure call. Traditionally, it has been difficult to exploit the frame rule in classical first-order assertion logics that model the program heap as an uninterpreted map from addresses to values. Therefore, although classical logics allow precise and efficient {em intraprocedural/} verification by leveraging powerful automated theorem provers, the same precision and efficiency cannot be carried over to the {em interprocedural/} setting. In this paper, we augment Floyd-Hoare logic with a new formulation of the frame rule, which we call the ``semantic frame rule'. This rule is semantic because it can be formulated independently of the syntactic constructs (e.g., the separating conjunction popularized by separation logic) in the assertion logics. We introduce a new specification called {em call invariants/} that allows the user to exploit the semantic frame rule, and we provide a technique for generating verification conditions for programs annotated with call invariants. We have created a prototype implementation and we discuss our experience with call invariants on programs manipulating lists and arrays.

We study the problem of selling identical goods to n unit-demand bidders in a setting in which the total supply of goods is unknown to the mechanism. Items arrive dynamically, and the seller must make the allocation and payment decisions online with the goal of maximizing social welfare. We consider two models of unknown supply: the adversarial supply model, in which the mechanism must produce a welfare guarantee for any arbitrary supply, and the stochastic supply model, in which supply is drawn from a distribution known to the mechanism, and the mechanism need only provide a welfare guarantee in expectation. Our main result is a separation between these two models. We show that all truthful mechanisms, even randomized, achieve a diminishing fraction of the optimal social welfare (namely, no better than a $Omega(loglog n)$ approximation) in the adversarial setting. In sharp contrast, in the stochastic model, under a standard monotone hazard-rate condition, we present a truthful mechanism that achieves a constant (16.865) approximation. We show that the monotone hazard rate condition is necessary, and also characterize a natural subclass of truthful mechanisms in our setting, the set of online-envy-free mechanisms. All of the mechanisms we present fall into this class, and we prove almost optimal lower bounds for such mechanisms. Since auctions with unknown supply are regularly run in many online-advertising settings, our main results emphasize the importance of considering distributional information in the design of auctions in such environments.

Object-oriented languages such as Java and C# provide interfaces to support a restricted form of multiple inheritance. Existing low-level typed intermediate languages for object-oriented languages, however, either do not support interfaces or require non-standard interface implementations. This paper describes a typed intermediate language that can express the standard interface implementation strategies based on interface tables (itables). The language can faithfully model itables, the standard itable-based interface method invocation, and interface cast. The type system is sound and the type checking is decidable.

Compact routing addresses the tradeoff between table sizes and stretch, which is the worst-case ratio between the length of the path a packet is routed through by the scheme and the length of a shortest path from source to destination. We adapt the compact routing scheme by Thorup and Zwick to optimize it for power-law graphs. We analyze our adapted routing scheme based on the theory of unweighted random power-law graphs with fixed expected degree sequence by Aiello, Chung, and Lu. Our result is the first theoretical bound coupled to the parameter of the power-law graph model for a compact routing scheme. In particular, we prove that, for stretch 3, instead of routing tables with $tilde{O}(n^{1/2})$ bits as in the general scheme by Thorup and Zwick, expected sizes of $O(n^{gamma}log n)$ bits are sufficient, and that all the routing tables can be constructed at once in expected time $O(n^{1+gamma}log n)$, with $gamma=(tau-2)/(2tau-3)+epsilon$, where $tau$ in (2,3) is the power-law exponent and $epsilon>0$ (which implies $epsilon < gamma < 1/3 + epsilon$). Both bounds also hold with probability at least 1-1/n (independent of $epsilon$). The routing scheme is a labeled scheme, requiring a stretch-5 handshaking step and using addresses and message headers with $O(log nloglog n)$ bits, with probability at least 1-o(1). We further demonstrate the effectiveness of our scheme by simulations on real-world graphs as well as synthetic power-law graphs. With the same techniques as for the compact routing scheme, we also adapt the approximate distance oracle by Thorup and Zwick for stretch 3 and obtain a new upper bound of expected $tilde{O}(n^{1+gamma})$ for space and preprocessing for random power-law graphs.

In this paper, we propose a novel interactive image ranking technique, color-structured image search, by exploiting color spatial relation information, and demonstrate it in image research results refinement. This technique enables users to draw a few color strokes, called target color structure, to indicate the intent. Beyond the conventional image retrieval methods based on query by image content that simply view the target color structure as an image and compute the similarity merely according to the spatial correspondence criterion, the proposed method represents the target color structure using a set of spatially relational colors, and evaluates the similarities between target color structure and image color structure by exploiting their spatial correspondence information, and an extra novel criterion, the consistency of spatial relation of colors implied in target color structure, and even offering a scheme to handle the uncertainty of target color structure. This similarity evaluation process can be accomplished efficiently. Moreover, a convenient interactive interface is presented to allow users to specify target color structure flexibly. Experimental results demonstrate the effectiveness and efficiency of the proposed approach.