People's experiences when interacting with online services affects their decisions on reuse. Users of Web search engines are primarily focused on obtaining relevant information pertaining to their query. Search engines that fail to satisfy users' information needs may find their market share to be negatively affected. However, despite its importance to search providers, the relationship be-tween search success and search engine reuse is poorly understood. In this paper, we present a longitudinal log-based study with a large cohort of search engine users that quantifies the relationship between success and re-use of search engines. We use time series analysis to define two groups of users: stationary and non-stationary. We find that recent changes in satisfaction rate do correlate moderately with changes in rate of return for stationary users. For non-stationary users, we find that satisfaction and rate of return change together and in the same direction. We also find that some effects are stronger for a smaller player on the market than for a clear market leader, but both are affected. This is the first study to explore these issues in the context of Web search, and our findings have implications for search providers seeking to better understand their users and improving their experience.

In this paper, we provide an overview of the MSR-Bing Web Scale Speller Challenge of 2011. We describe the motivation and outline the algorithmic and engineering challenges posed by this activity. The design and the evaluation methods are also reviewed, and the online resources that will remain publicly available to the community are also described. The Challenge will culminate in a workshop after the time of the writing where the top prize winners will publish their approaches. The main findings and the lessons learned will be summarized and shared in the Industry Track presentation accompanying this paper.

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.

Active learning efficiently hones in on the decision boundary between relevant and irrelevant documents, but in the process can miss entire clusters of relevant documents, yielding classifiers with low recall. In this paper, we propose a method to increase active learning recall by constraining sampling to a document subset rich in relevant examples.

In practical classification, there is often a mix of learnable and unlearnable classes and only a classifier above a minimum performance threshold can be deployed. This problem is exacerbated if the training set is created by active learning. The bias of actively learned training sets makes it hard to determine whether a class has been learned. We give evidence that there is no general and efficient method for reducing the bias and correctly identifying classes that have been learned. However, we characterize a number of scenarios where active learning can succeed despite these difficulties.

The Web has become a worldwide repository of information which individuals, companies, and organizations utilize to solve or address various information problems. Many of these Web users utilize automated agents to gather this information for them. Some assume that this approach represents a more sophisticated method of searching. However, there is little research investigating how Web agents search for online information. In this research, we first provide a classification for information agent using stages of information gathering, gathering approaches, and agent architecture. We then examine an implementation of one of the resulting classifications in detail, investigating how agents search for information on Web search engines, including the session, query, term, duration and frequency of interactions. For this temporal study, we analyzed three data sets of queries and page views from agents interacting with the Excite and AltaVista search engines from 1997 to 2002, examining approximately 900,000 queries submitted by over 3,000 agents. Findings include: (1) agent sessions are extremely interactive, with sometimes hundreds of interactions per second (2) agent queries are comparable to human searchers, with little use of query operators, (3) Web agents are searching for a relatively limited variety of information, wherein only 18% of the terms used are unique, and (4) the duration of agent-Web search engine interaction typically spans several hours. We discuss the implications for Web information agents and search engines.

Abstract Major Web search engines, such as AltaVista, are essential tools in the quest to locate online information. This article reports research that used transaction log analysis to examine the characteristics and changes in AltaVista Web searching that occurred from 1998 to 2002. The research questions we examined are (1) What are the changes in AltaVista Web searching from 1998 to 2002? (2) What are the current characteristics of AltaVista searching, including the duration and frequency of search sessions? (3) What changes in the information needs of AltaVista users occurred between 1998 and 2002? The results of our research show (1) a move toward more interactivity with increases in session and query length, (2) with 70% of session durations at 5 minutes or less, the frequency of interaction is increasing, but it is happening very quickly, and (3) a broadening range of Web searchers' information needs, with the most frequent terms accounting for less than 1% of total term usage. We discuss the implications of these findings for the development of Web search engines.

The Web has become a worldwide repository of information, which individuals, companies, and organizations utilize to solve or address various information problems. Many of these Web users utilize automated agents to gather this information for them. It is assumed that this approach represents a more sophisticated method of searching. However, there is little research investigating how Web agents search for online information. In this research, we examine how agents search for information on Web search engines, including the session, query, term, duration and frequency of interactions. For this study, we analyzed queries that 2,717 agents submitted to the Alta Vista search engine on 8 September 2002. Findings include: (1) agents interacting with Web search engines use queries comparable to human searchers, (2) Web agents are searching for a relatively limited variety of information, with only 18% of the terms used being unique, and (3) agent-Web search engine interaction typically spans several hours with multiple instances of interaction per second.

