AF: Small: Fundamental Problems in Geometric Data Structures
AF:小:几何数据结构中的基本问题
基本信息
- 批准号:1814026
- 负责人:
- 金额:$ 50万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2018
- 资助国家:美国
- 起止时间:2018-10-01 至 2021-09-30
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
In today's era of big data, we frequently encounter large amounts of data that are geometric, or that may be represented as points or objects in geometric spaces. There is a growing need for the design of efficient data structures that can process and answer queries about such geometric data quickly. This project focuses on some of the most fundamental and central data structuring problems in computational geometry, and explores new ideas to obtain improved results on these longstanding problems. The research project will be integrated with the development of courses for undergraduate and graduate students that incorporate the latest research findings on geometric data structures.Among the fundamental problems studied are point location and nearest neighbor search. The project will also investigate geometric data structure problems in new settings that arise from modern-day applications, including distance-related problems in high dimensions, distance-related problems concerning unit-disk graphs (frequently used to model ad hoc wireless networks) and other types of geometric graphs, and streaming algorithms that can process high volumes of geometric data quickly with a limited amount of storage space.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的法定使命,通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(22)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices
- DOI:10.1137/1.9781611976465.89
- 发表时间:2021-01
- 期刊:
- 影响因子:0
- 作者:Timothy M. Chan
- 通讯作者:Timothy M. Chan
Dynamic Generalized Closest Pair: Revisiting Eppstein's Technique
动态广义最近对:重温 Eppstein 的技术
- DOI:10.1137/1.9781611976014.6
- 发表时间:2020
- 期刊:
- 影响因子:0
- 作者:Chan, Timothy M.
- 通讯作者:Chan, Timothy M.
Further Results on Colored Range Searching
- DOI:10.4230/lipics.socg.2020.28
- 发表时间:2020-03
- 期刊:
- 影响因子:0
- 作者:Timothy M. Chan;Qizheng He;Yakov Nekrich
- 通讯作者:Timothy M. Chan;Qizheng He;Yakov Nekrich
More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time
- DOI:10.4230/lipics.socg.2021.25
- 发表时间:2021-03
- 期刊:
- 影响因子:0
- 作者:Timothy M. Chan;Qizheng He
- 通讯作者:Timothy M. Chan;Qizheng He
Faster Approximation Algorithms for Geometric Set Cover
几何集覆盖的更快近似算法
- DOI:10.4230/lipics.socg.2020.27
- 发表时间:2020
- 期刊:
- 影响因子:0
- 作者:Chan, Timothy M.;He, Qizheng
- 通讯作者:He, Qizheng
{{
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 }}
Timothy Chan其他文献
Theory of Computing
计算理论
- DOI:
10.4086/toc - 发表时间:
2013 - 期刊:
- 影响因子:0
- 作者:
Alexandr Andoni;Nikhil Bansal;P. Beame;Giuseppe Italiano;Sanjeev Khanna;Ryan O’Donnell;T. Pitassi;T. Rabin;Tim Roughgarden;Clifford Stein;Rocco Servedio;Amir Abboud;Nima Anari;Ibm Srinivasan Arunachalam;T. J. Watson;Research Center;Petra Berenbrink;Aaron Bernstein;Aditya Bhaskara;Sayan Bhattacharya;Eric Blais;H. Bodlaender;Adam Bouland;Anne Broadbent;Mark Bun;Timothy Chan;Arkadev Chattopadhyay;Xue Chen;Gil Cohen;Dana Dachman;Anindya De;Shahar Dobzhinski;Zhiyi Huang;Ken;Robin Kothari;Marvin Künnemann;Tu Kaiserslautern;Rasmus Kyng;E. Zurich;Sophie Laplante;D. Lokshtanov;S. Mahabadi;Nicole Megow;Ankur Moitra;Technion Shay Moran;Google Research;Christopher Musco;Prasad Raghavendra;Alex Russell;Laura Sanità;Alex Slivkins;David Steurer;Epfl Ola Svensson;Chaitanya Swamy;Madhur Tulsiani;Christos Tzamos;Andreas Wiese;Mary Wootters;Huacheng Yu;Aaron Potechin;Aaron Sidford;Aarushi Goel;Aayush Jain;Abhiram Natarajan;Abhishek Shetty;Adam Karczmarz;Adam O’Neill;Aditi Dudeja;Aditi Laddha;Aditya Krishnan;Adrian Vladu Afrouz;J. Ameli;Ainesh Bakshi;Akihito Soeda;Akshay Krishnamurthy;Albert Cheu;A. Grilo;Alex Wein;Alexander Belov;Alexander Block;Alexander Golovnev;Alexander Poremba;Alexander Shen;Alexander Skopalik;Alexandra Henzinger;Alexandros Hollender;Ali Parviz;Alkis Kalavasis;Allen Liu;Aloni Cohen;Amartya Shankha;Biswas Amey;Bhangale Amin;Coja;Yehudayoff Amir;Zandieh Amit;Daniely Amit;Kumar Amnon;Ta;Beimel Anand;Louis Anand Natarajan;Anders Claesson;André Chailloux;André Nusser;Andrea Coladangelo;Andrea Lincoln;Andreas Björklund;Andreas Maggiori;A. Krokhin;A. Romashchenko;Andrej Risteski;Anirban Chowdhury;Anirudh Krishna;A. Mukherjee;Ankit Garg;Anna Karlin;Anthony Leverrier;Antonio Blanca;A. Antoniadis;Anupam Gupta;Anupam Prakash;A. Singh;Aravindan Vijayaraghavan;Argyrios Deligkas;Ariel Kulik;Ariel Schvartzman;Ariel Shaulker;A. Cornelissen;Arka Rai;Choudhuri Arkady;Yerukhimovich Arnab;Bhattacharyya Arthur Mehta;Artur Czumaj;A. Backurs;A. Jambulapati;Ashley Montanaro;A. Sah;A. Mantri;Aviad Rubinstein;Avishay Tal;Badih Ghazi;Bartek Blaszczyszyn;Benjamin Moseley;Benny Pinkas;Bento Natura;Bernhard Haeupler;Bill Fefferman;B. Mance;Binghui Peng;Bingkai Lin;B. Sinaimeri;Bo Waggoner;Bodo Manthey;Bohdan Kivva;Brendan Lucier Bundit;Laekhanukit Burak;Sahinoglu Cameron;Seth Chaodong Zheng;Charles Carlson;Chen;Chenghao Guo;Chenglin Fan;Chenwei Wu;Chethan Kamath;Chi Jin;J. Thaler;Jyun;Kaave Hosseini;Kaito Fujii;Kamesh Munagala;Kangning Wang;Kanstantsin Pashkovich;Karl Bringmann Karol;Wegrzycki Karteek;Sreenivasaiah Karthik;Chandrasekaran Karthik;Sankararaman Karthik;C. S. K. Green;Larsen Kasturi;Varadarajan Keita;Xagawa Kent Quanrud;Kevin Schewior;Kevin Tian;Kilian Risse;Kirankumar Shiragur;K. Pruhs;K. Efremenko;Konstantin Makarychev;Konstantin Zabarnyi;Krišj¯anis Pr¯usis;Kuan Cheng;Kuikui Liu;Kunal Marwaha;Lars Rohwedder László;Kozma László;A. Végh;L'eo Colisson;Leo de Castro;Leonid Barenboim Letong;Li;Li;L. Roditty;Lieven De;Lathauwer Lijie;Chen Lior;Eldar Lior;Rotem Luca Zanetti;Luisa Sinisclachi;Luke Postle;Luowen Qian;Lydia Zakynthinou;Mahbod Majid;Makrand Sinha;Malin Rau Manas;Jyoti Kashyop;Manolis Zampetakis;Maoyuan Song;Marc Roth;Marc Vinyals;Marcin Bieńkowski;Marcin Pilipczuk;Marco Molinaro;Marcus Michelen;Mark de Berg;M. Jerrum;Mark Sellke;Mark Zhandry;Markus Bläser;Markus Lohrey;Marshall Ball;Marthe Bonamy;Martin Fürer;Martin Hoefer;M. Kokainis;Masahiro Hachimori;Matteo Castiglioni;Matthias Englert;Matti Karppa;Max Hahn;Max Hopkins;Maximilian Probst;Gutenberg Mayank Goswami;Mehtaab Sawhney;Meike Hatzel;Meng He;Mengxiao Zhang;Meni Sadigurski;M. Parter;M. Dinitz;Michael Elkin;Michael Kapralov;Michael Kearns;James R. Lee;Sudatta Bhattacharya;Michal Koucký;Hadley Black;Deeparnab Chakrabarty;C. Seshadhri;Mahsa Derakhshan;Naveen Durvasula;Nika Haghtalab;Peter Kiss;Thatchaphol Saranurak;Soheil Behnezhad;M. Roghani;Hung Le;Shay Solomon;Václav Rozhon;Anders Martinsson;Christoph Grunau;G. Z. —. Eth;Zurich;Switzerland;Morris Yau — Massachusetts;Noah Golowich;Dhruv Rohatgi — Massachusetts;Qinghua Liu;Praneeth Netrapalli;Csaba Szepesvári;Debarati Das;Jacob Gilbert;Mohammadtaghi Hajiaghayi;Tomasz Kociumaka;B. Saha;K. Bringmann;Nick Fischer — Weizmann;Ce Jin;Yinzhan Xu — Massachusetts;Virginia Vassilevska Williams;Yinzhan Xu;Josh Alman;Kevin Rao;Hamed Hatami;—. XiangMeng;McGill University;Edith Cohen;Xin Lyu;Tamás Jelani Nelson;Uri Stemmer — Google;Research;Daniel Alabi;Pravesh K. Kothari;Pranay Tankala;Prayaag Venkat;Fred Zhang;Samuel B. Hopkins;Gautam Kamath;Shyam Narayanan — Massachusetts;Marco Gaboardi;R. Impagliazzo;Rex Lei;Satchit Sivakumar;Jessica Sorrell;T. Korhonen;Marco Bressan;Matthias Lanzinger;Huck Bennett;Mahdi Cheraghchi;V. Guruswami;João Ribeiro;Jan Dreier;Nikolas Mählmann;Sebastian Siebertz — TU Wien;The Randomized k ;Conjecture Is;False;Sébastien Bubeck;Christian Coester;Yuval Rabani — Microsoft;Wei;Ethan Mook;Daniel Wichs;Joshua Brakensiek;Sai Sandeep — Stanford;University;Lorenzo Ciardo;Stanislav Živný;Amey Bhangale;Subhash Khot;Dor Minzer;David Ellis;Guy Kindler;Noam Lifshitz;Ronen Eldan;Dan Mikulincer;George Christodoulou;E. Koutsoupias;Annamária Kovács;José Correa;Andrés Cristi;Xi Chen;Matheus Venturyne;Xavier Ferreira;David C. Parkes;Yang Cai;Jinzhao Wu;Zhengyang Liu;Zeyu Ren;Zihe Wang;Ravishankar Krishnaswamy;Shi Li;Varun Suriyanarayana - 通讯作者:
Varun Suriyanarayana
Moore’s Paradox is not just another pragmatic paradox
- DOI:
10.1007/s11229-008-9403-x - 发表时间:
2008-10-15 - 期刊:
- 影响因子:1.300
- 作者:
Timothy Chan - 通讯作者:
Timothy Chan
Ultrafast disinfection of SARS-CoV-2 viruses
SARS-CoV-2 病毒的超快速消毒
- DOI:
- 发表时间:
2022 - 期刊:
- 影响因子:0
- 作者:
Yang Xu;A. Chin;Haosong Zhong;Connie Lee;Yi Chen;Timothy Chan;Z. Fan;Molong Duan;Leo L. M. Poon;Mitch Guijun Li - 通讯作者:
Mitch Guijun Li
P-330 The third-generation genetic engineered mouse model of late-stage multiple myeloma
- DOI:
10.1016/s2152-2650(23)01948-1 - 发表时间:
2023-09-01 - 期刊:
- 影响因子:
- 作者:
Jianhong Lin;Mohsin Maqbool;Kylin Emhoff;Tyler Alban;Hanna Hong;Eric Irons;Wanying Zhang;Rie Maeda;Sarah Ondrejka;Megan Nakashima;Faiz Anwer;Jason Valent;Jennifer Yu;Timothy Chan;Justin Lathia;Jianjun Zhao - 通讯作者:
Jianjun Zhao
Timothy Chan的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Timothy Chan', 18)}}的其他基金
AF: Small: Computational Geometry from a Fine-Grained Perspective
AF:小:细粒度角度的计算几何
- 批准号:
2224271 - 财政年份:2022
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
Towards Simpler Algorithms in Computational Geometry
计算几何中更简单的算法
- 批准号:
9902027 - 财政年份:1999
- 资助金额:
$ 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 万元
- 项目类别:重大研究计划
相似海外基金
AF: Small: Fundamental Questions in Communication and Computation Regarding Edit Type String Measures
AF:小:有关编辑类型字符串测量的通信和计算的基本问题
- 批准号:
2127575 - 财政年份:2021
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Fundamental High-Dimensional Algorithms
AF:小:基本的高维算法
- 批准号:
2007443 - 财政年份:2020
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Algorithms for Fundamental Optimization Problems in Computational Geometry
AF:小:计算几何中基本优化问题的算法
- 批准号:
1909171 - 财政年份:2019
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Fundamental Connections in Randomness and Complexity
AF:小:随机性和复杂性的基本联系
- 批准号:
1526952 - 财政年份:2015
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
CIF/AF: Small: Some fundamental complexity-inspired coding theory challenges
CIF/AF:小:一些由复杂性引发的基本编码理论挑战
- 批准号:
1422045 - 财政年份:2014
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: SMALL: Fundamental Data Structures
AF:小:基本数据结构
- 批准号:
1319648 - 财政年份:2013
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Fundamental High-Dimensional Algorithms based on Convex Geometry and Spectral Methods
AF:小:基于凸几何和谱方法的基本高维算法
- 批准号:
1217793 - 财政年份:2012
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: New Approaches to Fundamental Problems in Network Design
AF:小:网络设计中基本问题的新方法
- 批准号:
1115849 - 财政年份:2011
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Fundamental Geometry Processing
AF:小:基本几何处理
- 批准号:
0915661 - 财政年份:2009
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Fundamental Algorithms based on Convex Geometry and Spectral Methods
AF:小:基于凸几何和谱方法的基本算法
- 批准号:
0915903 - 财政年份:2009
- 资助金额:
$ 50万 - 项目类别:
Standard Grant