CAREER: Approximate Algorithms for High-dimensional Geometric Problems

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

• 批准号: 0133849
• 负责人: Piotr Indyk
• 金额: --
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-04-01 至 2007-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0133849&HistoricalAwards=false
• 关键词: CAREER; Approximate; Algorithms; dimensional; Geometric

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 的情况效率低下。这是不幸的，因为许多应用程序涉及的维度数量从几百到数百不等。近年来，已经发现了解决这些问题的新的、强​​大的技术，最引人注目的是几何空间中的降维和随机采样。使用这些技术获得的算法对维度的依赖性非常低（最多线性），但代价是提供近似答案。这些技术适用的问题包括最近邻搜索、聚类和 PCA。然而，这些问题的算法解决方案仍然具有（有时相当严重）的局限性。我们的目标是找出在理论上和实践上规避这些限制并使算法高效的方法。导致上述算法发展的技术是新的，但尚未广为人知。它们包括 70 年代和 80 年代在数学领域开发的许多工具，称为泛函分析。然而，计算机科学家直到最近才意识到这些方法，并且许多基本结果仍然没有被广泛了解或使用。因此，重要的是让大量计算机科学受众能够访问这些结果，以便它们能够成功使用，研究和开发。在教育计划部分，我们概述了如何让学生和计算机科学家更容易接触到这些内容的计划。