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

CSR：中：计算生物学和存储中的近似成员资格查询数据结构

• 批准号: 2317838
• 负责人: Robert Patro
• 金额: $ 120万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-10-01 至 2024-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2317838&HistoricalAwards=false
• 关键词: CSR; Medium; Approximate; Membership; Query

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.

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

项目成果

Automatic HBM Management: Models and Algorithms

• DOI: 10.1145/3490148.3538570
• 发表时间: 2022-07
• 期刊: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures
• 作者: Daniel DeLayo;Kenny Zhang;Kunal Agrawal;M. A. Bender;Jonathan W. Berry;Rathish Das;Benjamin Moseley;C. Phillips

On the optimal time/space tradeoff for hash tables

• DOI: 10.1145/3519935.3519969
• 发表时间: 2021-10
• 期刊: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: M. A. Bender;Martín Farach-Colton;John Kuszmaul;William Kuszmaul;Mingmou Liu

Fulgor: A Fast and Compact k-mer Index for Large-Scale Matching and Color Queries

Fulgor：用于大规模匹配和颜色查询的快速、紧凑的 k-mer 索引

• DOI: 10.4230/lipics.wabi.2023.18
• 发表时间: 2023
• 期刊: 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023
• 作者: Fan, Jason;Singh, Noor Pratap;Khan, Jamshed;Pibiri, Giulio Ermanno;Patro, Rob
• 通讯作者: Patro, Rob

Online List Labeling: Breaking the log 2 n Barrier

在线列表标签：打破 log 2 n 障碍

• DOI: 10.1109/focs54457.2022.00096
• 发表时间: 2022
• 期刊: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS
• 作者: Bender, Michael A.;Conway, Alex;Farach-Colton, Martin;Komlos, Hanna;Kuszmaul, William;Wein, Nicole
• 通讯作者: Wein, Nicole

Mosaic Pages: Big TLB Reach with Small Pages

马赛克页面：小页面实现大 TLB 覆盖范围

• DOI: 10.1145/3582016.3582021
• 发表时间: 2023
• 期刊: Proc.\ 28th {ACM} International Conference on Architectural Support for Programming Languages and Operating Systems
• 作者: Gosakan, Krishnan;Han, Jaehyun;Kuszmaul, William;Mubarek, Ibrahim N.;Mukherjee, Nirjhar;Sriram, Karthik;Tagliavini, Guido;West, Evan;Bender, Michael A.;Bhattacharjee, Abhishek
• 通讯作者: Bhattacharjee, Abhishek