CAREER: Approximate Algorithms for High-dimensional Geometric Problems

职业:高维几何问题的近似算法

基本信息

  • 批准号:
    0133849
  • 负责人:
  • 金额:
    --
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Continuing Grant
  • 财政年份:
    2002
  • 资助国家:
    美国
  • 起止时间:
    2002-04-01 至 2007-12-31
  • 项目状态:
    已结题

项目摘要

This Career Development Plan involves an integrated collection of research and educational activities focused on algorithms for high-dimensional geometric problems.Geometric computing with high-dimensional data is of crucial importance to many areas of computer science, including machine learning, data mining, databases and information retrieval, computer vision and computational biology.Example problems in this area are: nearest neighbor search, many variants of data clustering, and discovering linear structure of the data (e.g. via Principal Component Analysis (PCA)). Unfortunately, the classical geometric algorithms for many of these problems do not scale well with the dimension. For example, the running times of the classical algorithms for the nearest neighbor search depend exponentially on the dimension, which makes them inefficient for dimension higher than, say, 20. This is unfortunate, since many applications involve number of dimensions anywhere from a few hundred to a few million.In recent years, new, powerful techniques for solving theseproblems have been discovered, most notably dimensionality reduction and random sampling in geometric spaces. The algorithms obtained using those techniques enjoy very low (at most linear) dependence on the dimension, at the cost of providing approximate answers. The problems amenable to these techniques include nearest neighbor search, clustering and PCA.However, the algorithmic solutions to these problems still possess (sometimes quite severe) limitations. Our goal is to identify methods for circumventing these limitations and making the algorithms efficient, both in theory and in practice.The techniques which led to the development of the aforementioned algorithms are new and still not widely known. They include many tools which have been developed during 70s and 80s in the field of mathematics called functional analysis. However, computer scientists became aware of those methods only very recently,and many of the fundamental results are still not widely known or used.Therefore, it is important to make these results accessible to large computer science audience so that they can be successfully used, investigated and developed. In the Education Plan section we outline a plan on how to make them more accessible to students as well as computer scientists.
本职业发展计划包括一系列的研究和教育活动,重点关注高维几何问题的算法。高维数据的几何计算对计算机科学的许多领域都至关重要,包括机器学习、数据挖掘、数据库和信息检索、计算机视觉和计算生物学。该领域的示例问题包括:最近邻搜索,数据聚类的许多变体,以及发现数据的线性结构(例如,通过主成分分析(PCA))。不幸的是,许多这些问题的经典几何算法不缩放以及与尺寸。例如,用于最近邻搜索的经典算法的运行时间以指数方式依赖于维度,这使得它们对于维度高于20的情况下效率低下。这是不幸的,因为许多应用涉及的维数从几百到几百万不等。近年来,人们发现了解决这些问题的新的、强大的技术,最著名的是几何空间中的降维和随机抽样。使用这些技术获得的算法对维度的依赖性非常低(最多是线性的),代价是提供近似的答案。这些技术适用的问题包括最近邻搜索、聚类和主成分分析,然而,这些问题的算法解决方案仍然具有(有时相当严重)的局限性。我们的目标是确定方法,以规避这些限制,使算法有效,在理论和实践中。导致上述算法的发展的技术是新的,仍然没有广泛的知名度。它们包括许多在70年代和80年代在数学领域开发的工具,称为泛函分析。然而,计算机科学家们直到最近才意识到这些方法,许多基本结果仍然没有被广泛了解或使用。因此,重要的是要让大量的计算机科学观众可以访问这些结果,以便它们可以成功地使用,研究和开发。在教育计划部分,我们概述了如何使学生和计算机科学家更容易使用它们的计划。

项目成果

期刊论文数量(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 }}

Piotr Indyk其他文献

Differentially Private Approximate Near Neighbor Counting in High Dimensions
高维差分隐私近似近邻计数
  • DOI:
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Alexandr Andoni;Piotr Indyk;S. Mahabadi;Shyam Narayanan
  • 通讯作者:
    Shyam Narayanan
Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors
三元组、终端对比嵌入的尺寸精度权衡
  • DOI:
    10.48550/arxiv.2312.13490
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Vaggos Chatziafratis;Piotr Indyk
  • 通讯作者:
    Piotr Indyk

Piotr Indyk的其他文献

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

