ITR/SY: Combinatorial Optimization Algorithms for Informaion Access (Fundamental IT Models)

Cornell University, Ithaca NY

Investigators

Abstract

Proposal No: 0113371 ITR/SY: Combinatorial Optimization Algorithms for Information Access (Fundamental IT Models) PI: Eva Tardos The enormous growth in the amount of information online makes it vital to automate the job of searching and organizing large data collections while maintaining high accuracy. The research will consider two seemingly unrelated tasks: . Searching web pages, and . Analyzing the content of digital pictures and movies. Despite their obvious great importance, and the large efforts invested, the currently available solutions for these tasks are inadequate. The proposed research will address a difficult mathematical problem that underlies both of these tasks, the classification problem with pair-wise constraints. The traditional classification problems consist of a set of objects to be classified, and a set of labels (the classes). Classifying the topics of documents on the Web, or individual pixels or regions of an image are two examples of this general problem. The proposed research will build on the PIs recent successes in applying powerful combinatorial optimization techniques to develop algorithms for classification problems with pair-wise relationships. Pair-wise constraints can significantly enhance classification, by modeling, e.g., the relations of physically close objects in an image, or relations implicit in the hyperlink structure of the Web. The outcome of this research will be to provide powerful new tools for two important tasks in searching and organizing large data collections.