In this paper we describe a problem of discovering query clusters from a click-through graph of web search logs. The graph consists of a set of web search queries, a set of pages selected for the queries, and a set of directed edges that connects a query node and a page node clicked by a user for the query. The proposed method extracts all maximal bipartite cliques (bicliques) from a click-through graph and compute an equivalence set of queries (i.e., a query cluster) from the maximal bicliques. A cluster of queries is formed from the queries in a biclique. We present a scalable algorithm that enumerates all maximal bicliques from the click-through graph. We have conducted experiments on Yahoo web search queries and the result is promising.

In this paper we study the characteristics of search queries submitted from mobile devices using various Yahoo! one-Search applications during a 2 months period in the second half of 2007, and report the query patterns derived from 20 million English sample queries submitted by users in US, Canada, Europe, and Asia. We examine the query distribution and topical categories the queries belong to in order to find new trends. We compare and contrast the search patterns between US vs international queries, and between queries from various search interfaces (XHTML/WAP, java widgets, and SMS). We also compare our results with previous studies wherever possible, either to confirm previous findings, or to find interesting differences in the query distribution and pattern.

Contextual search refers to proactively capturing the information need of a user by automatically augmenting the user query with information extracted from the search context; for example, by using terms from the web page the user is currently browsing or a file the user is currently editing.We present three different algorithms to implement contextual search for the Web. The first, it query rewriting (QR), augments each query with appropriate terms from the search context and uses an off-the-shelf web search engine to answer this augmented query. The second, rank-biasing (RB), generates a representation of the context and answers queries using a custom-built search engine that exploits this representation. The third, iterative filtering meta-search (IFM), generates multiple subqueries based on the user query and appropriate terms from the search context, uses an off-the-shelf search engine to answer these subqueries, and re-ranks the results of the subqueries using rank aggregation methods.We extensively evaluate the three methods using 200 contexts and over 24,000 human relevance judgments of search results. We show that while QR works surprisingly well, the relevance and recall can be improved using RB and substantially more using IFM. Thus, QR, RB, and IFM represent a cost-effective design spectrum for contextual search.

Contextual search tries to better capture a user's information need by augmenting the user's query with contextual information extracted from the search context (for example, terms from the web page the user is currently reading or a file the user is currently editing).This paper presents Y!Q---a first of its kind large-scale contextual search system---and provides an overview of its system design and architecture. Y!Q solves two major problems. First, how to capture high quality search context. Second, how to use that context in a way to improve the relevancy of search queries. To address the first problem, Y!Q introduces an information widget that captures precise search context and provides convenient access to its functionality at the point of inspiration. For example, Y!Q can be easily embedded into web pages using a web API, or it can be integrated into a web browser toolbar. This paper provides an overview of Y!Q's user interaction design, highlighting its novel aspects for capturing high quality search context.To address the second problem, Y!Q uses a semantic network for analyzing search context, possibly resolving ambiguous terms, and generating a contextual digest comprising its key concepts. This digest is passed through a query planner and rewriting framework for augmenting a user's search query with relevant context terms to improve the overall search relevancy and experience. We show experimental results comparing contextual Y!Q search results side-by-side with regular Yahoo! web search results. This evaluation suggests that Y!Q results are considered significantly more relevant.The paper also identifies interesting research problems and argues that contextual search may represent the next major step in the evolution of web search engines.