III-COR-SMALL: RUI: Models and Methods for Information Organization

下一代互联网应用程序面临的一个关键挑战是有效管理和呈现海量数据。目前的许多研究工作都集中在为搜索和信息检索的目的对数据进行索引。这里，数据表示为最优算法遍历。相比之下，几乎没有人注意优化数据以供人类访问。例如，当保存电子邮件时，通常将消息存储在一系列按层次排列的文件夹中，其中每个子文件夹比其父文件夹更具体。为了检索消息，用户通常在搜索框中输入查询。应用程序返回匹配的电子邮件列表，用户线性搜索该列表。该建议开发了一个正式的算法框架，用于自动组织和呈现适合人类遍历的信息。组织和向人展示信息时的一个中心目标是创建一个系统，在该系统中，所需的信息可以快速且容易地找到。将这一标准扩展到人类可遍历的组织意味着安排数据，使组织结构直观，搜索高效。该提案研究了与人类可遍历的数据组织有关的三个具体问题：信息组织的最佳方式、信息组织的动态模型以及标记数据的新组织模式，例如博客、新闻网站和科学储存库中的可用数据。算法和模型的实现将公开供其他研究人员和教育工作者下载。结果将在国家讲习班和发表的论文中传播。这项研究还将被纳入威廉姆斯大学的几门课程，包括一门新的关于近似算法的教程风格的课程。与本科生就提案中定义的问题进行合作，将加强和扩大威廉姆斯学院目前的本科生研究机会。

A pivotal challenge for the next generation of internet applications is effectively managing and presenting massive amounts of data. Many current research efforts focus on indexing data for the purposes of search and information retrieval. Here the data is represented for optimal algorithmic traversal. In contrast, almost no attention is paid toward optimizing the data for human traversal.For example, when saving email, it is common to store messages in a series of hierarchically arranged folders where each child folder is more specific than its parents. To retrieve a message, a user typically enters a query in a search box. The application returns a list of matching emails and the user searches this list linearly. This proposal develops a formal algorithmic framework for automatically organizing and presenting information suitable for human traversal. A central goal when organizing and presenting information to a person is creating a system where desired information is quick and easy to find. Extending this criterion to human traversable organizations means arranging data so that the organizational structure is intuitive and the search is efficient. This proposal investigates three specific problems related to human-traversable organization of data: optimal ways to organize the information, dynamic models of information organization, and new organization models for tagged data, such as available on blogs, news websites and in scientific repositories. Algorithms and models implementations will be made publicly available for download by other researchers and educators. Results will be disseminated at national workshops and published papers. This research will also be incorporated into several courses at Williams including a new tutorial-style course on approximation algorithms. Collaborative work with undergraduate students on problems defined within the proposal will both enhance and expand the current opportunities for undergraduate research at Williams College.