课题基金 / 基金详情

AF: Small: New directions in the design of local computation algorithms

AF: Small: New directions in the design of local computation algorithms
AF:小:局部计算算法设计的新方向
批准号:
1420692
负责人:
Ronitt Rubinfeld
金额:
$40.0万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2014
资助国家:
美国
项目状态:
已结题
起止时间:
2014-09-01 至 2017-08-31

项目摘要

项目成果

Ronitt Rubinfeld的其他基金

相似基金

相关文献

中文摘要
翻译
当试图解决输入和输出都很大的计算时,处理大数据是很困难的。尽管如此,通常情况下,在任何阶段只需要解决方案的一小部分。最近引入了局部计算算法,以便允许用户快速访问所需的输出部分,而无需执行完整的计算。本地计算算法的目的是以一种比查看整个输入或输出的简单任务所需的速度快得多的方式为用户提供有用的答案。所提出的研究将扩展局部计算算法的范围,以允许对组合优化的新问题进行快速处理。将研究的一类局部计算算法是那些提供对输入图的稀疏子图的查询访问的算法,该子图保留了原始图的连通性和距离属性。第二类局部计算算法“清理”数据,使其具有某些理想的属性,例如图连通性。新技术将被开发来处理基本的计算问题,这些问题可以用作解决一系列其他问题的工具。这个项目更广泛的影响在于对年轻研究人员的教育和指导。PI将在当地小学开展“不插电计算机科学”活动。PI将积极努力,确保妇女和少数民族学生更多地参与该项目。次线性时间算法的材料将整合到本科和研究生算法课程中。
英文摘要
Dealing with big data is formidable when attempting to solve computations in which both the inputs and outputs are large. Nonetheless, frequently it is the case that only small parts of the solution are needed at any stage. Local computation algorithms were recently introduced in order to allow a user to quickly access the portions of the output that are required, without performing the full computation. The aim of local computation algorithms is to provide useful answers to the user in a manner that is significantly faster than what is required even for the simple task of viewing the whole input or output.The proposed research will expand the scope of local computation algorithms to allow such fast processing for new problems from combinatorial optimization. One class of local computation algorithms that will be studied are those that provide query access to a sparse subgraph of the input graph which preserves connectivity and distance properties of the original graph. A second class of local computation algorithms "clean up" data to have certain desirable properties, such as graph connectivity. New techniques will be developed to approach basic computational problems that can be used as tools in solving a wide array of other problems.The broader impacts of this project are in the education and mentoring of young researchers. The PI will engage in Computer Science Unplugged activities at local elementary schools. The PI will work actively to ensure greater participation of women and minority students in the project. Material from sub-linear time algorithms will be integrated into undergraduate and graduate algorithms courses.
期刊论文(1)
专著(0)
科研奖励(0)
会议论文
DOI: 10.4230/lipics.itcs.2017.41
发表时间: 2017-02
期刊: ArXiv
影响因子: --
作者: [V. Feldman;Badih Ghazi]
通讯作者: V. Feldman;Badih Ghazi
AF: SMALL: Extending the Reach of Distribution Testing via Structure
AF: Small: Sparsity in Local Computation
AitF: Collaborative Research: Fast, Accurate, and Practical: Adaptive Sublinear Algorithms for Scalable Visualization
BIGDATA: F: Testing High Dimensional Distributions without the Curse of Dimensionality
国内基金
海外基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 项目类别:
    省市级项目
  • 资助金额:
    --
  • 批准年份:
    2024
  • 负责人:
  • 依托单位:
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
  • 项目类别:
    省市级项目
  • 资助金额:
    10.0万元
  • 批准年份:
    2022
  • 负责人:
    张祥忠
  • 依托单位:
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 项目类别:
    面上项目
  • 资助金额:
    58.0万元
  • 批准年份:
    2019
  • 负责人:
    高学文
  • 依托单位: