III:Small: Optimal Query Processing meets Information Theory: from Proofs to Algorithms

III:Small:最优查询处理遇到信息论:从证明到算法

基本信息

  • 批准号:
    1907997
  • 负责人:
  • 金额:
    $ 50万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Continuing Grant
  • 财政年份:
    2019
  • 资助国家:
    美国
  • 起止时间:
    2019-08-15 至 2023-07-31
  • 项目状态:
    已结题

项目摘要

The demand to analyze large datasets is increasing at a rate faster than our ability to compute meaningful insights from the data. Despite the advances in query processing, query optimization, and novel hardware, efficient query evaluation remains a major challenge for the database community to date. This project will explore new ways to design query processing algorithms by using techniques from information theory. The field of information theory has been developed over the last seven decades and has found many applications ranging from communications to machine learning, but it has not been used yet in a significant way to support query processing. This project transfers techniques from information theory to the task of processing massive amounts of data.The project introduces a new paradigm for query evaluation, called "from proofs to algorithms," which maps an information-theoretic proof of a query's upper bounds into optimal query evaluation algorithms. The project will pursue four thrusts. In the first thrust it will use information theory to derive new bounds on the query answer based on database statistics. The second thrust will develop a mapping from the information theoretic inequalities to relational operators, and from the complete proof of the query size to a complete query plan with provably optimal runtime. The third thrust will extend these techniques to finer grained statistics, including sketches, distinct values, and heavy hitters. Finally, the fourth thrust will extend the algorithm to queries with projections, aggregates, and group-by's.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.
分析大型数据集的需求正在以比我们从数据中计算有意义的洞察力的能力更快的速度增长。尽管在查询处理、查询优化和新硬件方面取得了进步,但高效的查询评估仍然是数据库社区迄今面临的主要挑战。这个项目将探索利用信息论的技术来设计查询处理算法的新方法。信息论领域在过去的70年里得到了发展,并发现了从通信到机器学习的许多应用,但它还没有被显著地用于支持查询处理。这个项目将技术从信息论转移到处理海量数据的任务上。该项目引入了一种新的查询评估范式,称为从证明到算法,它将查询上限的信息论证明映射到最优查询评估算法中。该项目将推进四个方面的努力。在第一个推力中,它将使用信息论来推导基于数据库统计的查询答案的新界限。第二个推力将发展从信息论不等式到关系算子的映射,以及从查询大小的完全证明到具有可证明的最优运行时间的完整查询计划。第三个推力将把这些技术扩展到更细粒度的统计数据,包括草图、不同的值和重量级数据。最后,第四个重点将把算法扩展到具有投影、聚合和分组依据的查询。这一奖项反映了NSF的法定使命,并通过使用基金会的智力优势和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(22)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Convergence of Datalog over (Pre-) Semirings
A Near-Optimal Parallel Algorithm for Joining Binary Relations
一种二元关系连接的近最优并行算法
  • DOI:
    10.46298/lmcs-18(2:6)2022
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0.6
  • 作者:
    Ketsman, Bas;Suciu, Dan;Tao, Yufei
  • 通讯作者:
    Tao, Yufei
On the Tractability of SHAP Explanations
论 SHAP 解释的可处理性
Datalog in Wonderland
  • DOI:
    10.1145/3552490.3552492
  • 发表时间:
    2022-07
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Mahmoud Abo Khamis;RelationalAI;H. Ngo;R. Pichler;T. Wien;Dan Suciu
  • 通讯作者:
    Mahmoud Abo Khamis;RelationalAI;H. Ngo;R. Pichler;T. Wien;Dan Suciu
Optimizing Recursive Queries with Progam Synthesis
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Dan Suciu其他文献

A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries
连接查询并集广义模型计数问题的二分法
Optimizing Large-Scale Semi-Naïve Datalog Evaluation in Hadoop
优化 Hadoop 中的大规模半简单数据记录评估
  • DOI:
  • 发表时间:
    2012
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Marianne Shaw;Paraschos Koutris;Bill Howe;Dan Suciu
  • 通讯作者:
    Dan Suciu
Integrating Network-Bound XML Data
集成网络绑定的 XML 数据
XViz: A Tool for Visualizing XPath Expressions
XViz:可视化 XPath 表达式的工具
Cytosolic protein ubiquitylation in normal and endotoxin stimulated human peripheral blood mononuclear cells
正常和内毒素刺激的人外周血单核细胞中胞质蛋白的泛素化
  • DOI:
  • 发表时间:
    2000
  • 期刊:
  • 影响因子:
    0
  • 作者:
    M. Majetschak;Dan Suciu;K. Häsler;U. Obertacke;F. Schade;H. Jennissen
  • 通讯作者:
    H. Jennissen

Dan Suciu的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Dan Suciu', 18)}}的其他基金

