CCF-BSF: AF: Small: Collaborative Research: The Dictionary Problem Considered

CCF-BSF：AF：小型：协作研究：考虑的字典问题

基本信息

批准号：
1715777
负责人：
Martin Farach-Colton
金额：
$ 25万
依托单位：
Rutgers University New Brunswick
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-09-01 至 2020-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1715777&HistoricalAwards=false
关键词：
CCF BSF AF Small Collaborative

项目摘要

The performance of databases, file systems, and other data-storage systems depends on how the data is organized on disk. The data-organization parts of these systems are called dictionaries. Even though dictionaries have been studied for decades, some very basic questions remain unanswered. This grant will support research to address several of these questions. This research has the potential to improve performance of data-storage systems and applications based on these systems in many environments, including large-scale data analysis and high-performance computing. Dictionaries are so fundamental that theoretical advances in dictionaries are quickly picked up by practitioners, and thus this research has strong potential for tech transfer. Specifically, the project will tackle foundational problems in dictionaries using techniques in write-optimization pioneered by the PIs. How are systems of dictionaries different than individual dictionaries? How can dictionaries take advantage of variations in the rate of queries and updates? How can one comprehensively compare dictionary data structures? How can one bring the benefits of write-optimization to dictionaries on more complex data types? Write-optimized dictionaries have fundamentally changed the landscape of databases, and this research will improve our understanding of the complexity of operations on such systems.

数据库、文件系统和其他数据存储系统的性能取决于数据在磁盘上的组织方式。这些系统的数据组织部分称为字典。尽管对词典的研究已经有几十年了，但一些非常基本的问题仍然没有得到解答。这笔赠款将支持解决其中几个问题的研究。这项研究有可能在许多环境中提高数据存储系统和基于这些系统的应用程序的性能，包括大规模数据分析和高性能计算。字典是如此基础，以至于字典中的理论进步很快就被实践者所接受，因此这项研究具有强大的技术转让潜力。具体来说，该项目将使用 PI 首创的写入优化技术来解决字典中的基本问题。词典系统与单个词典有何不同？字典如何利用查询和更新速率的变化？如何全面比较字典数据结构？如何将写入优化的优势带给更复杂数据类型的字典？写入优化字典从根本上改变了数据库的面貌，这项研究将提高我们对此类系统操作复杂性的理解。

项目成果

期刊论文数量（1）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

A Scheduling Approach to Incremental Maintenance of Datalog Programs

数据记录程序增量维护的调度方法

DOI：
发表时间：
2020-01
期刊：
IPDPS
影响因子：
0
作者：
Singh, Shikha;Madaminov, Sergey;Bender, Michael;Ferdman, Michael;Johnson, Ryan;Moseley, Benjamin;Ngo, Hung;Nguyen, Dung;Olesen, Soeren;Stirewalt, Kurt;et al
通讯作者：
et al