AF:Small: Fundamental Geometric Data Structures

AF:Small:基本几何数据结构

基本信息

  • 批准号:
    2203278
  • 负责人:
  • 金额:
    $ 59.41万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2022
  • 资助国家:
    美国
  • 起止时间:
    2022-10-01 至 2025-09-30
  • 项目状态:
    未结题

项目摘要

Efficient methods of storing and querying large data volumes play a crucial role in a majority of computer applications. In many situations, both the stored data and the queries can be represented as geometric objects, such as points, lines, and rectangles. This scenario is traditionally studied in computational geometry. However, geometric data structures have numerous applications in other areas of Computer Science, from spatial databases to geographic information systems, from computer graphics to bioinformatics. This project will study geometric data structures and their connections with other areas of theoretical Computer Science. The investigator and his students will also study the implementations of obtained algorithms and their potential applications. This project will focus on fundamental geometric data structuring problems: the orthogonal range searching problem, the point location problem, the nearest neighbor problem, and the dynamic convex hull problem. Despite several decades of extensive study, there are still several important open questions related to these problems.This project aims to extend and deepen the knowledge of this area: reduce or eliminate the gaps between the lower and upper bounds, investigate the relative complexities of problems in different models of computation, and find more efficient ways to dynamize the static data structures. The investigator will also explore the connections between geometric data structures and algorithms in the external memory model, making the project's contributions applicable to a larger class of applications.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.
存储和查询大量数据的有效方法在大多数计算机应用中起着至关重要的作用。在许多情况下,存储的数据和查询都可以表示为几何对象,如点、线和矩形。这种情况是传统上研究计算几何。然而,几何数据结构在计算机科学的其他领域有许多应用,从空间数据库到地理信息系统,从计算机图形学到生物信息学。本项目将研究几何数据结构及其与理论计算机科学其他领域的联系。研究人员和他的学生还将研究所获得的算法的实现及其潜在的应用。这个项目将集中在基本的几何数据结构问题:正交范围搜索问题,点定位问题,最近邻问题,和动态凸船体问题。尽管经过了几十年的广泛研究,仍然有几个重要的开放问题与这些问题有关。本项目旨在扩展和深化这一领域的知识:减少或消除上下界之间的差距,研究不同计算模型中问题的相对复杂性,并找到更有效的方法来动态化静态数据结构。研究人员还将探索几何数据结构和外部存储器模型中的算法之间的联系,使该项目的贡献适用于更大类别的应用程序。该奖项反映了NSF的法定使命,并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

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

{{ 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 }}

Yakov Nekrich其他文献

Breadth-First Rank/Select in Succinct Trees and Distance Oracles for Interval Graphs
区间图的简洁树和距离预言中的广度优先排序/选择
  • DOI:
  • 发表时间:
    2020
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Meng He;J. Munro;Yakov Nekrich;Sebastian Wild;Kaiyu Wu
  • 通讯作者:
    Kaiyu Wu
Sorted Range Reporting
排序范围报告
Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
在确定性线性时间内节省空间地构建压缩索引
Time-Optimal Top-k Document Retrieval
时间最优的 Top-k 文档检索
Size-constrained Weighted Ancestors with Applications
尺寸受限的加权祖先及其应用

Yakov Nekrich的其他文献

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

相似国自然基金

昼夜节律性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 万元
  • 项目类别:
    重大研究计划

相似海外基金

AF: Small: Fundamental Questions in Communication and Computation Regarding Edit Type String Measures
AF:小:有关编辑类型字符串测量的通信和计算的基本问题
  • 批准号:
    2127575
  • 财政年份:
    2021
  • 资助金额:
    $ 59.41万
  • 项目类别:
    Standard Grant
AF: Small: Fundamental High-Dimensional Algorithms
AF:小:基本的高维算法
  • 批准号:
    2007443
  • 财政年份:
    2020
  • 资助金额:
    $ 59.41万
  • 项目类别:
    Standard Grant
AF: Small: Algorithms for Fundamental Optimization Problems in Computational Geometry
AF:小:计算几何中基本优化问题的算法
  • 批准号:
    1909171
  • 财政年份:
    2019
  • 资助金额:
    $ 59.41万
  • 项目类别:
    Standard Grant
AF: Small: Fundamental Problems in Geometric Data Structures
AF:小:几何数据结构中的基本问题
  • 批准号:
    1814026
  • 财政年份:
    2018
  • 资助金额:
    $ 59.41万
  • 项目类别:
    Standard Grant
AF: Small: Fundamental Connections in Randomness and Complexity
AF:小:随机性和复杂性的基本联系
  • 批准号:
    1526952
  • 财政年份:
    2015
  • 资助金额:
    $ 59.41万
  • 项目类别:
    Standard Grant
CIF/AF: Small: Some fundamental complexity-inspired coding theory challenges
CIF/AF:小:一些由复杂性引发的基本编码理论挑战
  • 批准号:
    1422045
  • 财政年份:
    2014
  • 资助金额:
    $ 59.41万
  • 项目类别:
    Standard Grant
AF: SMALL: Fundamental Data Structures
AF:小:基本数据结构
  • 批准号:
    1319648
  • 财政年份:
    2013
  • 资助金额:
    $ 59.41万
  • 项目类别:
    Standard Grant
AF: Small: Fundamental High-Dimensional Algorithms based on Convex Geometry and Spectral Methods
AF:小:基于凸几何和谱方法的基本高维算法
  • 批准号:
    1217793
  • 财政年份:
    2012
  • 资助金额:
    $ 59.41万
  • 项目类别:
    Standard Grant
AF: Small: New Approaches to Fundamental Problems in Network Design
AF:小:网络设计中基本问题的新方法
  • 批准号:
    1115849
  • 财政年份:
    2011
  • 资助金额:
    $ 59.41万
  • 项目类别:
    Standard Grant
AF: Small: Fundamental Geometry Processing
AF:小:基本几何处理
  • 批准号:
    0915661
  • 财政年份:
    2009
  • 资助金额:
    $ 59.41万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了