The effectiveness of a search engine is typically evaluated using hand-labeled datasets, where the labels indicate the relevance of documents to queries. Often the number of labels needed is too large to be created by the best annotators, and so less expensive labels (e.g., from crowdsourcing) are used. This introduces errors in the labels, and thus errors in standard effectiveness metrics (such as P@k and DCG). These errors must be taken into consideration when using the metrics. Previous work has approached assessor error by taking aggregates over multiple inexpensive assessors. We take a different approach and introduce equations and algorithms that can adjust the metrics to the values they would have had if there were no annotation errors. This is especially important when two search engines are compared on their metrics. We give examples where one engine appeared to be statistically significantly better than the other, but the effect disappeared after the metrics were corrected for annotation error. In other words, the evidence supporting a statistical difference was illusory and caused by a failure to account for annotation error.

Given an ecommerce query, how well the titles of items for sale match the user intent is an important signal for ranking the items. A well-known technique for computing this signal is to use a standard machine-learned model that uses words as features, targets user clicks and predicts a score to rank the titles. In this paper, we introduce an alternate modeling technique that applies to queries that are frequent enough to have historical click data. For each such query we build a parameterized model of user behavior that learns what makes users skip a title. The parameters are different for each query. Specifically, our model predicts how desirable an item's title is to the user query by focusing on the worst tokens in the title. The model is learned offline using maximum likelihood based on user behavioral data, significantly improving query processing cost. The model's output score is used as a feature in a machine learned ranker for e-commerce search at eBay. Besides titles, the model design can easily incorporate any attribute of an item including structured content. In this scope, we present our new title desirability model built for nearly 8M queries recently deployed into the eBay search ecosystem and demonstrate its significant performance improvement over a baseline click-based Nïve Bayes model through different evaluation approaches including A/B testing and human judgment. The reported performance is based on eBays commercial search engine serving millions of queries each day.

The quality of a search engine is typically evaluated using hand-labeled data sets, where the labels indicate the relevance of documents to queries. Often the number of labels needed is too large to be created by the best annotators, and so less accurate labels (e.g. from crowdsourcing) must be used. This introduces errors in the labels, and thus errors in standard precision metrics (such as [email protected] and DCG); the lower the quality of the judge, the more errorful the labels, consequently the more inaccurate the metric. We introduce equations and algorithms that can adjust the metrics to the values they would have had if there were no annotation errors.

MOTIVATION: In the past few years, mass spectrometry (MS) has emerged as the premier tool for identification and quantification of biological molecules such as peptides and glycans. There are two basic strategies: single-MS, which uses a single round of mass analysis, and MS/MS (or higher order MS(n)), which adds one or more additional rounds of mass analysis, interspersed with fragmentation steps. Single-MS offers higher throughput, broader mass coverage and more direct quantitation, but generally much weaker identification. Single-MS, however, does work fairly well for the case of N-glycan identification, which are more constrained than other biological polymers. We previously demonstrated single-MS identification of N-glycans to the level of 'cartoons' (monosaccharide composition and topology) by a system that incorporates an expert's detailed knowledge of the biological sample. In this article, we explore the possibility of ab initio single-MS N-glycan identification, with the goal of extending single-MS, or primarily-single-MS, identification to non-expert users, novel conditions and unstudied tissues. RESULTS: We propose and test three cartoon-assignment algorithms that make inferences informed by biological knowledge about glycan synthesis. To test the algorithms, we used 71 single-MS spectra from a variety of tissues and organisms, containing more than 2800 manually annotated peaks. The most successful of the algorithms computes the most richly connected subgraph within a 'cartoon graph'. This algorithm uniquely assigns the correct cartoon to more than half of the peaks in 41 out of the 71 spectra.

We describe position sensing algorithms used in an airjet paper moving system built at Xerox PARC. The algorithms combine inputs from optical sensors and compute the rectangle best fitting the data. We consider two different types of sensors: fax scan bars and disk-shaped area sensors. Our algorithms proved to be quite effective both in simulation and in actual use.

We present a new algorithm for automatically solving jigsaw puzzles by shape alone. The algorithm can solve more difficult puzzles than could be solved before, without the use of backtracking or branch-and-bound. The algorithm can handle puzzles in which pieces border more than four neighbors, and puzzles with as many as 200 pieces. Our overall strategy follows that of previous algorithms but applies a number of new ideas, such as robust fiducial points, "highest- confidence-first" search, and frequent global reoptimization of partial solutions.

We describe an algorithm for computing an image signature, suitable for first-stage screening for duplicate images. Our signature relies on the relative brightness of image regions, and is generally applicable to photographs, text documents, and line art. We give experimental results on the sensitivity and robustness of signatures for actual image collections, and also results on the robustness of signatures under transformations such as resizing, rescanning, and compression.

Two images of the same document could differ significantly due to faxing, scanner distortions, or degradation through multigeneration copying. Additionally, one of the images may have extensive annotations not present in the other. We give a method for registering two such images and separating out annotations. We further present an algorithm for detecting and repairing broken strokes in the annotations. Our methods have been tested on a wide variety of documents with reliable results; for the special case of form dropout our results are better than had been obtained previously with special-purpose algorithms.

We describe a method for improving scanned or faxed document images. Our method assumes a probabilistic model of the scanning process, and uses this model to cluster instances of the same letter and to compute super-resolved representatives of the clusters. The approach also enables Bayesian prior distributions and reversal of scanner distortions such as gain.

This paper describes the Liveboard, a large interactive display system. With nearly one million pixels and an accurate, multi-state, cordless pen, the Liveboard provides a basis for research on user interfaces for group meetings, presentations and remote collaboration. We describe the underlying hardware and software of the Liveboard, along with several software applications that have been developed. In describing the system, we point out the design rationale that was used to make various choices. We present the results of an informal survey of Liveboard users, and describe some of the improvements that have been made in response to user feedback. We conclude with several general observations about the use of large public interactive displays.

In a database to which data is continually added, users may wish to issue a permanent query and be notified whenever data matches the query. If such continuous queries examine only single records, this can be implemented by examining each record as it arrives. This is very efficient because only the incoming record needs to be scanned. This simple approach does not work for queries involving joins or time. The Tapestry system allows users to issue such queries over a database of mail and bulletin board messages. The user issues a static query, such as “show me all messages that have been replied to by Jones,” as though the database were fixed and unchanging. Tapestry converts the query into an incremental query that efficiently finds new matches to the original query as new messages are added to the database. This paper describes the techniques used in Tapestry, which do not depend on triggers and thus be implemented on any commercial database that supports SQL. Although Tapestry is designed for filtering mail and news messages, its techniques are applicable to any append-only database.

Abstract This paper is concerned with pen-based (also called stylus-based) computers. Two of the key questions for such computers are how to interface to handwriting recognition algorithms, and whether there are interfaces that can effectively exploit the differences between a stylus and a keyboard/mouse. We describe prototypes that explore each of these questions. Our text entry tool is designed around the idea that handwriting recognition algorithms will always be error prone, and has a different flavor from existing systems. Our prototype editor goes beyond the usual gesture editors used with styli and is based on the idea of leaving the markups visible.