In this paper, we study multi-click queries - queries for which more than one click is performed by the same user within the same query session. Such queries may reflect a more complex information need, which leads the user to examine a variety of results. We present a comprehensive analysis that reveals unique characteristics of multi-click queries, in terms of their syntax, lexical domains, contextual properties, and returned search results page. We also show that a basic classifier for predicting multi-click queries can reach an accuracy of 75% over a balanced dataset. We discuss the implications of our findings for the design of Web search tools.

Vertical selection is the task of predicting relevant verticals for a Web query so as to enrich the Web search results with complementary vertical results. We investigate a novel variant of this task, where the goal is to detect queries with a question intent. Specifically, we address queries for which the user would like an answer with a human touch. We call these CQA-intent queries, since answers to them are typically found in community question answering (CQA) sites. A typical approach in vertical selection is using a vertical's specific language model of relevant queries and computing the query-likelihood for each vertical as a selective criterion. This works quite well for many domains like Shopping, Local and Travel. Yet, we claim that queries with CQA intent are harder to distinguish by modeling content alone, since they cover many different topics. We propose to also take the structure of queries into consideration, reasoning that queries with question intent have quite a different structure than other queries. We present a supervised classification scheme, random forest over word-clusters for variable length texts, which can model the query structure. Our experiments show that it substantially improves classification performance in the CQA-intent selection task compared to content-oriented based classification, especially as query length grows.

We define the following parameter of connected graphs. For a given graph $G = (V,E)$ we place one agent in each vertex $v \in V$. Every pair of agents sharing a common edge is declared to be acquainted. In each round we choose some matching of $G$ (not necessarily a maximal matching), and for each edge in the matching the agents on this edge swap places. After the swap, again, every pair of agents sharing a common edge become acquainted, and the process continues. We define the acquaintance time of a graph $G$, denoted by $\mathcal{AC}(G)$, to be the minimal number of rounds required until every two agents are acquainted. We first study the acquaintance time for some natural families of graphs including the path, expanders, the binary tree, and the complete bipartite graph. We also show that for all $n \in {\mathbb N}$ and for all positive integers $k \leq n^{1.5}$ there exists an $n$-vertex graph $G$ such that $k/c \leq \mathcal{AC}(G) \leq c \cdot k$ for some universal constant $c \geq 1$. We also prove that for all $n$-vertex connected graphs $G$ we have $\mathcal{AC}(G) = O(\frac{n^2}{\log(n)/\log\log(n)})$, thus improving the trivial upper bound of $O(n^2)$ achieved by sequentially letting each agent perform depth-first search along some spanning tree of $G$. Studying the computational complexity of this problem, we prove that for any constant $t \geq 1$ the problem of deciding that a given graph $G$ has $\mathcal{AC}(G) \leq t$ or $\mathcal{AC}(G) \geq 2t$ is $\mathcal{NP}$-complete. That is, $\mathcal{AC}(G)$ is $\mathcal{NP}$-hard to approximate within multiplicative factor of 2, as well as within any additive constant factor. On the algorithmic side, we give a deterministic algorithm that given an $n$-vertex graph $G$ with $\mathcal{AC}(G)=1$ finds a strategy for acquaintance that consists of $\lceil{n/c}\rceil$ matchings in time $n^{c+O(1)}$. We also design a randomized polynomial time algorithm that given an $n$-vertex graph $G$ with $\mathcal{AC}(G)=1$ finds with high probability an $O(\log(n))$-rounds strategy for acquaintance.

We initiate the study of testing properties of images that correspond to sparse 0/1-valued matrices of size n × n . Our study is related to but different from the study initiated by Raskhodnikova ( Proceedings of RANDOM, 2003 ), where the images correspond to dense 0/1-valued matrices. Specifically, in the model studied by Raskhodnikova, the distance that an image has to a specific property is the number of entries that should be modified in the corresponding matrix so that the property can be obtained, divided by the total number of entries: n 2 . In the model we consider, the distance is the number of entries that should be modified divided by the actual number of 1’s in the matrix, which may be much smaller than n 2 . We study several natural properties: connectivity, convexity, monotonicity, and being a line. In all cases, we give testing algorithms with sublinear complexity, and, in some of the cases, we also provide corresponding lower bounds.

Fast-Match is a fast algorithm for approximate template matching under 2D affine transformations that minimizes the Sum-of-Absolute-Differences (SAD) error measure. There is a huge number of transformations to consider but we prove that they can be sampled using a density that depends on the smoothness of the image. For each potential transformation, we approximate the SAD error using a sub linear algorithm that randomly examines only a small number of pixels. We further accelerate the algorithm using a branch-and-bound scheme. As images are known to be piecewise smooth, the result is a practical affine template matching algorithm with approximation guarantees, that takes a few seconds to run on a standard machine. We perform several experiments on three different datasets, and report very good results. To the best of our knowledge, this is the first template matching algorithm which is guaranteed to handle arbitrary 2D affine transformations.

We initiate the study of testing properties of images that correspond to sparse 0/1-valued matrices of size n × n. Our study is related to but different from the study initiated by Raskhodnikova (Proceedings of RANDOM, 2003), where the images correspond to dense 0/1-valued matrices. Specifically, while distance between images in the model studied by Raskhodnikova is the fraction of entries on which the images differ taken with respect to all n2entries, the distance measure in our model is defined by the fraction of such entries taken with respect to the actual number of 1's in the matrix. We study several natural properties: connectivity, convexity, monotonicity, and being a line. In all cases we give testing algorithms with sublinear complexity, and in some of the cases we also provide corresponding lower bounds.