In this paper we examine the question of query parsing for World Wide Web queries and present a novel method for phrase recognition and expansion.Given a training corpus of approximately 16 million Web queries and a handwritten context-free grammar, the EM algorithm is used to estimate the parameters of a probabilistic context-free grammar (PCFG) with a system developed by Carroll [5].We use the PCFG to compute the most probable parse for a user query, re ecting linguistic structure and word usage of the domain being parsed.The optimal syntactic parse for a user query thus obtained is employed for phrase recognition and expansion.Phrase recognition is used to increase retrieval precision; phrase expansion is applied to make the best use possible of very short Web queries.

No abstract available.

Methods exist for comtant-time clustering of corpus subsets selected via Scatter/Gather browsing [3].In thii paper we expand on those techniqum, giving an algorithm for alrnostconstant-time clustering of arbitrary corpus subsets.This algorithm is never slower than clustering the document set from scratch, and for medium-sised and large sets it is significantly faster.ThE algorithm ia USSM for clustering arbitrary subsets of large corpora -obtained, for instance, by a boolean search -quickly enough to be useful in an interactive setting.

We present Scatter/Gather, a cluster-based document browsing method, as an alternative to ranked titles for the organization and viewing of retrieval results.We systematically evaluate Scatter/Gather in this context and find significant improvements over similarity search ranking alone.This result provides evidence validating the cluster hypothesis which states that relevant documents tend to be more similar to each other than to non-relevant documents.We describe a system employing Scatter/Gather and demonstrate that users are able to use this system close to its full potential.1

There is strong empirical and theoretic evidence that combination of retrieval methods can improve performance.In this paper, we systematically compare combination strategies in the context of document filtering, using queries from the Tipster reference corpus.We find that simple averaging strategies do indeed improve performance, but that direet averaging of probability estimates is not the correet approach.Instead, the probabiJit y estimates must be renormalized using logistic regression on the known relevance judgments.We examine more complex combination strat~ gies but find them less successful due to the high correlations among our filtering methods which are optimized over the same training data and employ similar document represerttations.1

To summarize is to reduce in complexity, and hence in length, while retaining some of the essential qualities of the original.This paper focusses on document extracts, a particular kind of computed document summary.Document extracts consisting of roughly 20% of the original cart be as informative as the full text of a document, which suggests that even shorter extracts may be useful indicative summmies.The trends in our results are in agreement with those of Ed- mundson who used a subjectively weighted combination of features as opposed to training the feature weights using a corpus.We have developed a trainable summarization program that is grounded in a sound statistical framework.

In this paper, we compare learning techniques based on statistical classification to traditional methods of relevance feedback for the document routing problem.We consider three classification techniques which have decision rules that are derived via explicit error minimization linear discriminant analysis, logistic regression, and neuraf networks.We demonstrate that the classifiers perform 10-15% better than relevance feedback via Rocchio expansion for the TREC-2 and TREC-3 routing tasks.Error minimization is difficult in high-dimensional feature spaces because the convergence process is slow and the models ~e prone to overfitting.We use two different strategies, latent semantic indexing and optimaJ term selection, to reduce the number of features.Our results indicate that features based on latent semantic indexing are more effective for techniques such as linear discriminant anafysis and logistic regression, which have no way to protect against overfitting.Neural networks perform equally well with either set of features and can take advantage of the additional information available when both feature sets are used as input.

The Scatter/Gather document browsing method uses fast document clustering to produce table-of-contents-like outlines of large document collections. Previous work [1] developed linear-time document clustering algorithms to establish the feasibility of this method over moderately large collections. However, even linear-time algorithms are too slow to support interactive browsing of very large collections such as Tipster, the DARPA standard text retrieval evaluation collection. We present a scheme that supports constant interaction-time Scatter/Gather of arbitrarily large collections after near-linear time preprocessing. This involves the construction of a cluster hierarchy. A modification of Scatter/Gather employing this scheme, and an example of its use over the Tipster collection are presented.

Document clustering has not been well received as an information retrieval tool. Objections to its use fall into two main categories: first, that clustering is too slow for large corpora (with running time often quadratic in the number of documents); and second, that clustering does not appreciably improve retrieval.

For free-text search over rapidly evolving corpora, dynamic update of inverted indices is a basic requirement. B-trees are an effective tool in implementing such indices. The Zipfian distribution of postings suggests space and time optimizations unique to this task. In particular, we present two novel optimizations, merge update, which performs better than straight forward block update, and pulsing which significantly reduces space requirements without sacrificing performance.