AF: Small:Efficient Data Management Algorithms

在过去的十年里，随着视频点播应用的增长以及通过传感器和其他设备收集的数据的爆炸性增长，海量数据集上的计算正在成为无处不在的规范。这一事态发展要求更深入地理解这种情况下的几个具体问题。第一个问题是数据放置；当数据位置更接近需求时，对网络资源的需求就会减少。第二个问题与能源最小化有关：如何开发算法方法来提高数据处理的效率？这两个问题都导致了一系列有趣的问题，如日程安排和设施选址类型问题。为了解决这些问题，本项目致力于开发管理用于处理的数据存储的算法，并将能源效率作为首要考虑因素。许多先前的调度文献假设以作业为中心的观点--算法被开发来优化拖期、完成时间、完工时间等。相反，这项工作是由以系统为中心的观点所推动的，在该观点中，以“高效”的方式利用资源是最优先的，以“令人满意的”方式完成单个作业。这种效率主要表现为系统产生的能源成本。这些问题在大规模存储设备和数据中心的环境中尤为突出。主要关注所有类型的数据，从存储在磁盘集合上的多媒体数据到收集和存储在分布式存储系统中的数据。要存储和高效访问的数据量正在以不可持续的速度增长。管理这些数据的成本预计将大幅增长。主要问题是如何开发调度算法来有效和高效地管理这些数据。数据中心正迅速成为社会不可或缺的一部分，并改变了从社交网络到人类交流到科学协作、计算和数据交换的一切。这项研究将提高这一关键基础设施的效率。该项目将培训研究生在大学进行研究，并在夏季通过在工业研究实验室的实习进行研究。预计将有本科生和女性的广泛指导和参与。在过去的几年里，国际计算机协会开发了一门新的课程《计算背后的科学》，并正在为这门课程编写一本书，其主要目的是教育普通公众有关21世纪与计算有关的重要科学概念。

Within the last decade, with the growth of video on-demand applications and the explosion of data collected via sensors and other devices, computation over massive data sets is becoming the ubiquitous norm. This development calls for a deeper understanding of several issues specific to such contexts. The first issue is one of data placement; when data is located more closely to the demand, the need for network resources is reduced. The second issue pertains to energy minimization: how can one develop algorithmic methods to make data processing more efficient? Both of these issues lead to a host of interesting questions in the vein of scheduling and facility location type problems. In an effort to address these issues, this project focuses on the development of algorithms that manage data storage for processing, with energy efficiency as the primary consideration.Much of the prior scheduling literature assumes a job-centric perspective -- algorithms are developed to optimize tardiness, completion time, makespan, etc. In contrast, this work is motivated by a system-centric view in which utilizing resources in an "efficient'' way is of the utmost priority, subject to individual jobs being completed in a "satisfactory'' manner. Such efficiencies are primarily manifested in the form of the energy cost incurred by the system. These problems are particularly eminent in the context of large scale storage devices and data centers. The main focus is on data of all types, ranging from multimedia data stored on a collection of disks to data collected and stored in a distributed storage system. The amount of data to be stored and efficiently accessed is increasing at an unsustainable rate. The costs for managing this data are expected in turn to grow significantly. The main question is how can one develop scheduling algorithms to manage this data effectively and efficiently.Data centers are fast becoming integral to society and have transformed everything from social networking to human communication to scientific collaboration, computation, and data exchange. This research will lead to increased efficiencies in this critical infrastructure. The project will train graduate students in conducting research both at universities and through internships at industrial research labs during the summer. Extensive mentoring and involvement of undergraduate students and women is expected. Over the last few years, the PI has developed a new course on "Science behind Computing'' and is working on a book for this course, the primary purpose of which is to educate the general public about important scientific concepts related to computing in the 21st century.