III: Small: Datalog with Aggregates: Complexity, Optimization, Evaluation
III:小:带有聚合的数据记录:复杂性、优化、评估
  • 批准号:
    2314527
  • 财政年份:
    2023
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
NSF-BSF: III: Small: Data Driven Schema
NSF-BSF:III:小型:数据驱动模式
  • 批准号:
    2109922
  • 财政年份:
    2021
  • 资助金额:
    $ 50万
  • 项目类别:
    Continuing Grant
III: Medium: Collaborative Research: Reasoning about Optimizers for Data-Intensive Systems
III:媒介:协作研究:数据密集型系统优化器的推理
  • 批准号:
    1954222
  • 财政年份:
    2020
  • 资助金额:
    $ 50万
  • 项目类别:
    Continuing Grant
III: Medium: Collaborative Research: A Unified and Declarative Approach to Causal Analysis for Big Data
III:媒介:协作研究:大数据因果分析的统一声明式方法
  • 批准号:
    1703281
  • 财政年份:
    2017
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
III: Small: Scalable Probabilistic Inference for Large Knowledge Bases
III:小:大型知识库的可扩展概率推理
  • 批准号:
    1614738
  • 财政年份:
    2016
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
AitF: FULL: Query Processing with Optimal Communication Cost
AitF:FULL:具有最佳通信成本的查询处理
  • 批准号:
    1535565
  • 财政年份:
    2015
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
BIGDATA: Mid-Scale: DCM: A Formal Foundation for Big Data Management
BIGDATA:中型:DCM:大数据管理的正式基础
  • 批准号:
    1247469
  • 财政年份:
    2013
  • 资助金额:
    $ 50万
  • 项目类别:
    Continuing Grant
III: Small: Query Compilation on Probabilistic Databases
III:小:概率数据库上的查询编译
  • 批准号:
    1115188
  • 财政年份:
    2011
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
III: Small: BeliefDB - Adding Belief Annotations to Databases
III:小:BeliefDB - 向数据库添加信念注释
  • 批准号:
    0915054
  • 财政年份:
    2009
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
III COR: Query Evaluation and View Materialization in Probabilistic Data
III COR:概率数据中的查询评估和视图具体化
  • 批准号:
    0713576
  • 财政年份:
    2007
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant

相似国自然基金

昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
    n/a
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
  • 批准号:
    32000033
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
  • 批准号:
    81900988
  • 批准年份:
    2019
  • 资助金额:
    21.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

Collaborative Research: ECCS: Small: Personalized RF Sensing: Learning Optimal Representations of Human Activities and Ethogram on the Fly
合作研究:ECCS:小型:个性化射频传感:学习人类活动的最佳表示和动态行为图
  • 批准号:
    2233503
  • 财政年份:
    2023
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
Collaborative Research: ECCS: Small: Personalized RF Sensing: Learning Optimal Representations of Human Activities and Ethogram on the Fly
合作研究:ECCS:小型:个性化射频传感:学习人类活动的最佳表示和动态行为图
  • 批准号:
    2233536
  • 财政年份:
    2023
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
FET: Small: An Integrated Framework for the Optimal Control of Open Quantum Systems --- Theory, Quantum Algorithms, and Applications
FET:小型:开放量子系统最优控制的集成框架 --- 理论、量子算法和应用
  • 批准号:
    2312456
  • 财政年份:
    2023
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
RI: Small: Collaborative Research: Evolutionary Approach to Optimal Morphology and Control of Transformable Soft Robots
RI:小型:协作研究:可变形软机器人的最佳形态和控制的进化方法
  • 批准号:
    2325491
  • 财政年份:
    2023
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
RI: Small: Optimal Transport Generative Adversarial Networks: Theory, Algorithms, and Applications
RI:小型:最优传输生成对抗网络:理论、算法和应用
  • 批准号:
    2327113
  • 财政年份:
    2023
  • 资助金额:
    $ 50万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Small: Efficient Algorithms for Optimal Transport in Geometric Settings
合作研究:AF:小:几何设置中最佳传输的高效算法
  • 批准号:
    2223871
  • 财政年份:
    2022
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
AF: Small: New Techniques for Optimal Bounds on MCMC Algorithms
AF:小:MCMC 算法最优边界的新技术
  • 批准号:
    2147094
  • 财政年份:
    2022
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: Efficient Algorithms for Optimal Transport in Geometric Settings
合作研究:AF:小:几何设置中最佳传输的高效算法
  • 批准号:
    2223870
  • 财政年份:
    2022
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
Analysis and Development of Optimal Circuit Structure for Small Volume Wireless Communication Circuits for IoT
物联网小体积无线通信电路最优电路结构的分析与开发
  • 批准号:
    21K21284
  • 财政年份:
    2021
  • 资助金额:
    $ 50万
  • 项目类别:
    Grant-in-Aid for Research Activity Start-up
CIF: Small: Statistically Optimal Subsampling for Big Data and Rare Events Data
CIF:小:大数据和稀有事件数据的统计最佳子采样
  • 批准号:
    2105571
  • 财政年份:
    2021
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了