EAGER:High Performance Algorithms for Interactive Data Science at Scale

数据科学面临的现实挑战是开发交互式方法来快速分析潜在的大规模新数据集。该合同将设计和实现高性能计算解决方案的基本算法，使大规模数据集的交互式大规模数据分析成为可能。基于广泛使用的数据类型和字符串、集合、矩阵和图的结构，该方法将为三类基本算法生成高效且可扩展的软件，这些算法将大大提高在广泛的现实世界查询或直接实现频繁查询上的性能。这些创新将允许广泛的社区将大规模数据探索从耗时的批处理转移到交互式分析，从而使数据分析师能够全面，深入和有效地探索现实世界数据集中的见解和科学。通过使越来越多的开发人员能够轻松地操作大型数据集，这将极大地扩大数据科学社区，并在新的社区中找到更广泛的用途。这个项目的材料将包括在研究生和本科生课程中。特别是女性、高中生和其他STEM领域代表性不足的群体将被鼓励参与这项研究活动。本项目重点研究数据分析的三种重要数据结构：1)后缀数组构造，2)“treap”构造和3)分布式内存连接算法，它们分别用于分析大规模字符串，在大型字符串数据集中实现随机搜索，以及生成新的关系。这些基本算法是支持大规模交互式数据科学的基石。在理论成果和系统算法设计的基础上，提出一种将理论分析、数据结构特征和典型数据分布特征有机结合的新型共生优化方法，以显著提高所提算法的实际性能。为了评估和展示所提出算法的有效性，这些算法将在一个类似numpy的开源软件框架中实现，并为其做出贡献，该框架旨在通过将Python的生产力与世界一流的高性能计算相结合，为大规模，数十tb的数据集提供高效的数据发现工具。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

A real-world challenge in data science is to develop interactive methods for quickly analyzing new and novel data sets that are potentially of massive scale. This award will design and implement fundamental algorithms for high performance computing solutions that enable the interactive large-scale data analysis of massive data sets. Based on the widely-used data types and structures of strings, sets, matrices and graphs, this methodology will produce efficient and scalable software for three classes of fundamental algorithms that will drastically improve the performance on a wide range of real-world queries or directly realize frequent queries. These innovations will allow the broad community to move massive-scale data exploration from time-consuming batch processing to interactive analyses that give a data analyst the ability to comprehensively, deeply and efficiently explore the insights and science in real world data sets. By enabling the increasing number of developers to easily manipulate large data sets, this will greatly enlarge the data science community and find much broader use in new communities. Materials from this project will be included in graduate and undergraduate course curriculum. Especially, women, high school students and other underrepresented groups in STEM areas will be encouraged to participate in this research activity. This project focuses on these three important data structures for data analytics: 1) suffix array construction, 2) 'treap' construction and 3) distributed memory join algorithms, useful for analyzing large scale strings, implementing random search in large string data sets, and generating new relations, respectively. These fundamental algorithms serve as the cornerstone to support interactive data science at scale. Based on the theoretical achievements and systematic algorithm design, a novel symbiotic optimization methodology that can combine the theoretical analysis, data structure features, and typical data distribution features together as a whole will be developed to significantly improve the practical performance of the proposed algorithms. To evaluate and show the effectiveness of the proposed algorithms, these algorithms will be implemented in and contribute to an open source NumPy-like software framework that aims to provide productive data discovery tools on massive, dozens-of-terabytes data sets by bringing together the productivity of Python with world-class high performance computing.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.