We present a graph-theoretic approach to discover storylines from search results. Storylines are windows that offer glimpses into interesting themes latent among the top search results for a query; they are different from, and complementary to, clusters obtained through traditional approaches. Our framework is axiomatically developed and combinatorial in nature, based on generalizations of the maximum induced matching problem on bipartite graphs. The core algorithmic task involved is to mine for signature structures in a robust graph representation of the search results. We present a very fast algorithm for this task based on local search. Experiments show that the collection of storylines extracted through our algorithm offers a concise organization of the wealth of information hidden beyond the first page of search results.

In this paper we present a solution to the general vision problem of parsing and recognizing a set of correlated entities in the presence of imperfect information. Our solution mechanism involves the generation of multiple hypotheses in the initial stages of the system, and the use of very-large vocabulary recognition, together with a database of all the valid combination of the correlated entities, to choose among the hypotheses. We have applied our ideas and techniques to the specific task of identifying the city, state and zipcode fields in handwritten addresses. Given the image of a handwritten address, our algorithm produces a ranking of the 76,121-entry database of valid (city, state, zip) triples in the U.S. and in nearly 75% of the cases, the correct entry for the input address is assigned a rank of at most 10.

The problem of separating words in a handwritten line is made difficult by the presence of non-uniform spacing between words and between characters within a word. A central sub-problem in word separation is the estimation of gaps between adjacent components in a line. We present a new technique to estimate inter-component distances that is based on the gap between their convex hulls. The technique evolved through a study of the drawbacks in previous approaches to gap estimation, and is shown to be better in terms of performance and robustness.