{{ truncateString('Piotr Indyk', 18)}}的其他基金

Travel: SODA 2024 Conference Student and Postdoc Travel Support
旅行:SODA 2024 会议学生和博士后旅行支持
  • 批准号:
    2343779
  • 财政年份:
    2023
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
Conference: SODA 2023 Conference Student and Postdoc Travel Support
会议:SODA 2023 会议学生和博士后旅行支持
  • 批准号:
    2232958
  • 财政年份:
    2022
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
Foundations of Data Science Institute
数据科学研究所基础
  • 批准号:
    2022448
  • 财政年份:
    2020
  • 资助金额:
    --
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Small: Fine-Grained Complexity of Approximate Problems
协作研究:AF:小:近似问题的细粒度复杂性
  • 批准号:
    2006798
  • 财政年份:
    2020
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
TRIPODS: Institute for Foundations of Data Science (IFDS)
TRIPODS:数据科学研究所 (IFDS)
  • 批准号:
    1740751
  • 财政年份:
    2017
  • 资助金额:
    --
  • 项目类别:
    Continuing Grant
AitF: FULL: Sparse Fourier Transform: From Theory to Practice
AitF:FULL:稀疏傅里叶变换:从理论到实践
  • 批准号:
    1535851
  • 财政年份:
    2015
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
BIGDATA: F: DKA: Collaborative Research: Structured Nearest Neighbor Search in High Dimensions
BIGDATA:F:DKA:协作研究:高维结构化最近邻搜索
  • 批准号:
    1447476
  • 财政年份:
    2015
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
AF: Large: Collaborative Research: Compact Representations and Efficient Algorithms for Distributed Geometric Data
AF:大型:协作研究:分布式几何数据的紧凑表示和高效算法
  • 批准号:
    1012042
  • 财政年份:
    2010
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
Fast Approximate Algorithms for Wireless Sensor Networks
无线传感器网络的快速近似算法
  • 批准号:
    0728645
  • 财政年份:
    2007
  • 资助金额:
    --
  • 项目类别:
    Standard Grant

相似海外基金

Novel Algorithms to Approximate the Future Consequence of Sequential Decisions
近似连续决策的未来后果的新算法
  • 批准号:
    RGPIN-2017-04877
  • 财政年份:
    2022
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
A study on practical algorithms for combinatorial optimization based on approximate submodularity
基于近似子模性的组合优化实用算法研究
  • 批准号:
    22K17857
  • 财政年份:
    2022
  • 资助金额:
    --
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
Novel Algorithms to Approximate the Future Consequence of Sequential Decisions
近似连续决策的未来后果的新算法
  • 批准号:
    RGPIN-2017-04877
  • 财政年份:
    2021
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
Novel Algorithms to Approximate the Future Consequence of Sequential Decisions
近似连续决策的未来后果的新算法
  • 批准号:
    RGPIN-2017-04877
  • 财政年份:
    2020
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
CAREER: Approximate Scheduling Algorithms via Mathematical Relaxations
职业:通过数学松弛的近似调度算法
  • 批准号:
    1844890
  • 财政年份:
    2019
  • 资助金额:
    --
  • 项目类别:
    Continuing Grant
Novel Algorithms to Approximate the Future Consequence of Sequential Decisions
近似连续决策的未来后果的新算法
  • 批准号:
    RGPIN-2017-04877
  • 财政年份:
    2019
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
CRII: CIF: Approximate Message Passing Algorithms for High-Dimensional Estimation
CRII:CIF:高维估计的近似消息传递算法
  • 批准号:
    1849883
  • 财政年份:
    2019
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
Approximate Optimization Algorithms with Theoretical Rationales in Markov Decision Processes
马尔可夫决策过程中具有理论依据的近似优化算法
  • 批准号:
    19K04904
  • 财政年份:
    2019
  • 资助金额:
    --
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Fast approximate inference methods: new algorithms, applications and theory
快速近似推理方法:新算法、应用和理论
  • 批准号:
    DP180100597
  • 财政年份:
    2018
  • 资助金额:
    --
  • 项目类别:
    Discovery Projects
Novel Algorithms to Approximate the Future Consequence of Sequential Decisions
近似连续决策的未来后果的新算法
  • 批准号:
    RGPIN-2017-04877
  • 财政年份:
    2018
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了