CSR: Medium: Approximate Membership Query Data Structures in Computational Biology and Storage

该项目将为计算生物学和大数据存储系统开发新的数据结构和软件。在这个项目中创建的数据结构将允许计算生物学和大数据应用程序维护庞大数据集的紧凑摘要。由于摘要很小，它们可以存储在计算机的快速内存中，从而使应用程序能够更快地运行并扩展到更大的数据集。例如，该项目将开发一种工具，用于搜索数千（到数百万）个人的遗传信息，以检测与疾病或其他特征相关的遗传变异。这个项目将解决的一个主要挑战是应用程序需要紧凑、功能丰富的摘要数据结构。应用程序需要能够表示一组元素的摘要，在一组输入数据中计算重复项，随着数据集的增长调整大小，支持删除项，与其他摘要合并，并支持当今多核系统上的高并发性。然而，当前的汇总数据结构提供的功能有限。因此，今天的应用程序必须围绕这些限制进行设计，从而导致软件速度变慢，使用更多内存，并且比必要的更复杂。该项目将影响核心计算机科学应用，如数据库和文件系统，以及医学和生物学应用，如基因组和转录组分析。数据库和文件系统将运行得更快，使用的内存更少。他们将能够将快速、昂贵的固态存储设备与廉价、慢速、但容量大的硬盘驱动器结合起来，从而获得两种设备的最佳性能：低成本和高性能。生物学家将能够使用更少的计算资源，更快、更便宜地分析测序数据。他们将能够在庞大的数据集中进行搜索，以获得新的发现。该项目创建的所有论文、文档和软件都将以开源形式发布，通常在流行的开源开发网站上发布，例如在COMBINE-lab （https://github.com/COMBINE-lab）和splatlab （https://github.com/splatlab）组织下的GitHub。论文将由出版商主持，以及对作者？S个人网站。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This project will develop new data structures and software for computational biology and big data storage systems. The data structures created in this project will allow computational biology and big data applications to maintain compact summaries of huge data sets. Because the summaries are small, they can be stored in a computer's fast memory, enabling applications to run much more quickly and to scale to larger data sets. For example, this project will develop a tool for searching through genetic information for thousands (to millions) of individuals to detect genetic variations that are correlated with disease or other traits. A major challenge that this project will address is that applications need compact, feature-rich summary data structures. Applications need summaries that can represent a set of elements, count duplicates in a set of input data, be resized as the data set grows, support deletions of items, be merged with other summaries, and support high concurrency on today's multi-core systems. However, current summary data structures offer limited features. As a result, today's applications must design around these limitations, resulting in software that is slower, uses more memory, and is more complex than necessary.The project will impact core computer science applications, such as databases and file systems, and medical and biological applications, such as genome and transcriptome analysis. Databases and file systems will run faster and use less memory. They will be able to combine fast, expensive solid-state storage devices with cheap, slow, but capacious hard drives to get the best of both devices: low cost and high performance. Biologists will be able to analyze sequencing data more quickly and cheaply, using fewer computational resources. They will be able to search through huge datasets to make new discoveries.All papers, documentation, and software created by this project will be released as open source, typically on popular open-source development websites, such as GitHub, under the COMBINE-lab (https://github.com/COMBINE-lab) and splatlab (https://github.com/splatlab) organizations. Papers will be hosted by the publishers, as well as on the author?s personal websites.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.