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.
