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.